Implement two stacks in one array
Problem
Implement two independent stacks inside a single fixed-size array so that neither overflows while free space remains anywhere in the array.
Example 1
Input: size 5: push1(1), push2(5), push2(4), pop1(), pop2() Output: 1, 4
Also asked as: Implement 2 stack in an array · Implement "N" stacks in an Array · Implement "n" queue in an array
Test cases
Case 1
Input: new TwoStacks(5) .push1(1) .push2(5) .push2(4) .pop1() .pop2() .pop2() .pop2() Expected: [null,null,null,1,4,5,null]
Case 2
Input: new TwoStacks(2) .push1(1) .push2(2) .pop1() .pop2() Expected: [null,null,1,2]
Case 3
Input: new TwoStacks(3) .pop1() .pop2() Expected: [null,null]
View solutionHide solution1 approach
1. Grow from both ends
Time O(1) per opSpace O(n)
Stack 1 grows from index 0 upward, stack 2 grows from the last index downward; they collide only when the array is full.
class TwoStacks { constructor(n) { this.a = new Array(n); this.top1 = -1; this.top2 = n; } push1(x) { if (this.top1 + 1 === this.top2) throw new Error('full'); this.a[++this.top1] = x; } push2(x) { if (this.top2 - 1 === this.top1) throw new Error('full'); this.a[--this.top2] = x; } pop1() { return this.top1 >= 0 ? this.a[this.top1--] : undefined; } pop2() { return this.top2 < this.a.length ? this.a[this.top2++] : undefined; }}For N stacks in one array: keep a `next[]` free-list and a `top[]` per stack; each cell stores the index of the previous element of its stack.