One Stack, Two Queues

background

Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no satisfactory result came up. I remember the course TA insisted on something he couldn't prove, and said he forgot the proof, and ... [you know what].

Today, I recalled the problem. I was still eager to know, so here it is...

The Question

Is it possible to implement a stack using two queues, so that both PUSH and POP operations run in amortized time O(1)? If yes, could you tell me how?

Note: The situation is quite easy if we want to implement a queue with two stacks (with corresponding operations ENQUEUE & DEQUEUE). Please observe the difference.

PS: The above problem is not the homework itself. The homework did not require any lower bounds; just an implementation and the running time analysis.

• I guess that you can only use a limited amount of space other than the two queues (O(1) or O(log n)). Sounds impossible to me, because we do not have any way to reverse the order of a long input stream. But of course this is no proof unless it can be made into a rigorous claim…. Commented Oct 30, 2010 at 12:32
• @Tsuyoshi: You're right about the limited space assumption. And yes, that was what I said to that (stubborn) TA, but he refused :( Commented Oct 30, 2010 at 13:22
• @Tsuyoshi: I don't think you need to assume a bound on space in general, you only need to assume that you are not allowed to store the objects pushed and poped from the stack in any place other than the two queues (and probably a constant number of variables). Commented Oct 31, 2010 at 8:58
• @SadeqDousti In my opinion, the only way this would be possible is if you used a linked-list implementation of a queue and used some pointers to always point to the top of the "stack" Commented Oct 16, 2013 at 0:23
• It sounds like the TA might have actually have wanted to say "Implement a queue using two stacks" which is indeed possible precisely in "O(1) amortized time". Commented Nov 15, 2013 at 14:45

I don't have an actual answer, but here's some evidence that the problem is open:

• It's not mentioned in Ming Li, Luc Longpré and Paul M. B. Vitányi, "The power of the queue", Structures 1986, which considers several other closely related simulations

• It's not mentioned in Martin Hühne, "On the power of several queues", Theor. Comp. Sci. 1993, a follow-on paper.

• It's not mentioned in Holger Petersen, "Stacks versus Deques", COCOON 2001.

• Burton Rosenberg, "Fast nondeterministic recognition of context-free languages using two queues", Inform. Proc. Lett. 1998, gives an O(n log n) two-queue algorithm for recognizing any CFL using two queues. But a nondeterministic pushdown automaton can recognize CFLs in linear time. So if there were a simulation of a stack with two queues faster than O(log n) per operation, Rosenberg and his referees should have known about it.

• +1 for excellent references. There's some technicalities, though: Some of the papers, like the first one, do not consider the problem of simulating one stack using two queues (as much as I can say from the abstract). Others consider the worst-case analysis, not amortized cost. Commented Oct 30, 2010 at 15:40

Following some comments on my previous answer, it became clear to me that I was more or less cheating: I used extra space ($O(\sqrt{n})$ extra space in the second algorithm) during the execution of my Pop method.

The following algorithm does not use any additional space between methods and only $O(1)$ extra space during the execution of Push and Pop. Push has a $O(\sqrt{n})$ amortized running time and Pop has a $O(1)$ worst case (and amortized) running time.

Note to moderators: I'm not entirely sure if my decision to make this a separate answer is a correct one. I thought I shouldn't delete my original answer since it might still be of some relevance to the question.

The algorithm

We have two queues: queue $first$ and queue $second$. $first$ will be our 'cache', while $second$ will be our main 'storage'. Both queues will always be in 'stack order'. $first$ will contain the elements at the top of the stack and $second$ will contain the elements at the bottom of the stack. The size of $first$ will always be at most the square root of $second$.

• Push is done by 'inserting' the parameter at the start of the queue as follows: we enqueue the parameter to $first$, and then dequeue and re-enqueue all other elements in $first$. This way, the parameter ends up at the start of $first$.
• If $first$ becomes larger than the square root of $second$, we enqueue all elements of $second$ onto $first$ one by one and then swap $first$ and $second$. This way, the elements of $first$ (the top of the stack) end up at the head of $second$.
• Pop is done by dequeueing $first$ and returning the result if $first$ is not empty, and otherwise by dequeueing $second$ and returning the result.

