In our first case study on evaluating arithmetic expressions

In our first case study on evaluating arithmetic 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 arrays, 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 operations 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 Alls up three quarters. The top member function of the STL slack returns a reference to the top item. This is similar to the way that our node class from Chapter 6 has a data function that returns a reference to the item in the node (see page 323). For this project, modify both of the stack implementations

Solution

Here we will be using STACK and stack have LIFO organization i..e Last in first out ,Generally while implementing two stack in a single array we use simple technique where array size is divided by two and elements are added to the array but it leads to overflow and underflow problem i.e. space issues are there

but if we uses different technique where elements ae added from rightmost and leftmost end this issue can be resolvedi.e if array size is n supposingly so the two stack will pop the element and the element is returned to the array from the two end i.e one stack from left end and other one from right end

one stack starts from left end: top1 = top1++; 2nd stack starts from right end: top2=top2--;

and problem of underflow and overflow can be resolved space between top elements of the stack here we will enter the element s but size should be one quarter and three quarter for the leftmost and rightmost ends so

suppose sixe of array is n

so leftmost -1/4*n

and rightmost -3/4*n

#include<iostream>
#include<stdlib.h>

using namespace std;

class two_Stacks
{
   int *arr;
   int size,size2;
   int top1, top2;

public:
two_Stacks(int n)
{
   size = n/4;
   size2=n*3/4;
   arr = new int[n];
   top1 = -1;
   top2 = size;
}

void push1(int x)
{
  

   if (top1 < top2 - 1)
   {
       top1++;
       arr[top1] = x;
   }
   else
   {
       cout << \"Stack Overflow\";
       exit(1);
   }
}

void push2(int x)
{

   if (top1 < top2 - 1)
   {
       top2--;
       arr[top2] = x;

   }
   else
   {
       cout << \"Stack Overflow\";
       exit(1);
   }
}

int pop1()
{
   if (top1 >= 0 )
   {
       int x = arr[top1];
       top1--;
       return x;
   }
   else
   {
       cout << \"Stack UnderFlow\";
       exit(1);
   }

}

int pop2()
{
   if (top2 < size2)
   {
       int x = arr[top2];
       top2++;
       return x;
   }
   else
   {
       cout << \"Stack UnderFlow\";
       exit(1);
   }
}
};

int main()

{
   two_Stacks ts(100);
   ts.push1(2);
   ts.push2(3);
   ts.push2(4);
   ts.push1(5);
   ts.push2(6);
   cout << \"Popped element from stack1 is \" << ts.pop1();
   ts.push2(7);
   cout << \"\ Popped element from stack2 is \" << ts.pop2();
   return 0;
}