Implement Two Stacks in a Single Array

Implement Two Stacks in a Single Array” is a popular technical interview problem based on stack. Here, we are given an array of size ‘n’ and our task is to implement two stacks in this single array.

We need to ensure that the space in an array is maximally utilized.

This problem is quite tricky and requires some basic thinking.

METHOD 1: Dividing the Array into Two Halves

The Brute-Force Solution of this problem is, that, we can divide the given array into two halves and allocate first half of the array to implement first stack and second half of the array to implement second stack.

For example, If the array size is 1000. Then, we can reserve indexes from 0 to 499 to implement first stack, and indexes from 500 to 999 to implement second stack.

This Approach seems quite simple and efficient, but there is a problem in this approach. Suppose, we need to push 600 elements into first stack and 30 elements into second stack. Now, for first stack, we can only push at max 500 elements because, we previously defined the limit. For second stack, we can easily push 30 elements into the stack. 

Now, we had total space to store 1000 elements. 

Total Elements inserted into first stack is 500 and total elements inserted into second stack is 30. So, 1000 – (500+30) = 470 is still available and still we cannot insert 100 left out elements which are needed to be pushed into first stack.

So, here, using the following approach, we are wasting the space and also, we are not able to push elements into stack, when array space is still available. Therefore, we are not utilizing the space efficiently.

METHOD 2: Pushing Elements into Array from Extreme End (A Space Efficient Approach)

This Method is space efficient method and utilizes the array space efficiently. In this method, we push the elements into the stacks from extreme ends (‘0’ and ‘n-1’) of the array and grow the stack accordingly.

For example:

There is an array of size 1000. Now, if we want to push 600 elements into first stack and 30 elements into second stack, we can easily store these into array as:

  1. From index 0 to 599, elements of first stack will be pushed.
  2. From index 999 to 970(in reverse order), elements of the second stack will be pushed.

And, for Pop Operation also, both the stack will pop out the elements in opposite direction.

In this approach, an overflow condition occurs only if the space is fully utilized and there will be no space in an array to push an element from either of stack. 

C++ Program to Implement Two Stacks in a Single Array is as follows:

/* C++ Program to Implement Two Stacks in a Single Array */
#include<bits/stdc++.h>
using namespace std;

/* Class to Implement Two Stack */
class implementTwoStacks
{
    int *arr;
    int size;
    int top1; /* Variable to monitor top of first stack */
    int top2; /* variable to monitor top of second stack */
    
    public:
    
    /* Constructor */
    implementTwoStacks(int n)
    {
        size = n;
        arr = new int[size]; /* Dynamically Allocating Memory to First Stack */
        top1 = -1; /* Initial Top of First Stack */
        top2 = n; /* Initial Top of Second Stack */
    }
    
    /* Method to Push an Element into First Stack */
    void pushFirst(int ele)
    {
        /*
            Check Overflow Condition!!
            Check if there is a space left in the array, where an 
            Element can be pushed.
        */
        if(top2 > top1 + 1)
        {
            top1++;
            arr[top1] = ele;
        }
        else
        {
            cout<<"Array is Already Full!! No More Elements can be pushed Now!!\n";
        }
    }
    
    /* Method to Push an Element into Second Stack */
    void pushSecond(int ele)
    {
        /*
            Check Overflow Condition!!
            Check if there is a space left in the array, where an 
            Element can be pushed.
        */
        if(top2 > top1 + 1)
        {
            top2--;
            arr[top2] = ele;
        }
        else
        {
            cout<<"Array is Already Full!! No More Elements can be pushed Now!!\n";
        }
    }
    
    /* Method to Pop an Element from First Stack */
    int popFirst()
    {
        /* Check Underflow Condition */
        if(top1 == -1)
        {
            cout<<"The First Stack is empty!! Nothing to Pop Out!!\n";
            exit(1);
        }
        else
        {
            int ele = arr[top1];
            top1--;
            return ele;
        }
    }
    
    /* Method to Pop an Element from Second Stack */
    int popSecond()
    {
        /* Check Underflow Condition */
        if(top2 == size)
        {
            cout<<"The Second Stack is empty!! Nothing to Pop Out!!\n";
            exit(1);
        }
        else
        {
            int ele = arr[top2];
            top2++;
            return ele;
        }
    }
    
};
int main()
{
    implementTwoStacks Stack(100); /* Creating an array of size 100 */
    
    /* Pushing Some Elements into First Stack */
    Stack.pushFirst(1);
    Stack.pushFirst(2);
    Stack.pushFirst(3);
    Stack.pushFirst(4);
    
    /* Pushing Some Elements into Second Stack */
    Stack.pushSecond(5);
    Stack.pushSecond(6);
    Stack.pushSecond(7);
    Stack.pushSecond(8);
    
    /* Popping and Printing Some Elements from First Stack */
    cout<<"\nThe Popped Elements of First Stack is "<<Stack.popFirst();
    cout<<"\nThe Popped Elements of First Stack is "<<Stack.popFirst();
    
    /* Popping and Printing Some Elements from Second Stack */
    cout<<"\nThe Popped Elements of Second Stack is "<<Stack.popSecond();
    cout<<"\nThe Popped Elements of Second Stack is "<<Stack.popSecond();
    
}
OUTPUT:
The Popped Elements of First Stack is 4
The Popped Elements of First Stack is 3
The Popped Elements of Second Stack is 8
The Popped Elements of Second Stack is 7

Related Posts:

  1. Print Bracket Number
  2. Next Greater Frequency Element
  3. Sort a Stack using Temporary Stack
  4. Infix to Postfix Conversion
  5. Infix to Prefix Conversion
  6. Prefix to Infix Conversion
  7. Prefix to Postfix Conversion
  8. Postfix to Infix Conversion
  9. Postfix to Prefix Conversion
  10. Check whether given Parentheses String are Balanced Parentheses or Not.
  11. Next Greater Element
  12. Find Minimum number of bracket reversals required to make an expression balanced.
  13. Implement Queue Using Two Stacks.
  14. Merge Overlapping Intervals using Stacks
  15. Implement Stack Using Linked List
  16. Largest Rectangular Area in Histogram
  17. Length of Longest Valid Substring
  18. Reverse a String using Stack
  19. Program to Remove all the blank spaces from the String.
  20. Program to check if String is isogram or not.

You may also like...

Leave a Reply

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