C# code for the first algorithm

This code should be quite readable, even if you've never seen C# before. If you don't know what generics are, just replace all instances of 'T' by 'string' in your mind, for a stack of strings.

public class Stack<T> {
private Queue<T> first = new Queue<T>();
private Queue<T> second = new Queue<T>();
public void Push(T value) {
// I'll explain what's happening in these comments. Assume we pushed
// integers onto the stack in increasing order: ie, we pushed 1 first,
// then 2, then 3 and so on.

// Suppose our queues look like this:
// first: in 5 6 out
// second: in 1 2 3 4 out
// Note they are both in stack order and first contains the top of
// the stack.

// Suppose value == 7:
first.Enqueue(value);
// first: in 7 5 6 out
// second: in 1 2 3 4 out

// We restore the stack order in first:
for (int i = 0; i < first.Count - 1; i++)
first.Enqueue(first.Dequeue());
// first.Enqueue(first.Dequeue()); is executed twice for this example, the
// following happens:
// first: in 6 7 5 out
// second: in 1 2 3 4 out
// first: in 5 6 7 out
// second: in 1 2 3 4 out

// first exeeded its capacity, so we merge first and second.
if (first.Count * first.Count > second.Count) {
while (second.Count > 0)
first.Enqueue(second.Dequeue());
// first: in 4 5 6 7 out
// second: in 1 2 3 out
// first: in 3 4 5 6 7 out
// second: in 1 2 out
// first: in 2 3 4 5 6 7 out
// second: in 1 out
// first: in 1 2 3 4 5 6 7 out
// second: in out

Queue<T> temp = first; first = second; second = temp;
// first: in out
// second: in 1 2 3 4 5 6 7 out
}
}
public T Pop() {
if (first.Count == 0) {
if (second.Count > 0)
return second.Dequeue();
else
throw new InvalidOperationException("Empty stack.");
} else
return first.Dequeue();
}
}

Analysis

Obviously Pop works in $O(1)$ time in the worst case.

Push works in $O(\sqrt{n})$ amortized time. There are two cases: if $|first| < \sqrt{|second|}$ then Push takes $O(\sqrt{n})$ time. If $|first| \geq \sqrt{|second|}$ then Push takes $O(n)$ time, but after this operation $first$ will be empty. It will take $O(\sqrt{n})$ time before we get this case again, so the amortized time is $O(\frac{n}{\sqrt{n}}) = O(\sqrt{n})$ time.

• about deleting an answer, please take a look at meta.cstheory.stackexchange.com/q/386/873. Commented Nov 1, 2010 at 9:10
• I can't understand the line first.Enqueue(first.Dequeue()). Have you mistyped something? Commented Nov 1, 2010 at 9:13
• Thanks for the link, I updated my original answer accordingly. Secondly, I've added a lot of comments to my code describing what is going on during the execution of my algorithm, I hope it clears up any confusion. Commented Nov 1, 2010 at 12:57
• for me the algorithm was more readable and easier to understand before the edit. Commented Nov 1, 2010 at 13:05

The answer below is 'cheating', in that while it doesn't use any space between operations the operations themselves can use more than $O(1)$ space. See elsewhere in this thread for an answer that doesn't have this problem.

While I don't have an answer to your exact question, I did find an algorithm that works in $O(\sqrt{n})$ time instead of $O(n)$. I believe this is tight, though I don't have a proof. If anything, the algorithm shows that trying to prove a lower bound of $O(n)$ is futile, so it might help in answering your question.

I present two algorithms, the first being a simple algorithm with a $O(n)$ running time for Pop and the second with a $O(\sqrt{n})$ running time for Pop. I describe the first one mainly because of its simplicity so that the second one is easier to understand.

To be give more details: the first uses no additional space, has an $O(1)$ worst case (and amortized) Push and an $O(n)$ worst case (and amortized) Pop, but the worst case behaviour is not always triggered. Since it doesn't use any additional space beyond the two queues, it's slightly 'better' than the solution offered by Ross Snider.

The second uses a single integer field (so $O(1)$ extra space), has a $O(1)$ worst case (and amortized) Push and a $O(\sqrt{n})$ amortized Pop. It's running time is therefore significantly better than that of the 'simple' approach, yet it does use some extra space.

The first algorithm

We have two queues: queue $first$ and queue $second$. $first$ will be our 'push queue', while $second$ will be the queue already in 'stack order'.

• Pushing is done by simply enqueueing the parameter onto $first$.
• Popping is done as follows. If $first$ is empty, we simply dequeue $second$ and return the result. Otherwise, we reverse $first$, append all of $second$ to $first$ and swap $first$ and $second$. We then dequeue $second$ and return the result of the dequeue.

C# code for the first algorithm

This could should be quite readable, even if you've never seen C# before. If you don't know what generics are, just replace all instances of 'T' by 'string' in your mind, for a stack of strings.

public class Stack<T> {
private Queue<T> first = new Queue<T>();
private Queue<T> second = new Queue<T>();
public void Push(T value) {
first.Enqueue(value);
}
public T Pop() {
if (first.Count == 0) {
if (second.Count > 0)
return second.Dequeue();
else
throw new InvalidOperationException("Empty stack.");
} else {
int nrOfItemsInFirst = first.Count;
T[] reverser = new T[nrOfItemsInFirst];

// Reverse first
for (int i = 0; i < nrOfItemsInFirst; i++)
reverser[i] = first.Dequeue();
for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
first.Enqueue(reverser[i]);

// Append second to first
while (second.Count > 0)
first.Enqueue(second.Dequeue());

// Swap first and second
Queue<T> temp = first; first = second; second = temp;

return second.Dequeue();
}
}
}

Analysis

Obviously Push works in $O(1)$ time. Pop may touch everything inside $first$ and $second$ a constant amount of times, so we have $O(n)$ in the worst case. The algorithm exhibits this behaviour (for instance) if one pushes $n$ elements onto the stack and then repeatedly performs a singe Push and a single Pop operation in succession.

The second algorithm

We have two queues: queue $first$ and queue $second$. $first$ will be our 'push queue', while $second$ will be the queue already in 'stack order'.

This is an adapted version of the first algorithm, in which we don't immediately 'shuffle' the contents of $first$ into $second$. Instead, if $first$ contains a sufficiently small number of elements compared to $second$ (namely the square root of the number of elements in $second$), we only reorganise $first$ into stack order and don't merge it with $second$.

• Pushing is still done by simply enqueueing the parameter onto $first$.
• Popping is done as follows. If $first$ is empty, we simply dequeue $second$ and return the result. Otherwise, we reorganising the contents of $first$ so that they are in stack order. If $|first| < \sqrt{|second|}$ we simply dequeue $first$ and return the result. Otherwise, we append $second$ onto $first$, swap $first$ and $second$, dequeue $second$ and return the result.

C# code for the first algorithm

This could should be quite readable, even if you've never seen C# before. If you don't know what generics are, just replace all instances of 'T' by 'string' in your mind, for a stack of strings.

public class Stack<T> {
private Queue<T> first = new Queue<T>();
private Queue<T> second = new Queue<T>();
int unsortedPart = 0;
public void Push(T value) {
unsortedPart++;
first.Enqueue(value);
}
public T Pop() {
if (first.Count == 0) {
if (second.Count > 0)
return second.Dequeue();
else
throw new InvalidOperationException("Empty stack.");
} else {
int nrOfItemsInFirst = first.Count;
T[] reverser = new T[nrOfItemsInFirst];

for (int i = nrOfItemsInFirst - unsortedPart - 1; i >= 0; i--)
reverser[i] = first.Dequeue();

for (int i = nrOfItemsInFirst - unsortedPart; i < nrOfItemsInFirst; i++)
reverser[i] = first.Dequeue();

for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
first.Enqueue(reverser[i]);

unsortedPart = 0;
if (first.Count * first.Count < second.Count)
return first.Dequeue();
else {
while (second.Count > 0)
first.Enqueue(second.Dequeue());

Queue<T> temp = first; first = second; second = temp;

return second.Dequeue();
}
}
}
}

Analysis

Obviously Push works in $O(1)$ time.

