Multiple Stacks

The use of a contiguous stack (using array) when more than one stack is needed is not a space efficient approach, because many locations in the stacks are often left unused.

An efficient solution to this problem is to use a single array to store more than one stack. The solution is simple if we implement only two stacks. The first stack grows towards A[n - 1] from A[0] and the second stack grows towards A[0] from A[n − 1]. The space can be used most efficiently so that the stack is full only when the top of one stack reaches the top of other stack.

The difficulty arises to represent m stacks in the memory. This can be overcome by dividing A[0, ..., n - 1] into m segments and allocate one of these segments to each of the m stacks .