<p>Not sure I fully understand your question, but it seems related to <a href="http://books.google.com/books?id=idUdqdDXqnAC&amp;lpg=PP1&amp;dq=%22Algorithms%22%20Robert%20Sedgewick%20and%20Kevin%20Wayne&amp;pg=PA171#v=onepage&amp;q=1.3.49&amp;f=false" rel="nofollow">Problem 1.3.49</a> from Sedgewicks Algorithm book.</p>

CC BY-SA 3.0
2011-04-12T07:05:20.530Z
That problem has an interesting story. See the discussion at http://stackoverflow.com/questions/5538192/how-to-implement-a-queue-with-three-stacks, which eventually leads to a change in the problem statement at http://algs4.cs.princeton.edu/13stacks/. (Originally the problem was about worst-case queue with 3 stacks, now 3 has been changed to "a constant number of".)
Maverick Woo
CC BY-SA 2.5
2011-04-05T08:43:42.847Z
2011-04-05T08:43:42.847Z
Martin B.
<p>In "<a href="http://ecommons.cornell.edu/handle/1813/6273" rel="nofollow noreferrer">Real Time Queue Operations in Pure LISP</a>" (<a href="https://web.archive.org/web/20100626050951/http://www.eecs.usma.edu/webs/people/okasaki/jfp95/queue.hm.sml" rel="nofollow noreferrer">ML implementation</a>), Hood and Melville show an $O(1)$ worst-case simulation of a queue using 6 stacks and global rebuilding. Can a real-time queue be simulated with fewer stacks?</p>

<p>In "<a href="https://web.archive.org/web/20120207055242/http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html" rel="nofollow noreferrer">Simple and Efficient Purely Functional Queues and Deques</a>", Okasaki shows an implementation using one stack and two lazy stacks.</p>

<p>Both Okasaki's and Hood &amp; Melville's queues require purely functional stacks as building blocks, and both produce purely functional queues. If <code>push</code> and <code>pop</code> are destructive, can global rebuilding be used to simulate an ephemeral queue with 6 ephemeral stacks? Fewer?</p>

<ds.data-structures>
How many ephemeral stacks are required to simulate a queue in worst-case $O(1)$ time?
jbapple
# How many ephemeral stacks are required to simulate a queue in worst-case $O(1)$ time?

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

In "[Real Time Queue Operations in Pure LISP](http://ecommons.cornell.edu/handle/1813/6273)" ([ML implementation](https://web.archive.org/web/20100626050951/http://www.eecs.usma.edu/webs/people/okasaki/jfp95/queue.hm.sml)), Hood and Melville show an $O(1)$ worst-case simulation of a queue using 6 stacks and global rebuilding. Can a real-time queue be simulated with fewer stacks?

In "[Simple and Efficient Purely Functional Queues and Deques](https://web.archive.org/web/20120207055242/http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html)", Okasaki shows an implementation using one stack and two lazy stacks.

Both Okasaki's and Hood & Melville's queues require purely functional stacks as building blocks, and both produce purely functional queues. If `push` and `pop` are destructive, can global rebuilding be used to simulate an ephemeral queue with 6 ephemeral stacks? Fewer?

**Tags:** ds.data-structures


---

## 1 answers

### Answer by username_1 on 2011-04-05. Score: 3

Not sure I fully understand your question, but it seems related to [Problem 1.3.49](http://books.google.com/books?id=idUdqdDXqnAC&lpg=PP1&dq=%22Algorithms%22%20Robert%20Sedgewick%20and%20Kevin%20Wayne&pg=PA171#v=onepage&q=1.3.49&f=false) from Sedgewicks Algorithm book.

> **Comments:**
> **username_2**: That problem has an interesting story. See the discussion at http://stackoverflow.com/questions/5538192/how-to-implement-a-queue-with-three-stacks, which eventually leads to a change in the problem statement at http://algs4.cs.princeton.edu/13stacks/. (Originally the problem was about worst-case queue with 3 stacks, now 3 has been changed to "a constant number of".)  

---