Pop works in $O(\sqrt{n})$ amortized time. There are two cases: if $|first| < \sqrt{|second|}$, then we shuffle $first$ into stack order in $O(|first|) = O(\sqrt{n})$ time. If $|first| \geq \sqrt{|second|}$, then we must have had at least $\sqrt{n}$ calls for Push. Hence, we can only hit this case every $\sqrt{n}$ calls to Push and Pop. The actual running time for this case is $O(n)$, so the amortized time is $O(\frac{n}{\sqrt{n}}) = O(\sqrt{n})$.

Final note

It it is possible to eliminate the extra variable at the cost of making Pop an $O(\sqrt{n})$ operation, by having Pop reorganise $first$ at every call instead of having Push do all the work.

• I edited the first paragraphs so my answer is formulated as an actual answer to the question. Commented Oct 31, 2010 at 1:41
• You are using an array (reverser) for reversing! I don't think you are allowed to do this. Commented Oct 31, 2010 at 8:51
• True, I use extra space while executing the methods, but I thought that would be allowed: if you want to implement a queue using two stacks in the straightforward way, you have to reverse one of the stacks at one point, and as far as I know you need extra space to do that, so since this question is similar I figured using extra space during the execution of a method would be allowed, as long as you don't use additional space between method calls. Commented Oct 31, 2010 at 12:48
• "if you want to implement a queue using two stacks in the straightforward way, you have to reverse one of the stacks at one point, and as far as I know you need extra space to do that" --- You don't. There's a way to get the amortized cost of Enqueue to be 3 and the amortized cost of Dequeue to be 1 (ie both O(1)) with one memory cell and two stacks. The hard part is really the proof, not the design of the algorithm. Commented Oct 31, 2010 at 13:30
• After thinking about it some more, I realise I am indeed cheating and my previous comment is indeed wrong. I've found a way to rectify it: I thought up two algorithms with the same running times as the above two (though Push is now the operation taking long and Pop is now done in constant time) without using extra space at all. I'll post a new answer once I've written all of it down. Commented Oct 31, 2010 at 14:01

I claim we have $\Theta(\sqrt{N})$ amortized cost per operation. Alex's algorithm gives the upper bound. To prove the lower bound I give a worst-case sequence of PUSH and POP moves.

The worst case sequence consists of $N$ PUSH operations, followed by $\sqrt{N}$ PUSH operations and $\sqrt{N}$ POP operations, again followed by $\sqrt{N}$ PUSH operations and $\sqrt{N}$ POP operations, etc. That is:

$PUSH^N (PUSH^{\sqrt{N}} POP^{\sqrt{N}})^{\sqrt{N}}$

Consider the situation after the initial $N$ PUSH operations. No matter how the algorithm works, at least one of the queues must have at least $N/2$ entries in it.

Now consider the task of dealing with the (first set of) $\sqrt{N}$ PUSH and POP operations. Any algorithmic tactic whatsoever must fall into one of two cases:

In the first case, the algorithm will use both queues. The larger of these queues has at least $N/2$ entries in it, so we must incur a cost of at least $N/2$ queue operations in order to eventually retrieve even a single element we ENQUEUE and later need to DEQUEUE from this larger queue.

In the second case, the algorithm does not use both queues. This reduces the problem to simulating a stack with a single queue. Even if this queue is initially empty, we can't do better than using the queue as a circular list with sequential access, and it appears straightforward that we must use at least $\sqrt{N}/2$ queue operations on average for each of the $2\sqrt{N}$ stack operations.

In both cases, we required at least $N/2$ time (queue operations) in order to handle $2\sqrt{N}$ stack operations. Because we can repeat this process $\sqrt{N}$ times, we need $N\sqrt{N}/2$ time to process $3N$ stack operations in total, giving a lower bound of $\Omega(\sqrt{N})$ amortized time per operation.

