Multi-Stack - PCCST303

If a program needs two stacks, the obvious approach is two separate arrays, one per stack. But that forces you to guess how much space each stack will need ahead of time. Split the total space evenly between the two arrays, and it's easy to end up with one stack overflowing while the other sits mostly empty:

STACK 1OVERFLOW

STACK 2

unused

Total space: 8 slots, split into two fixed halves of 4 each

Stack 1 has run out of room and hit OVERFLOW, even though Stack 2 still has three unused slots. Because the two stacks use separate arrays, Stack 1 cannot use those slots. A multi-stack fixes this by letting both stacks share a single array.

The idea: grow toward each other

Instead of splitting the array in two fixed halves, place Stack 1 at the left end, growing rightward, and Stack 2 at the right end, growing leftward. Both stacks share the same underlying array, and the boundary between them isn't fixed, it's wherever the two stacks happen to meet.

01234567

↑TOP1

↑TOP2

Stack 1 (blue) has grown 3 elements in from the left, TOP1 pointing at the last one pushed. Stack 2 (violet) has grown 2 elements in from the right, TOP2 pointing at the last one pushed there. The dashed cells in the middle are unused, and either stack is free to grow into that space as needed.

Key Idea

This works because both stacks are growing toward the same shared pool of unused space, rather than each being boxed into its own fixed half. If Stack 1 turns out to need more room and Stack 2 stays small, Stack 1 simply grows further right into space Stack 2 was never using.

Applications

Multi-stacks matter most when memory is limited and the exact split between two stacks isn't known ahead of time:

Memory-constrained systems: embedded devices and older systems with small, fixed memory pools benefit from letting two stacks share one array rather than reserving separate, worst-case-sized arrays for each.
Compilers and interpreters: some implementations use two stacks growing toward each other, one for operands and one for operators or control data, within a single allocated block, for the same space-sharing reason.
Any two LIFO structures with unpredictable, inversely-related demand: if one stack tends to grow exactly when the other tends to shrink, sharing space means the total memory needed is closer to the sum of what's actually used, not the sum of two independently-sized worst cases.

Initial state and the full condition

Before anything is pushed, TOP1 = -1 (Stack 1 empty, same convention as a single stack) and TOP2 = n (Stack 2 empty, where n is the array size, one past the last valid index). Each push moves its TOP inward, and the array is only full once the two stacks meet:

Array is full when TOP1 + 1 == TOP2

At that point neither stack has any space left to grow into, since the entire array is filled by the two of them combined.

Operations

Each stack gets its own PUSH and POP, since they grow in opposite directions and need separate overflow/underflow checks.

PUSH1(x): push onto Stack 1

If TOP1 + 1 == TOP2
    return OVERFLOW
TOP1 = TOP1 + 1
A[TOP1] = x

Stack 1's overflow condition isn't "TOP1 reached the end of the array", it's "TOP1 is about to collide with TOP2", since Stack 2 might already be occupying the far end.

POP1(): pop from Stack 1

If TOP1 < 0
    return UNDERFLOW
value = A[TOP1]
TOP1 = TOP1 - 1
return value

PUSH2(x): push onto Stack 2

If TOP2 - 1 == TOP1
    return OVERFLOW
TOP2 = TOP2 - 1
A[TOP2] = x

This is the mirror image of PUSH1: Stack 2 moves TOP2 leftward instead of TOP1 rightward, and its overflow check is the same collision condition seen from the other side.

POP2(): pop from Stack 2

If TOP2 >= n
    return UNDERFLOW
value = A[TOP2]
TOP2 = TOP2 + 1
return value

Note

Notice PUSH1/POP1 mirror PUSH2/POP2 exactly, with left/right and increment/decrement swapped. If you understand one stack's pair of operations, the other pair is the same logic reflected.

Quick recall

A multi-stack fits two stacks into one array by growing them from opposite ends toward each other, instead of splitting the array into two fixed halves.
Stack 1 starts at TOP1 = -1 and grows rightward; Stack 2 starts at TOP2 = n and grows leftward.
The array is full when TOP1 + 1 == TOP2, the point where the two stacks meet.
The main advantage over two separate arrays is that unused space is shared dynamically between both stacks, rather than locked into whichever half it was assigned to.
Useful whenever two stacks have unpredictable, often inversely-related space needs, such as in memory-constrained systems or a compiler's operand/operator stacks.