Implement two stacks in one array

Easy

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.