How to implement two stacks in an array in C++

Hi there. Today we will see how to implement two stacks in an array using C++. There are two ways to solve this question. The first method divides the space into two halves, and assigns one half to each stack. But this method is not efficient. We will implement an efficient method.

The method we will implement utilizes the available space efficiently. It doesn’t run into the overflow condition. We start both stacks from the opposite corners of the array, and instead of allocating a particular size, we keep pushing elements in both the stacks. Let’s look at the implementation part.

Program to implement two stacks in an array in C++

We can push and pop elements from both the stacks freely, but we need to take care of the distance between the tops of both the stacks. If the distance becomes 0, then there will be no space left to add elements in both stacks. So we need to check for it every time we push something in either of the stack. Let’s look at the code now.

#include<bits/stdc++.h>
using namespace std; 
  
class tsc 
{ 
    int *a; 
    int len; 
    int t1, t2; 
public: 
   tsc(int n)
   { 
       len=n; 
       a=new int[n]; 
       t1=-1; 
       t2=len; 
   } 
  
   
   void push1(int x) 
   { 
       
       if(t1<t2 - 1) 
       { 
           t1++; 
           a[t1]=x; 
       } 
       else
       { 
           cout<<"Stack Overflow"; 
           exit(1); 
       } 
   } 
  
   void push2(int x) 
   {       
       if(t1<t2 - 1) 
       { 
           t2--; 
           a[t2]=x; 
       } 
       else
       { 
           cout<<"Stack Overflow"; 
           exit(1); 
       } 
   } 
   
   int pop1() 
   { 
       if (t1>=0) 
       { 
          int x=a[t1]; 
          t1--; 
          return x; 
       } 
       else
       { 
           cout<<"Stack UnderFlow"; 
           exit(1); 
       } 
   } 
  
   int pop2() 
   { 
       if(t2<len) 
       { 
          int x=a[t2]; 
          t2++; 
          return x; 
       } 
       else
       { 
           cout<<"Stack UnderFlow"; 
           exit(1); 
       } 
   } 
}; 
  
int main() 
{ 
    tsc ts(5); 
    ts.push1(1); 
    ts.push2(2); 
    ts.push2(3); 
    ts.push1(4); 
    ts.push2(5); 
    cout<<"Element popped from stack1 is "<<ts.pop1()<<endl; 
    ts.push2(6); 
    cout<<"Element popped from stack2 is "<<ts.pop2(); 
    return 0; 
}

As you can see, we push 6 elements at different intervals, and print the result for both the stacks. Let’s look at the output.

Element popped from stack1 is 4
Element popped from stack2 is 6

I hope you found this article useful. After you are comfortable with this problem, try to implement the same for more than 2 stacks in a single array. It is quite challenging but a very interesting program to implement.

Leave a Reply

Your email address will not be published. Required fields are marked *