Implement two Stacks in an Array Easy 0 attempts
GeeksforGeeks ↗

Implement two Stacks in an Array

Easy Stack&Queue GeeksforGeeks

Implement two stacks using a single array efficiently. Both stacks should grow in opposite directions: stack 1 grows from the start and stack 2 grows from the end of the array. Support push1, push2, pop1, and pop2 operations. An overflow occurs only when the two stacks meet in the middle.

Example:

push1(1), push2(2), push1(3), pop1() -> 3, pop2() -> 2
Sample Input
—
Sample Output
—
Constraints
  • 1 <= N <= 100
Topics
Stack&Queue

Two-End Approach

Stack 1 grows from left, Stack 2 grows from right.

class TwoStacks {
  constructor(n) { this.arr = new Array(n); this.top1 = -1; this.top2 = n; this.size = n; }
  push1(x) { if (this.top1 < this.top2 - 1) this.arr[++this.top1] = x; }
  push2(x) { if (this.top1 < this.top2 - 1) this.arr[--this.top2] = x; }
  pop1() { return this.top1 >= 0 ? this.arr[this.top1--] : -1; }
  pop2() { return this.top2 < this.size ? this.arr[this.top2++] : -1; }
}

Time: O(1) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript