How to implement a queue with three stacks?

Ok, this is really hard, and the only solution I could come up with, remembers me of Kirks solution to the Kobayashi Maru test (somehow cheated): The idea, is that we use stack of stacks (and use this to model a list). I call the operations en/dequeue and push and pop, then we get:

queue.new() : Stack1 = Stack.new(<Stack>);  
              Stack2 = Stack1;  

enqueue(element): Stack3 = Stack.new(<TypeOf(element)>); 
                  Stack3.push(element); 
                  Stack2.push(Stack3);
                  Stack3 = Stack.new(<Stack>);
                  Stack2.push(Stack3);
                  Stack2 = Stack3;                       

dequeue(): Stack3 = Stack1.pop(); 
           Stack1 = Stack1.pop();
           dequeue() = Stack1.pop()
           Stack1 = Stack3;

isEmtpy(): Stack1.isEmpty();

(StackX = StackY is no copying of the contents, just a copy of reference. Its just to describe it easy. You could also use an array of 3 stacks and access them via index, there you would just change the value of the index variable). Everything is in O(1) in stack-operation-terms.

And yes I know its argueable, because we have implicit more than 3 stacks, but maybe it give others of you good ideas.

EDIT: Explanation example:

 | | | |3| | | |
 | | | |_| | | |
 | | |_____| | |
 | |         | |
 | |   |2|   | |
 | |   |_|   | |
 | |_________| |
 |             |
 |     |1|     |
 |     |_|     |
 |_____________|

I tried here with a little ASCII-art to show Stack1.

Every element is wrapped in a single element stack (so we have only typesafe stack of stacks).

You see to remove we first pop the first element (the stack containing here element 1 and 2). Then pop the next element and unwrap there the 1. Afterwards we say that the first poped stack is now our new Stack1. To speak a little more functional - these are lists implement by stacks of 2 elements where the top element ist cdr and the first/below top element is car. The other 2 are helping stacks.

Esp tricky is the inserting, as you have somehow have to dive deep into the nested stacks to add another element. Thats why Stack2 is there. Stack2 is always the innermost stack. Adding is then just pushing an element in and then pushing ontop a new Stack2 (and thats why we are not allowed to touch Stack2 in our dequeue operation).


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

Tags:

Algorithm

Data Structures

Recent Posts