• Jack edited this so the number of rounds (exponent on the parentheses) is $\sqrt{N}$ instead of $\infty$ as I had it. This is because what I had before to show you couldn't amortize over the whole sequence was "overkill", and you can see it from just the $\sqrt{N}$ iterations. Thanks, Jack! Commented Mar 29, 2011 at 14:59
• What about the mix of these two cases? For example, we push the $\sqrt{n}$ entries alternatively into $Q_1$ (the one with at least $^N/_2$ entries) and $Q_2$ (the other queue)? I guess this pattern costs more, but how to argue about it? And in the second case, I think the average (amortized) cost for each of the $2 \sqrt{n}$ stack operations is at least $\frac{\sqrt{n}}{4}: \frac{1+2+ \ldots + \sqrt{n} + \sqrt{n}}{2\sqrt{n}}$. Commented Nov 10, 2013 at 3:30
– Joe
Commented Mar 1, 2014 at 0:18
• @Joe I do not think Peter's answer contradicts this lower bound since the first N pushes are never popped in this sequence. Any shuffling procedure will require at least O(N) time, so if it must take place each phase'' (sequence of $PUSH^{\sqrt{N}}POP^{\sqrt{N}}$ operations) we still have amortized $O(\sqrt{N})$ for the phase. In particular such an algorithm falls under the "first case" in my analysis. Commented Jul 26, 2014 at 16:31
• @hengxin Your comment made me realize I hadn't expressed my argument as clearly as I would have liked. I've edited it so now it should be clear the pattern you propose is covered under the first case. The argument is that if we ENQUEUE even a single element into the larger queue in case one, we must require $O(N)$ operations to ultimately retrieve it. Commented Jul 26, 2014 at 16:33

You can get a $O(\lg n)$ (amortized) slowdown if, after many $push$es and no $pop$s, when you see a $pop$ you perform a sequence of perfect shuffles using the two queues. It was proven by Diaconis, Graham and Cantor in "The Mathematics of Perfect Shuffles" in 1983 that with $O(\lg n)$ perfect shuffles one can reorder the "deck" into any order. Therefore, you could maintain one queue as the "input queue" and one queue as the "output queue" (similar to the two stacks case) and then when a $pop$ is requested and the output queue is empty, you perform a sequence of perfect shuffles to reverse the input queue and store it in the output queue.

The only remaining question is whether the particular pattern of perfect shuffles required is regular enough to not require more than $O(1)$ memory.

As far as I know, this is a new idea...

• Commented Apr 30, 2011 at 18:29
• Argh! I should have looked for an updated or related question. The papers you linked to in your earlier answer posited a relation between k stacks and k+1 stacks. Does this trick end up putting the power of k queues between k and k+1 stacks? If so, that's kind of a neat sidenote. Either way, thanks for linking me to your answer so I didn't waste too much time writing this up for another venue. Commented Apr 30, 2011 at 21:27

Without using extra space, maybe using a prioritized queue and forcing each new push to give it a bigger priority than the previous one? Still wouldn't be O(1) though.

I can't get the queues to implement a stack in amortized constant time. However, I can think of a way to get two queues to implement a stack in worst case linear time.

• Using one external bit of data, keep a record of which queue was used last, the left queue $A$ or the right queue $B$.
• Each time there is a push operation, flip the bit and insert the element in the queue the bit now demarcates. Pop everything from the other queue and push it onto the current queue.
• A pop operation takes off the front of the current queue and does not touch the external state bit.

Of course, we can add another bit of external state which tells us whether the last operation was a push or a pop. We can delay moving everything from one queue onto the other until we get two push operations in a row. This also makes the pop operation slightly more complicated. This gives us O(1) amortized complexity for the pop operation. Unfortunately push remains linear.

All of this works because each time a push operation is done, the new element is put at the head of an empty queue and the full queue is added to the tail end of it, effectively reversing the elements.

If you want to get amortized constant time operations, you'll probably have to do something more clever.

• Surely, I can use a single queue with the same worse case time complexity and without the complication, essentially treating the queue as a circular list with an additional queue element representing the top of the stack. Commented Oct 30, 2010 at 16:06
• Looks like you can! However, it looks like more than one classical queue is necessary to simulate a stack in this way. Commented Oct 30, 2010 at 17:40

There is a trivial solution, if your queue allows front-loading, that only requires one queue (or, more specifically, deque.) Perhaps this is the type of queue the course TA in the original question had in mind?

This algorithm requires two queues and two pointers, we'll call them Q1, Q2, primary, and secondary, respectively. Upon initilization Q1 and Q2 are empty, primary points to Q1 and secondary points to Q2.

