Multiple Stacks

Definition

Multiple stacks are a data structure arrangement in which two or more stacks are maintained in the same memory region, usually a single array, so that each stack can perform standard stack operations such as push, pop, and peek independently while sharing available space efficiently.

Main Content

1. First Concept

Single-array implementation of multiple stacks

Multiple stacks can be stored in one array rather than using separate arrays. This saves memory and allows flexible allocation of space. The simplest form is storing two stacks in one array, one growing from the left side and the other from the right side. If the array is large enough, both stacks can expand toward each other until they meet.

Example:

  Index: 0  1  2  3  4  5  6  7  8  9
         [A][A][A][ ][ ][ ][B][B][B][B]

Here, Stack A grows from the beginning and Stack B grows from the end.

Memory efficiency

If one stack is small and the other is large, the unused space can still be available to the other stack. This avoids wasting memory that would happen if each stack were given a fixed separate block. This is especially useful when stack sizes are unpredictable.

2. Second Concept

Different ways to implement multiple stacks

Multiple stacks can be implemented in several ways:

Two stacks in one array with opposite growth directions.
k stacks in one array using fixed partitioning.
k stacks in one array using dynamic allocation with auxiliary arrays such as top[], next[], and free list.

Each method has advantages depending on the use case. Fixed partitioning is simple but wasteful if stacks are uneven. Dynamic sharing is more efficient but more complex.

Stack metadata management

To manage multiple stacks, we need extra information such as the top index of each stack. For example, if there are three stacks, an array top[3] may store the current top positions of each stack. In more advanced implementations, another array tracks the next free slot or links between elements. This metadata helps determine where to push, pop, and whether a stack is empty or full.

3. Third Concept

Operations on multiple stacks

Each stack still supports standard operations:

Push: Insert an element onto a chosen stack.
Pop: Remove the top element from that stack.
Peek/Top: Read the top element without removing it.
isEmpty / isFull: Check whether the stack has no elements or no available space.

These operations must be carefully adapted to handle shared memory. For example, in a dynamic multi-stack system, a push operation must first check whether a free slot exists before inserting.

Example of two stacks in one array

Suppose an array of size 10 is used:

Stack 1 starts from index 0 and grows rightward.
Stack 2 starts from index 9 and grows leftward.

If Stack 1 pushes 10, 20 and Stack 2 pushes 90, 80, the array may look like this:

  [10][20][ ][ ][ ][ ][ ][ ][80][90]
     S1 ->                     <- S2

Each stack behaves independently, but both share the same array.

Working / Process

1. Initialize memory and stack pointers

Create the shared array and initialize the top pointers or indexes for each stack. For two stacks, one top may start at -1 and the other at the last index. For k stacks, initialize a top[] array and, if using dynamic sharing, a free list structure.

2. Perform push and pop operations with boundary checks

When pushing, verify that the shared memory has space. For fixed partitioning, ensure the stack does not exceed its allocated segment. For dynamic multiple stacks, use the next available free slot. When popping, update the top pointer and return the removed value.

3. Handle overflow and underflow correctly

If there is no space available, a push causes overflow. If a stack is empty and a pop is requested, underflow occurs. Proper checks prevent data corruption and ensure each stack remains valid even while sharing storage.

Advantages / Applications

Better memory utilization

Shared storage reduces wasted space compared to allocating separate fixed-size arrays for each stack.

Flexibility in stack sizes

One stack can use more space when needed, as long as unused space is available in the shared memory region.

Useful in system-level and algorithmic problems

Multiple stacks appear in memory managers, expression parsing, recursion simulation, undo/redo systems, and in interview-style problems involving efficient resource sharing.

Summary

Multiple stacks store more than one stack in shared memory.
They improve space usage compared with separate fixed-size stacks.
Common implementations include two stacks in one array and dynamic k-stack systems.
Important terms to remember: stack, top pointer, push, pop, overflow, underflow, shared memory, fixed partitioning, dynamic allocation