Double Stacks

Problem

Suppose you need to use two stacks, but want to store both in a single array of fixed size. Design a data structure that supports two stacks in one array, with one stack growing from the left and the other from the right. Both stacks should be able to grow toward the middle as long as there is space.

Implement the following operations:

• push1(x): Push an element onto Stack 1 (left stack).
• push2(x): Push an element onto Stack 2 (right stack).
• pop1(): Pop and return the top element from Stack 1. If empty, throw an exception or return an error value.
• pop2(): Pop and return the top element from Stack 2. If empty, throw an exception or return an error value.

The two stacks should not overwrite each other's data, and the combined number of elements in both stacks should never exceed the array size.

Examples

Example 1

Input:
push1(10)
push2(20)
push1(30)
pop1()
pop2()
Output:
30
20
Explanation:
First stack: [10, 30], Second stack: [20]. pop1() returns 30, pop2() returns 20.

Example 2

Input:
push1(5)
push2(15)
push1(25)
push2(35)
pop2()
pop1()
Output:
35
25
Explanation:
First stack: [5, 25], Second stack: [15, 35]. pop2() returns 35, pop1() returns 25.

Solution

Method 1 – Two Pointers (Left/Right Indices)

Intuition

Use two pointers: one starting from the left (for Stack 1) and one from the right (for Stack 2). Each stack grows toward the center. If the pointers cross, the array is full.

Approach

1. Initialize two pointers: left = 0 for Stack 1, right = n - 1 for Stack 2 (where n is the array size).
2. For push1(x), check if space exists (left <= right). If so, insert at arr[left] and increment left.
3. For push2(x), check if space exists (left <= right). If so, insert at arr[right] and decrement right.
4. For pop1(), if left > 0, decrement left and return arr[left].
5. For pop2(), if right < n - 1, increment right and return arr[right].
6. If a push is attempted when left > right, throw an overflow error.

Code

C++

class TwoStacks {
  int* arr;
  int n, left, right;
public:
  TwoStacks(int size) : n(size), left(0), right(size-1) {
    arr = new int[n];
  }
  void push1(int x) {
    if (left > right) throw std::overflow_error("Stack Overflow");
    arr[left++] = x;
  }
  void push2(int x) {
    if (left > right) throw std::overflow_error("Stack Overflow");
    arr[right--] = x;
  }
  int pop1() {
    if (left == 0) throw std::underflow_error("Stack 1 Empty");
    return arr[--left];
  }
  int pop2() {
    if (right == n-1) throw std::underflow_error("Stack 2 Empty");
    return arr[++right];
  }
};

Go

type TwoStacks struct {
  arr   []int
  left  int
  right int
}

func NewTwoStacks(size int) *TwoStacks {
  return &TwoStacks{
    arr:   make([]int, size),
    left:  0,
    right: size - 1,
  }
}

func (s *TwoStacks) Push1(x int) error {
  if s.left > s.right {
    return errors.New("Stack Overflow")
  }
  s.arr[s.left] = x
  s.left++
  return nil
}

func (s *TwoStacks) Push2(x int) error {
  if s.left > s.right {
    return errors.New("Stack Overflow")
  }
  s.arr[s.right] = x
  s.right--
  return nil
}

func (s *TwoStacks) Pop1() (int, error) {
  if s.left == 0 {
    return 0, errors.New("Stack 1 Empty")
  }
  s.left--
  return s.arr[s.left], nil
}

func (s *TwoStacks) Pop2() (int, error) {
  if s.right == len(s.arr)-1 {
    return 0, errors.New("Stack 2 Empty")
  }
  s.right++
  return s.arr[s.right], nil
}

Java

class TwoStacks {
  int[] arr;
  int left, right;
  public TwoStacks(int size) {
    arr = new int[size];
    left = 0;
    right = size - 1;
  }
  public void push1(int x) {
    if (left > right) throw new RuntimeException("Stack Overflow");
    arr[left++] = x;
  }
  public void push2(int x) {
    if (left > right) throw new RuntimeException("Stack Overflow");
    arr[right--] = x;
  }
  public int pop1() {
    if (left == 0) throw new RuntimeException("Stack 1 Empty");
    return arr[--left];
  }
  public int pop2() {
    if (right == arr.length - 1) throw new RuntimeException("Stack 2 Empty");
    return arr[++right];
  }
}

Python

class TwoStacks:
  def __init__(self, size: int):
    self.arr = [0] * size
    self.left = 0
    self.right = size - 1

  def push1(self, x: int) -> None:
    if self.left > self.right:
      raise Exception("Stack Overflow")
    self.arr[self.left] = x
    self.left += 1

  def push2(self, x: int) -> None:
    if self.left > self.right:
      raise Exception("Stack Overflow")
    self.arr[self.right] = x
    self.right -= 1

  def pop1(self) -> int:
    if self.left == 0:
      raise Exception("Stack 1 Empty")
    self.left -= 1
    return self.arr[self.left]

  def pop2(self) -> int:
    if self.right == len(self.arr) - 1:
      raise Exception("Stack 2 Empty")
    self.right += 1
    return self.arr[self.right]

Complexity

• ⏰ Time complexity: O(1) for all operations, as each push/pop is a single array access and pointer update.
• 🧺 Space complexity: O(n) for the array of size n.