How to implement a queue with three stacks?

Question

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

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

I am going to attempt a proof to show that it can't be done.

---

Suppose there is a queue Q that is simulated by 3 stacks, A, B and C.

Assertions

• ASRT0 := Furthermore, assume that Q can simulate operations {queue,dequeue} in O(1). This means that there exists a specific sequence of stack push/pops for every queue/dequeue operation to be simulated.

• Without loss of generality, assume the queue operations are deterministic.

Let the elements queued into Q be numbered 1, 2, ..., based on their order of queue, with the first element that is queued into Q being defined as 1, the second one as 2, and so on.

Define

• Q(0) := The state of Q when there are 0 elements in Q (and thus 0 elements in A, B and C)
• Q(1) := The state of Q (and A, B and C) after 1 queue operation on Q(0)
• Q(n) := The state of Q (and A, B and C) after n queue operations on Q(0)

Define

• |Q(n)| := the number of elements in Q(n) (therefore |Q(n)| = n)
• A(n) := the state of the stack A when the state of Q is Q(n)
• |A(n)| := the number of elements in A(n)

And similar definitions for stacks B and C.

Trivially,

|Q(n)| = |A(n)| + |B(n)| + |C(n)|

---

|Q(n)| is obviously unbounded on n.

Therefore, at least one of |A(n)|, |B(n)| or |C(n)| is unbounded on n.

WLOG1, suppose stack A is unbounded and stacks B and C are bounded.

Define * B_u := an upper bound of B * C_u := an upper bound of C * K := B_u + C_u + 1

WLOG2, for an n such that |A(n)| > K, select K elements from Q(n). Suppose that 1 of those elements is in A(n + x), for all x >= 0, i.e. the element is always in stack A no matter how many queue operations are done.

• X := that element

Then we can define

• Abv(n) := the number of items in stack A(n) that is above X

• Blo(n) := the number of elements in stack A(n) that is below X

  |A(n)| = Abv(n) + Blo(n)

ASRT1 := The number of pops required to dequeue X from Q(n) is at least Abv(n)

From (ASRT0) and (ASRT1), ASRT2 := Abv(n) must be bounded.

If Abv(n) is unbounded, then if 20 dequeues are required to dequeue X from Q(n), it will require at least Abv(n)/20 pops. Which is unbounded. 20 can be any constant.

Therefore,

ASRT3 := Blo(n) = |A(n)| - Abv(n)

must be unbounded.

---

WLOG3, we can select the K elements from the bottom of A(n), and one of them is in A(n + x) for all x >= 0

X(n) := that element, for any given n

ASRT4 := Abv(n) >= |A(n)| - K

Whenever an element is queued into Q(n)...

WLOG4, suppose B and C are already filled to their upper bounds. Suppose that the upper bound for elements above X(n) has been reached. Then, a new element enters A.

WLOG5, suppose that as a result, the new element must enter below X(n).

ASRT5 := The number of pops required to put an element below X(n) >= Abv(X(n))

From (ASRT4), Abv(n) is unbounded on n.

Therefore, the number of pops required to put an element below X(n) is unbounded.

---

This contradicts ASRT1, therefore, it is not possible to simulate an O(1) queue with 3 stacks.

---

I.e.

At least 1 stack must be unbounded.

For an element that stays in that stack, the number of elements above it must be bounded, or the dequeue operation to remove that element will be unbounded.

However, if the number of elements above it is bounded, then it will reach a limit. At some point, a new element must enter below it.

Since we can always choose the old element from among one of the lowest few elements of that stack, there can be an unbounded number of elements above it (based on the unbounded size of the unbounded stack).

To enter a new element below it, since there's an unbounded number of elements above it, an unbounded number of pops is required to put the new element below it.

And thus the contradiction.

---

There are 5 WLOG (Without loss of generality) statements. In some sense, they can be intuitively understood to be true (but given that they are 5, it might take some time). The formal proof that no generality is lost can be derived, but is extremely lengthy. They're omitted.

I do admit that such omission might leave the WLOG statements in question. With a programmer's paranoia for bugs, please do verify the WLOG statements if you like to.

The third stack is also irrelevant. What matters is that there's a set of bounded stacks, and a set of unbounded stacks. The minimum needed for an example is 2 stacks. The number of stacks must be, of course, finite.

Lastly, if I am right that there's no proof, then there should be an easier inductive proof available. Probably based on what happens after every queue (keep track of how it affects the worst case of dequeue given the set of all elements in the queue).

Note: This is meant to be a comment to the functional implementation of real-time ( constant time worst case ) queues with singly-linked-lists. I can't add comments due to reputation, but it'll be nice if someone could change this to a comment appended to the answer by antti.huima. Then again, it is somewhat long for a comment.

@antti.huima: Linked lists are not the same as a stack.

• s1 = (1 2 3 4) --- a linked list with 4 nodes, each pointing to the one on the right, and holding values 1, 2, 3 and 4

• s2 = popped(s1) --- s2 is now (2 3 4)

At this point, s2 is equivalent to popped(s1), which behaves like a stack. However, s1 is still available for reference!

• s3 = popped(popped(s1)) --- s3 is (3 4)

We can still peek into s1 to get 1, whereas in a proper stack implementation, element 1 is gone from s1!

What does this mean?

• s1 is the reference to the top of the stack
• s2 is the reference to the second element of the stack
• s3 is the reference to the third ...

The additional linked-lists created now each serves as a reference/pointer! A finite number of stacks can't do that.

From what I see in the papers/code, the algorithms all make use of this property of linked-lists to retain references.

Edit: I'm referring only to the 2 and 3 linked-list algorithms make use of this property of linked-lists, as I read them first (they looked simpler). This is not meant to show that they are or are not applicable, just to explain that linked-lists aren't necessarily identical. I'll read the one with 6 when I'm free. @Welbog: Thanks for the correction.

---

Laziness can also simulate pointer-functionality in similar ways.

---

Using linked-list solves a different problem. This strategy can be used to implement real-time queues in Lisp (Or at least Lisps that insist on building everything from linked-lists): Refer to "Real Time Queue Operations in Pure Lisp" (linked to through antti.huima's links). It's also a nice way to design immutable lists with O(1) operation time and shared (immutable) structures.