In our first case study on evaluating arith- metic expressions we used two stack

Question

In our first case study on evaluating arith-

metic expressions we used two stacks that

held different types of data. In some other

applications, we might need two stacks with the

same type of data. If we implement the stacks as ar-

rays, there is a chance that one array (and hence one

stack) becomes filled, causing our computation to

end prematurely. This might be a shame, since the

other array (stack) might have plenty of room. One

way around this problem is to implement two stacks

as one large array rather than two smaller arrays.

Write a class for a pair of stacks. A pair of stacks is

simply an object with two stacks. Call these stacks

StackA and StackB. There should be separate opera-

tions for each stack, for example, pop_a and pop_b.

Implement the stack pair as a single array. The two

stacks grow from the two ends of the array, so for

example, one stack could fill up one quarter of the

array while the other fills up three quarters.

Explanation / Answer

#define MAX 1000
int arr[MAX];

class dual_stack
{
int top_a = -1;
int top_b = MAX;
int pop_a( int * top_a);
int pop_b( int * top_b);
void push_a( int * top_a, int *top_b, int data);
void push_b( int * top_b, int *top_b, int data);
};

void dual_stack::push_a( int *top_a, int *top_b, int data )
{
if(*top_b - *top_a == 1 )
{
cout<<"Stack full";
}
else
{
*top_a += 1;
arr[ *top_a ] = data;
}
}

void dual_stack::push_b( int *top_a, int *top_b, int data )
{
if(*top_b - *top_a == 1 )
{
cout<<"Stack full";
}
else
{
*top_b -= 1;
arr[ *top_b ] = data;
}
}

int dual_stack::pop_a( int *top_a )
{
if( *top_a < 0 )
{
cout<<"Stack empty";
}
else
{
*top_a -=1;
return arr[*top_a + 1];
}
}

int dual_stack::pop_b( int *top_b )
{
if( *top_b > MAX-1 )
{
cout<<"Stack empty";
}
else
{
*top_a +=1;
return arr[*top_a - 1];
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.