algorithm - How to implement a queue with three stacks?

Question

I came across this question in an algorithms book (Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne).

Queue with three stacks. Implement a queue with three stacks so that each queue operation takes a constant (worst-case) number of stack operations. Warning : high degree of difficulty.

I know how to make a queue with 2 stacks but I can't find the solution with 3 stacks. Any idea ?

(oh and, this is not homework :) )

Answer 1

SUMMARY

• O(1) algorithm is known for 6 stacks
• O(1) algorithm is known for 3 stacks, but using lazy evaluation which in practice corresponds to having extra internal data structures, so it does not constitute a solution
• People near Sedgewick have confirmed they are not aware of a 3-stack solution within all the constraints of the original question

DETAILS

There are two implementations behind this link: http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html

One of them is O(1) with three stacks BUT it uses lazy execution, which in practice creates extra intermediate data structures (closures).

Another of them is O(1) but uses SIX stacks. However, it works without lazy execution.

UPDATE: Okasaki's paper is here: http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps and it seems that he actually uses only 2 stacks for the O(1) version that has lazy evaluation. The problem is that it's really based on lazy evaluation. The question is if it can be translated to a 3-stack algorithm without lazy evaluation.

UPDATE: Another related algorithm is described in paper "Stacks versus Deques" by Holger Petersen, published in 7th Annual Conference on Computing and Combinatorics. You can find the article from Google Books. Check pages 225-226. But the algorithm is not actually real-time simulation, it's linear-time simulation of a double-ended queue on three stacks.

gusbro: "As @Leonel said some days ago, I thought it would be fair to check with Prof. Sedgewick if he knew a solution or there was some mistake. So I did write to him. I just received a response (albeit not from himself but from a colleague at Princeton) so I like to share with all of you.He basically said that he knew of no algorithms using three stacks AND the other constraints imposed (like not using lazy evaluation). He did know of an algorithm using 6 stacks as we already know looking at the answers here. So I guess the question is still open to find an algorithm (or prove one cannot be found)."