Stack • Advanced Implementation

Two Stacks in One Array

How can you efficiently implement two separate stacks within a single statically sized array? The trick is to start at opposite ends and grow inwards.

Try Interactive Simulator

The Naive Approach

You could divide the array strictly in half (indices 0 to N/2 for Stack 1, and N/2 to N for Stack 2). But if Stack 1 gets full while Stack 2 is completely empty, you throw an Overflow error despite having empty space.

The Optimal Approach

Initialize `top1 = -1` and `top2 = size`. Stack 1 grows left-to-right. Stack 2 grows right-to-left. This way, no space is wasted. You only overflow when the two pointers collide.

The Collision Condition

The stacks are completely full ONLY when `top2 - top1 == 1`. At this exact moment, there are zero empty slots between them.

Top 1▼

▲Top 2

Code Tracker

:::

1function push1(x) {

2 if (top2 - top1 > 1) {

3 top1++; arr[top1] = x;

4 }

5}

6function push2(x) {

7 if (top2 - top1 > 1) {

8 top2--; arr[top2] = x;

9 }

10}

Two Stack One Array

Two Stack One Array

Two Stacks in One Array

The Naive Approach

The Optimal Approach

The Collision Condition

Two Stacks in One Array

The Naive Approach

The Optimal Approach

The Collision Condition