9
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – Avi Tal
    Commented May 5, 2019 at 1:11
  • $\begingroup$ 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. $\endgroup$
    – user1020406
    Commented May 7, 2019 at 2:37
  • 1
    $\begingroup$ 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? $\endgroup$
    – Dmitri Urbanowicz
    Commented May 13, 2019 at 9:41
  • $\begingroup$ Would $O(\sqrt{N})$ of additional space satisfy you? $\endgroup$
    – Dmitri Urbanowicz
    Commented May 13, 2019 at 13:44
  • $\begingroup$ 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. $\endgroup$
    – user1020406
    Commented May 14, 2019 at 12:00

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

Let N be the length of the underlying array. I can imagine stacks as linked lists of large chunks, so that overall number of chunks is no more than O(log2(N)). Place the third stack between the first two, at the index of N/2. So we have 3 occupied areas and 2 free. When a stack cannot accept next element, this means one free area is exhausted. If the other is exhausted too, then the whole memory is exhausted. Otherwise, there is another free area with size no more than N/2. Continue the overflowed stack into that free area. so that the whole configuration resembles the initial layout of stacks. Since the free memory now is no more than the half of the initial, there will be no more than log2(N) of such linking operations. Each linking operation requires fixed amount of memory to save previous state of the stack. So, the memory overhead is no more than O(log2(N)).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ How do you recycle memory obtained by popping things from one of the large chunks? $\endgroup$
    – Emil Jeřábek
    Commented May 11, 2019 at 14:46
  • $\begingroup$ Good question. Quick answer is that chunk which becomes free returns its memory to the free area where it was previously taken from. But what if the free area shrinked since the time of allocation memory for that chunk, and the chunk is now not adjacent with it? This leads to fragmentation of free memory, there can be more than 2 free areas, which ruins all my construction. $\endgroup$
    – Alexei Kaigorodov
    Commented May 11, 2019 at 16:30
  • $\begingroup$ Popping is indeed the problem here, but Alexei's construction provides a nice upper bound for the version of the problem that Dmitri asked about in the comments: what if we require all pushes to happen before all pops? I wonder whether anything better than O(log N) is possible in this case. $\endgroup$
    – user1020406
    Commented May 14, 2019 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.