Two stacks in an array

Optimized Approach 

In this approach, the starting index of both stacks is chosen as the extreme corners of the stack, i.e. from the leftmost and rightmost corner indices. Iteration is continued for every element and the array starts to shrink towards the middle while storing elements. The space between the top elements of the stacks is checked and if there is space, the elements are stored in those indices.

Pseudocode

The pseudocode for this approach is similar to the brute force approach with the difference that the loop iterations start from 0 for stack1 and from (n-1) for stack2.

Implementation in C++

// Program to implement two stacks in an array
#include <iostream>
#include <stdlib.h>
  
using namespace std;
  
class twoStacks {
    int* ar;
    int size;
    int top1, top2;
  
public:
    twoStacks(int n)
    {
        size = n;
        ar = new int[n];
        top1 = -1;
        top2 = size;
    }

    void push1(int x)
    {
        if (top1 < top2 - 1) {
            top1++;
            ar[top1] = x;
        }
        else {
            cout << "Stack Overflow";
            exit(1);
        }
    }

    void push2(int x)
    {
        if (top1 < top2 - 1) {
            top2--;
            ar[top2] = x;
        }
        else {
            cout << "Stack Overflow";
            exit(1);
        }
    }

    int pop1()
    {
        if (top1 >= 0) {
            int x = ar[top1];
            top1--;
            return x;
        }
        else {
            cout << "Stack UnderFlow";
            exit(1);
        }
    }
  
    int pop2()
    {
        if (top2 < size) {
            int x = ar[top2];
            top2++;
            return x;
        }
        else {
            cout << "Stack UnderFlow";
            exit(1);
        }
    }
};
  
int main()
{
    twoStacks ts(5);
    ts.push1(5);
    ts.push2(10);
    ts.push2(16);
    ts.push1(13);
    ts.push2(6);
    cout << "Popped element from stack1 is "
        << ts.pop1();
    ts.push2(12);
    cout << "\nPopped element from stack2 is "
        << ts.pop2();
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Implementation in Python

# Python Script to Implement two stacks in a list
class twoStacks:
      
    def __init__(self, n): 
        self.size = n
        self.ar = [None] * n
        self.top1 = -1
        self.top2 = self.size

    def push1(self, x):

        if self.top1 < self.top2 - 1 :
            self.top1 = self.top1 + 1
            self.ar[self.top1] = x
  
        else:
            print("Stack Overflow ")
            exit(1)

    def push2(self, x):

        if self.top1 < self.top2 - 1:
            self.top2 = self.top2 - 1
            self.ar[self.top2] = x
  
        else :
          print("Stack Overflow ")
          exit(1)

    def pop1(self):
        if self.top1 >= 0:
            x = self.ar[self.top1]
            self.top1 = self.top1 -1
            return x
        else:
            print("Stack Underflow ")
            exit(1)

    def pop2(self):
        if self.top2 < self.size:
            x = self.ar[self.top2]
            self.top2 = self.top2 + 1
            return x
        else:
            print("Stack Underflow ")
            exit()
  
# Main program
ts = twoStacks(5)
ts.push1(5)
ts.push2(10)
ts.push2(16)
ts.push1(13)
ts.push2(6)
  
print("Popped element from stack1 is " + str(ts.pop1()))
ts.push2(12)
print("Popped element from stack2 is " + str(ts.pop2()))

You can also try this code with Online Python Compiler

Run Code

Output: 

Popped element from stack1 is 13
Popped element from stack2 is 12

Complexity Analysis

Time Complexity - We have traversed over n elements and therefore, the time complexity is O(n).

Space Complexity - The auxiliary space is used for n elements and therefore, the space complexity is O(n), but the space is used more efficiently in this approach.

Check out this problem - Search In Rotated Sorted Array

Must Read Stack Operations

Frequently Asked Questions

What is the condition of overflow and underflow in a stack?

Removing elements from an empty stack is called stack underflow and adding elements to a full stack is called stack overflow.

What is the time complexity of pop() and push() operations?

O(1) is the time complexity of pop() operation as it accesses only one end of the stack and the same is the case for push() operations.

How many queues are required to implement a stack?

To implement a stack using enqueue and dequeue operations, we require two queues.

Conclusion

In this blog, we have discussed the approach to implement two stacks in an array where both the stacks use the same array for storing elements.

Recommended problems -

• Max circular subarray sum
• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Subarray sums divisible by k

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!