Can three stacks be implemented in one array, with O(1) push/pop time?

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:

1. You have a fixed size array that can hold N objects.
2. As long as the sum of the three stack sizes is < N, push() should not fail.
3. Both push() and pop() operations should take O(1) time.
4. 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.

• I don't know if you consider this as a violation of requirement 4, but if each "object" in your N objects array can include an additional field such as an integer index, then you can implement the "linked lists" inside your array. You can hold the index of the top of each of the 3 stacks using 3 external variables, and each "object" can point to the previous element it its stack. – Avi Tal May 5 at 1:11
• By "objects" I meant things that push() accepts and pop() returns. From the point of view of the stack implementation, they are just opaque blobs of data (for example, an object could be a 32-bit integer). The stack implementation should not modify these objects in any way. – user1020406 May 7 at 2:37
• Consider you first do a sequence of $N$ push operations and then only do pop operations. Is anything known about this version of the problem? – Dmitri Urbanowicz May 13 at 9:41
• Would $O(\sqrt{N})$ of additional space satisfy you? – Dmitri Urbanowicz May 13 at 13:44
• Re: "N pushes and then N pops" version: I don't know, but even identifying this as an interesting subproblem is useful because even there it's not clear whether an O(1) solution is possible. See @Alexei's answer and its comment thread for the upper bound. As for an $O(\sqrt N)$ solution, yes I'll accept. I'm new at posting questions on stackexchange, so I'm not sure how to handle cases where better and better solutions can be provided over time. One approach I've seen was to wait a day or so before accepting an answer in case something better is posted, so I'll do that. – user1020406 May 14 at 12:00

Fredman and Goldsmith showed in "Three Stacks" (Journal of Algorithms, 1994) that $$\Theta(n^\varepsilon)$$ bits of wasted space is achievable. It is also the minimum needed for arrays of size at least 16 quattuordecillion yottabytes. I described a simple algorithm wasting $$\Theta(\sqrt{n})$$ words of space in my StackOverflow answer to this question. As @dmitri-urbanowicz mentioned in the comments, this is basically just treating the array as $$\sqrt{n}$$ blocks of size $$\sqrt{n}$$, where each block is used for exactly one stack and contains a single pointer to the next block in that stack.