The PUSH operation is trivial, it consists of merely:

*primary.enqueue(value);

The POP operation is slightly more involved; it requires spooling all but the last item of the primary queue onto the secondary queue, swapping the pointers, and returning the last remaining item from the original queue:

while(*primary.size() > 1)
{
*secondary.enqueue(*primary.dequeue());
}

swap(primary, secondary);
return(*secondary.dequeue());

No bounds checking is done, and it's not O(1).

As I'm typing this I see that this could be done with a single queue using a for loop in place of a while loop, like Alex has done. Either way, the PUSH operation is O(1) and the POP operation becomes O(n).

Here is another solution using two queues and one pointer, called Q1, Q2, and queue_p, respectively:

Upon initialization, Q1 and Q2 are empty and queue_p points to Q1.

Again, the PUSH operation is trivial, but does require one additional step of pointing queue_p at the other queue:

*queue_p.enqueue(value);
queue_p = (queue_p == &Q1) ? &Q2 : &Q1;

The POP operation operation is similar to before, but now there are n/2 items that need to be rotated through the queue:

queue_p = (queue_p == &Q1) ? &Q2 : &Q1;
for(i=0, i<(*queue_p.size()-1, i++)
{
*queue_p.enqueue(*queue_p.dequeue());
}
return(*queue_p.dequeue());

The PUSH operation is still O(1), but now the POP operation is O(n/2).

Personally, for this problem, I prefer the idea of implementing a single, double-ended queue (deque) and calling it a stack when we want to.

• Your second algorithm is helpful to understand the more involved one of Alex. Commented Nov 8, 2013 at 2:22

Optimal simulation of a stack with $k$ queues takes $Θ(n^{1/k})$ time per operation regardless of whether:
- the time is worst-case or amortized,
- we simulate one stack or any fixed number of stacks with $k$ queues total,
- $n$ is the number of operations or maximum total simultaneous number of items,
- push (but not pop) is required to be $O(1)$ or not.

In one direction (i.e. upper bound), the $i$th queue will have size $Θ(n^{i/k})$, and together with lower-numbered queues, will have the most recent $Θ(n^{i/k})$ items per stack (except if a stack has fewer elements; also items are only moved and not copied). We maintain this constraint by moving items between the queues, doing the moves in bulk so as to achieve $O(1)$ time per item moved to queue $i+1$ and $O(n^{1/k})$ to queue $i-1$. Each item is annotated by the identity of its stack and its height within the stack; this is not needed if we allow push to be $Θ(n^{1/k})$ (or if we have just one stack and allow amortized pop time).

In the other direction (i.e. lower bound), we can keep adding items until for some $m$, the $m$th most recent item is $Ω(mn^{1/k})$ items away from the end of each queue containing it, and then we request it and repeat. Suppose that this does not happen enough. Then, a new item must usually be added to a queue of size $o(n^{1/k})$. To keep this queue size, items must be moved with frequency $Ω(n^{1/k})$ to another queue, whose size must usually be $o(n^{2/k})$ to allow fast enough item retrieval after the move. By repeating this argument, we get $k$ queues with a total size of $o(n)$ (and growing), as required.

Also, if a stack must be emptied all at once (before we start adding items again), I expect the optimal amortized performance is $Θ(\log n)$ (one stack using two or more queues); this performance can be achieved using (essentially) merge sort.

A stack may be implemented using two queues by using the second queue as a b uffer. When items are pushed onto the stack they are added onto the end of the queue. Each time an item is popped, the n – 1 elements of the first queue must be moved to the second, while the remaining item is returned. public class QueueStack implemen ts IStack { private IQueue q1 = new Queue(); private IQueue q2 = new Queue(); public void push( E e ) { q1.enqueue( e ) // O ( 1 ) } public E pop( E e ) { while ( 1 < q1.size() ) // O ( n ) { q2.enqueue( q1.dequeue() ); } sw apQueues(); return q2.dequeue(); } p rivate void swapQueues() { IQueue Q = q2; q2 = q1; q1 = Q; } }

• Did you miss the part in the question about amortized time O(1)? Commented Jan 16, 2014 at 3:51