<p>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)).</p>

CC BY-SA 4.0
2019-05-11T14:46:45.827Z
How do you recycle memory obtained by popping things from one of the large chunks?
Emil Jeřábek
CC BY-SA 4.0
2019-05-11T16:30:26.747Z
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.
Alexei Kaigorodov
CC BY-SA 4.0
2019-05-14T11:49:28.473Z
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.
user1020406
CC BY-SA 4.0
2019-05-11T11:26:42.277Z
2019-05-11T11:26:42.277Z
Alexei Kaigorodov
<p>Fredman and Goldsmith showed in "Three Stacks" (Journal of Algorithms, 1994) that <span class="math-container">$\Theta(n^\varepsilon)$</span> 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 <span class="math-container">$\Theta(\sqrt{n})$</span> <em>words</em> of space in <a href="https://stackoverflow.com/a/38947631/388716">my StackOverflow answer to this question</a>. As @dmitri-urbanowicz mentioned in the comments, this is basically just treating the array as <span class="math-container">$\sqrt{n}$</span> blocks of size <span class="math-container">$\sqrt{n}$</span>, where each block is used for exactly one stack and contains a single pointer to the next block in that stack.</p>

CC BY-SA 4.0
2019-06-12T04:40:25.543Z
2019-06-12T04:40:25.543Z
jbapple
<p>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?</p>

<p>More specifically, is it possible to implement three stacks given the following conditions:</p>

<ol>
<li>You have a fixed size array that can hold N objects.</li>
<li>As long as the sum of the three stack sizes is &lt; N, push() should not fail.</li>
<li>Both push() and pop() operations should take O(1) time.</li>
<li>In addition to the array, you can use only O(1) additional space.</li>
</ol>

<p>Here are examples of solutions that do <em>not</em> satisfy these requirements:</p>

<ul>
<li>Splitting the array into 3 fixed parts and using each part for a stack (violates 2).</li>
<li>Similar to the above but with movable boundaries between stacks (violates 3).</li>
<li>Simple linked-list based implementations (violates 4).</li>
</ul>

<p>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.</p>

CC BY-SA 4.0
2019-05-05T01:11:02.213Z
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
CC BY-SA 4.0
2019-05-07T02:37:53.923Z
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
CC BY-SA 4.0
2021-01-18T17:16:08.737Z
FYI I've just come across the area of research dedicated to representing data structures with minimum space overhead. See this wiki entry and the references: https://en.wikipedia.org/wiki/Succinct_data_structure
user1020406
CC BY-SA 4.0
2019-05-13T09:41:49.687Z
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
CC BY-SA 4.0
2019-05-13T13:44:28.833Z
Would $O(\sqrt{N})$ of additional space satisfy you?
Dmitri Urbanowicz
CC BY-SA 4.0
2019-05-14T12:00:54.493Z
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
CC BY-SA 4.0
2019-05-14T18:30:41.617Z
$O(\sqrt{N})$ is basically linked-list solution that operates on large blocks. Not sure if it qualifies as non-trivial.
Dmitri Urbanowicz
<ds.data-structures><lower-bounds>
Can three stacks be implemented in one array, with O(1) push/pop time?
user1020406
# Can three stacks be implemented in one array, with O(1) push/pop time?

(Asked by: username_0 on 2019-05-04)

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.

**Tags:** ds.data-structures, lower-bounds

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: 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?  
> **username_2**: Would $O(\sqrt{N})$ of additional space satisfy you?  
> **username_0**: 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.  
> **username_2**: $O(\sqrt{N})$ is basically linked-list solution that operates on large blocks. Not sure if it qualifies as non-trivial.  
> **username_0**: FYI I've just come across the area of research dedicated to representing data structures with minimum space overhead. See this wiki entry and the references: https://en.wikipedia.org/wiki/Succinct_data_structure  

---

## 2 answers

### Answer by username_5 on 2019-06-12. Score: 6 | Accepted answer

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](https://stackoverflow.com/a/38947631/388716). 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.


---

### Answer by username_3 on 2019-05-11. Score: 0

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)).

> **Comments:**
> **username_4**: How do you recycle memory obtained by popping things from one of the large chunks?  
> **username_3**: 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.  
> **username_0**: 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.  

---

