Implement Two Stacks in an Array

Problem Statement

In the “Implement Two Stacks in an Array” problem we have to implement two stacks in an array such that, if the user wants to push an element in either of two stacks then there should not be an error till the array gets full.

Example

Push 5 into stack1.
Push 10 into stack2.
Push 15 into stack2.
Push 11 into stack1.
Push 7 into stack2.
Popped element from stack1. 
Push 40 into stack2.
Popped element from stack2.

Stack Overflow By element: 7
Popped element from stack1 is: 11
Stack Overflow By element: 40
Popped element from stack2 is: 15

Algorithm

The idea is to start two stacks from the extreme corners of the array. Both these stacks will grow towards each other, stack1 will start from the leftmost corner and stack2 will start from the rightmost corner of the array.

1. stack1 will start from index 0 and grow towards the right end of the array

2. stack2 will start from index n-1 and grow towards the left end of the array

3. when both the stacks meet each other then we cant push an element in both stacks

We use push, pop functions to push elements in both stacks

1. push function will take the stack name and value to be inserted, and pushes the number into the respective stack

a. According to the stack name proceed

b. Check whether the stack is full or not ie, top1 < top2 -1 Here, top1, top2 are the variables
to keep track of top elements in both stacks

c. If not, push the element in the respective stack ie, arr[top1] = k

2. pop will take the stack name and will pop the topmost element in that stack

a. According to the stack name proceed

b. check whether there is any element to pop

c. If yes, decrement or increment the top1, top2 variables accordingly

Implementation

C++ Program to Implement Two Stacks in an Array

#include <bits/stdc++.h>
using namespace std;

class twoStacks 
{
  int* arr;
  int size;
  int top1, top2;

public:
  twoStacks(int n)
  {
    size = n;
    arr = new int[n];
    top1 = n / 2 + 1;
    top2 = n / 2;
  }
  void push1(int x)
  {
    if (top1 > 0) {
      top1--;
      arr[top1] = x;
    }
    else {
      cout << "Stack Overflow"
        << " By element :" << x << endl;
      return;
    }
  }
  void push2(int x)
  {
    if (top2 < size - 1) {
      top2++;
      arr[top2] = x;
    }
    else {
      cout << "Stack Overflow"
        << " By element : " << x << endl;
      return;
    }
  }
  int pop1()
  {
    if (top1 <= size / 2) {
      int x = arr[top1];
      top1++;
      return x;
    }
    else {
      cout << "Stack UnderFlow";
      exit(1);
    }
  }
  int pop2()
  {
    if (top2 >= size / 2 + 1) {
      int x = arr[top2];
      top2--;
      return x;
    }
    else {
      cout << "Stack UnderFlow";
      exit(1);
    }
  }
};

int main()
{
  twoStacks ts(5);
  ts.push1(5);
  ts.push2(10);
  ts.push2(15);
  ts.push1(11);
  ts.push2(7);
  cout << "Popped element from stack1 is "<< " : " << ts.pop1()<< endl;
  ts.push2(40);
  cout << "Popped element from stack2 is "<< " : " << ts.pop2()<< endl;
  return 0;
}

Java Program to Implement Two Stacks in an Array

import java.util.Scanner;
class twoStacks
{
  int[] arr;
  int size;
  int top1, top2;
  twoStacks(int n)
  {
    size = n;
    arr = new int[n];
    top1 = n / 2 + 1;
    top2 = n / 2;
  }
  void push1(int x)
  {
    if (top1 > 0)
    {
      top1--;
      arr[top1] = x;
    }
    else
    {
      System.out.print("Stack Overflow"+ " By element :" +  x +"\n");
      return;
    }
  }
  void push2(int x)
  {
    if (top2 < size - 1)
    {
      top2++;
      arr[top2] = x;
    }
    else
    {
      System.out.print("Stack Overflow"+ " By element : " +  x +"\n");
      return;
    }
  }
 
  // Method to pop an element from first stack
  int pop1()
  {
    if (top1 <= size / 2)
    {
      int x = arr[top1];
      top1++;
      return x;
    }
    else
    {
      System.out.print("Stack UnderFlow");
      System.exit(1);
    }
    return 0;
  }
 
  // Method to pop an element
  // from second stack
  int pop2()
  {
    if (top2 >= size / 2 + 1)
    {
      int x = arr[top2];
      top2--;
      return x;
    }
    else
    {
      System.out.print("Stack UnderFlow");
      System.exit(1);
    }
    return 1;
  }
};
class sum
{
    public static void main(String[] args)  
    { 
        twoStacks ts = new twoStacks(5);
        ts.push1(5);
        ts.push2(10);
        ts.push2(15);
        ts.push1(11);
        ts.push2(7);
        System.out.print("Popped element from stack1 is "+ " : " +  ts.pop1() +"\n");
        ts.push2(40);
        System.out.print("Popped element from stack2 is "+ ": " +  ts.pop2()+"\n");
    }
}

Stack Overflow By element :7
Popped element from stack1 is  : 11
Stack Overflow By element : 40
Popped element from stack2 is : 15

Complexity Analysis to Implement Two Stacks in an Array

Time Complexity

• Push operation: O(1) because we directly push an integer value at the end of the stack.
• Pop operation: O(1) because we directly remove the last value or the top value of the stack.

Space Complexity

O(N) because we use an array to implement the stack. It is not the space-optimized method as explained above.