Two stacks can be efficiently implemented using one fixed sized array: stack #1 starts from the left end and grows to the right, and stack #2 starts from the right end and grows to the left. Is the same possible for three stacks?
More specifically, is it possible to implement three stacks given the following conditions:
- You have a fixed size array that can hold N objects.
- As long as the sum of the three stack sizes is < N, push() should not fail.
- Both push() and pop() operations should take O(1) time.
- In addition to the array, you can use only O(1) additional space.
Here are examples of solutions that do not satisfy these requirements:
- Splitting the array into 3 fixed parts and using each part for a stack (violates 2).
- Similar to the above but with movable boundaries between stacks (violates 3).
- Simple linked-list based implementations (violates 4).
I'll accept non-trivial algorithms or impossibility proofs even if they don't meet all the conditions (1)-(4) exactly, for example, an algorithm where push/pop take O(1) amortized time, or where the additional memory is smaller than O(N), eg O(log N). Or an impossibility proof that shows that for example, accessing fewer than 5 elements of the array per push/pop is impossible.