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:


You have a fixed size array that can hold N objects.
As long as the sum of the three stack sizes is &lt; 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.
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.