Implement two Stacks in an Array Easy 0 attempts
GeeksforGeeks ↗

Implement two Stacks in an Array

Easy Stack&Queue GeeksforGeeks

Fit two independent stacks inside a single array without wasting space. Let the first stack grow forward from index 0, and the second grow backward from the last index, so they advance toward each other from opposite ends. Expose push1, push2, pop1, and pop2 for each stack respectively — space only runs out once the two stacks' pointers meet somewhere in the middle of the array.

Pushes into a full shared array leave it unchanged. Popping an empty stack returns -1.

Input Format
Implement the class TwoStacks. Fixtures contain constructor arguments and a list of [method, ...arguments] calls. Each fixture starts with a fresh instance.
Output Format
Return the specified result from each method. The displayed output lists results in call order; undefined results appear as null.

Sample Input and Output

Example 1 · Run Sample

Input
constructorArgs = [3]
operations = [["push1",1],["push2",2],["push1",3],["pop1"],["pop2"],["pop2"]]
Output
[null,null,null,3,2,-1]

Example 2

Input
constructorArgs = [1]
operations = [["push1",1],["push2",2],["pop2"],["pop1"]]
Output
[null,null,-1,1]
Constraints
  • 1 <= N <= 100
Test Cases (2)
Case 1
Args: [[3],[["push1",1],["push2",2],["push1",3],["pop1"],["pop2"],["pop2"]]] Expected: [null,null,null,3,2,-1]
Case 2
Args: [[1],[["push1",1],["push2",2],["pop2"],["pop1"]]] Expected: [null,null,-1,1]
Topics
Stack&Queue

Two-End Approach

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

javascript
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