How to implement three stacks using a single array

Question

I came across this problem in an interview website. The problem asks for efficiently implement three stacks in a single array, such that no stack overflows until there is no space left in the entire array space.

For implementing 2 stacks in an array, it's pretty obvious: 1st stack grows from LEFT to RIGHT, and 2nd stack grows from RIGHT to LEFT; and when the stackTopIndex crosses, it signals an overflow.

Thanks in advance for your insightful answer.

Answer 1

You can implement three stacks with a linked list:

• You need a pointer pointing to the next free element. Three more pointers return the last element of each stack (or null, if the stack is empty).
• When a stack gets another element added, it has to use the first free element and set the free pointer to the next free element (or an overflow error will be raised). Its own pointer has to point to the new element, from there back to the next element in the stack.
• When a stack gets an element removed it will hand it back into the list of free elements. The own pointer of the stack will be redirected to the next element in the stack.

A linked list can be implemented within an array.

How (space) efficent is this?
It is no problem to build a linked list by using two cells of an array for each list element (value + pointer). Depending on the specification you could even get pointer and value into one array element (e.g. the array is long, value and pointer are only int).
Compare this to the solution of kgiannakakis ... where you lose up to 50% (only in the worst case). But I think that my solution is a bit cleaner (and maybe more academic, which should be no disadvantage for an interview question ^^).

Answer 2

See Knuth, The Art of Computer Programming, Volume 1, Section 2.2.2. titled "Sequential allocation". Discusses allocating multiple queues/stacks in a single array, with algorithms dealing with overflows, etc.