139

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

37
  • 30
    I guess it’s a Tower of Hanoi variant.
    – Gumbo
    Apr 4, 2011 at 12:22
  • 14
    @Jason: That question is not a duplicate, since it asks for O(1) amortized time while this one asks for O(1) worst-case for each operation. DuoSRX's two-stack solution is already O(1) amortized time per operation.
    – interjay
    Apr 4, 2011 at 14:22
  • 16
    The author sure wasn't kidding when he said "Warning : high degree of difficulty."
    – BoltClock
    Apr 5, 2011 at 2:06
  • 9
    @Gumbo unfortunately the time complexity of Tower of Hanoi is nowhere near constant time!
    – prusswan
    Apr 5, 2011 at 20:51
  • 12
    Note: The question in the text has been updated to this: Implement a queue with a constant number of stacks [not "3"] so that each queue operations takes a constant (worst-case) number of stack operations. Warning: high degree of difficulty. (algs4.cs.princeton.edu/13stacks - Section 1.3.43). It appears that Prof. Sedgewick has conceded the original challenge. Apr 11, 2011 at 15:46

5 Answers 5

44
+50

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

10
  • I just flew over the papers and programms in your link. But if I see right they do not use stacks, they use lists as basic type. And esp. in these lists are constructed with header and rest, so it basicly looks similar to my solution (and I think is not right).
    – flolo
    Apr 6, 2011 at 22:10
  • 1
    Hi, the implementations are in a functional language where lists correspond to stacks as long as pointers are not shared, and they are not; the six-stack version can be really implemented using six "plain" stacks. The problem with the two/three stacks version is that it uses hidden data structures (closures). Apr 6, 2011 at 22:20
  • Are you sure the six-stack solution doesn't share pointers? In rotate, it looks like the front list gets assigned to both oldfront and f, and these are then modified separately.
    – interjay
    Apr 6, 2011 at 22:56
  • 14
    The source material at algs4.cs.princeton.edu/13stacks has been changed: 43. Implement a queue with a constant number of [not "3"] stacks so that each queue operations takes a constant (worst-case) number of stack operations. Warning: high degree of difficulty. The title of the challenge still says "Queue with three stacks" however :-). Apr 11, 2011 at 15:48
  • 4
    @AnttiHuima The six-stacks link is dead, do you know if this exists somewhere? Dec 17, 2014 at 13:16
14

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

8
  • Would you care to explain how it works? Maybe trace out pushing 'A','B','C','D' and then popping 4 times?
    – MAK
    Apr 6, 2011 at 15:07
  • 1
    @Iceman: No Stack2 is right. They are not lost, because Stack always refers to the innermost stack in Stack1, so they are still implicit in Stack1.
    – flolo
    Apr 6, 2011 at 15:22
  • 3
    I agree that it's cheating :-). That's not 3 stacks, it's 3 stack references. But an enjoyable read. Apr 6, 2011 at 15:27
  • 1
    Its a clever scheme, but if I understand it correctly, it will end up needing n stacks when there are n elements pushed into the queue. The question asks for exactly 3 stacks.
    – MAK
    Apr 6, 2011 at 15:29
  • 2
    @MAK: I know, thats why explicitly stated that its cheated (I even spent reputation on a bounty because I am also curious for the real solution). But at least prusswan comment can be answered: The number of stacks is important, because my solution is indeed a valid, when you can use as much as you want.
    – flolo
    Apr 6, 2011 at 15:33
4

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

6
  • 2
    I think that proof works for those assumptions - but I'm not sure that all stacks have to be empty for the queue to be empty, or that the sum of the sizes of the stacks must equal the size of the queue.
    – Mikeb
    Apr 6, 2011 at 18:11
  • 3
    "WLOG1, suppose stack A is unbounded and stacks B and C are bounded." You can't assume that some of the stacks are bounded, as that would make them worthless (they would be the same as O(1) additional storage).
    – interjay
    Apr 6, 2011 at 18:20
  • 3
    Sometimes the trivial things are not that trivial: |Q| = |A|+|B|+|C| is only right, if you assume that for every entry in Q you add exact one into A, B or C, but it can be that theer is some algorithm, that always add an element two times to two stacks or even all three. And if it works this way, you WLOG1 does not hold any longer (e.g. imagine C a copy of A (not that it makes any sense, but maybe there is an algorithm, with a different order or whatever...)
    – flolo
    Apr 6, 2011 at 21:28
  • @flolo and @mikeb: Both of you are right. |Q(n)| should be defined as |A(n)|+|B(n)|+|C(n)|. And then |Q(n)| >= n. Subsequently, the proof would work with n, and note that as long as |Q(n)| larger, the conclusion applies. Apr 7, 2011 at 5:41
  • @interjay: You can have 3 unbounded stacks and no bounded stacks. Then instead of "B_u + C_u + 1", the proof can just use "1". Basically, the expression represents "sum of the upper bound in bounded stacks + 1", thus the number of bounded stacks wouldn't matter. Apr 7, 2011 at 5:45
3

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.

4
  • 1
    I can't speak to the other algorithms in antti's answer, but the six-stack constant-time solution (eecs.usma.edu/webs/people/okasaki/jfp95/queue.hm.sml) does not use this property of lists, as I have re-implemented it in Java using java.util.Stack objects. The only place where this feature is used is an optimization which allows immutable stacks to be "duplicated" in constant time, which base Java stacks cannot do (but which can be implemented in Java) since they are mutable structures.
    – Welbog
    Apr 8, 2011 at 16:46
  • If it's an optimization that doesn't reduce the computational complexity, it shouldn't affect the conclusion. Glad to finally have a solution, now to verify it: But I don't like reading SML. Mind sharing your java code? (: Apr 8, 2011 at 17:14
  • It's not a final solution as it uses six stacks instead of three, unfortunately. However, it might be possible to prove that six stacks is a minimal solution...
    – Welbog
    Apr 8, 2011 at 17:18
  • @Welbog! Can you share your 6-stack implementation? :) It would be cool to see it :) Apr 8, 2011 at 19:09
1

You can do it in amortized constant time with two stacks:

------------- --------------
            | |
------------- --------------

Adding is O(1) and removing is O(1) if the side you want to take from is not empty and O(n) otherwise (split the other stack in two).

The trick is to see that the O(n) operation will only be done every O(n) time (if you split, e.g. in halves). Hence, the average time for an operation is O(1)+O(n)/O(n) = O(1).

While this may seam like a problem, if you are using an imperative language with an array based stack (fastest), you are going to have only amortized constant time anyway.

1
  • As to the original question: Splitting a stack actually requires an extra intermediate stack. This might be why your task included three stacks. Dec 3, 2011 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.