<p>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.</p>

<p>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.</p>

<p>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.</p>

<p><strong>The algorithm</strong></p>

<p>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$.</p>

<ul>
<li>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$.</li>
<li>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$.</li>
<li>Pop is done by dequeueing $first$ and returning the result if $first$ is not empty, and otherwise by dequeueing $second$ and returning the result.</li>
</ul>

<p><strong>C# code for the first algorithm</strong></p>

<p>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.</p>

<pre><code>public class Stack&lt;T&gt; {
    private Queue&lt;T&gt; first = new Queue&lt;T&gt;();
    private Queue&lt;T&gt; second = new Queue&lt;T&gt;();
    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 &lt; 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 &gt; second.Count) {
            while (second.Count &gt; 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&lt;T&gt; 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 &gt; 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else
            return first.Dequeue();
    }
}
</code></pre>

<p><strong>Analysis</strong></p>

<p>Obviously Pop works in $O(1)$ time in the worst case.</p>

<p>Push works in $O(\sqrt{n})$ amortized time. There are two cases: if $|first| &lt; \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.</p>

CC BY-SA 2.5
2010-11-01T09:10:31.457Z
about deleting an answer, please take a look at http://meta.cstheory.stackexchange.com/q/386/873.
Sadeq Dousti
CC BY-SA 2.5
2010-11-01T09:13:56.567Z
I can't understand the line `first.Enqueue(first.Dequeue())`. Have you mistyped something?
Sadeq Dousti
CC BY-SA 2.5
2010-11-01T12:57:09.807Z
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.
Alex ten Brink
CC BY-SA 2.5
2010-11-01T13:05:49.380Z
for me the algorithm was more readable and easier to understand before the edit.
Kaveh
CC BY-SA 3.0
2010-10-31T14:34:51.483Z
2013-11-08T03:46:15.990Z
2013-11-08T03:46:15.990Z
Alex ten Brink
<p><em><strong>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.</em></strong></p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p><strong>The first algorithm</strong></p>

<p>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'.</p>

<ul>
<li>Pushing is done by simply enqueueing the parameter onto $first$.</li>
<li>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.</li>
</ul>

<p><strong>C# code for the first algorithm</strong></p>

<p>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.</p>

<pre><code>public class Stack&lt;T&gt; {
    private Queue&lt;T&gt; first = new Queue&lt;T&gt;();
    private Queue&lt;T&gt; second = new Queue&lt;T&gt;();
    public void Push(T value) {
        first.Enqueue(value);
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count &gt; 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 &lt; nrOfItemsInFirst; i++)
                reverser[i] = first.Dequeue();    
            for (int i = nrOfItemsInFirst - 1; i &gt;= 0; i--)
                first.Enqueue(reverser[i]);

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

            // Swap first and second
            Queue&lt;T&gt; temp = first; first = second; second = temp;

            return second.Dequeue();
        }
    }
}
</code></pre>

<p><strong>Analysis</strong></p>

<p>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.</p>

<p><strong>The second algorithm</strong></p>

<p>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'.</p>

<p>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$.</p>

<ul>
<li>Pushing is still done by simply enqueueing the parameter onto $first$.</li>
<li>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| &lt; \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.</li>
</ul>

<p><strong>C# code for the first algorithm</strong></p>

<p>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.</p>

<pre><code>public class Stack&lt;T&gt; {
    private Queue&lt;T&gt; first = new Queue&lt;T&gt;();
    private Queue&lt;T&gt; second = new Queue&lt;T&gt;();
    int unsortedPart = 0;
    public void Push(T value) {
        unsortedPart++;
        first.Enqueue(value);
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count &gt; 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 &gt;= 0; i--)
                reverser[i] = first.Dequeue();

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

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

            unsortedPart = 0;
            if (first.Count * first.Count &lt; second.Count)
                return first.Dequeue();
            else {
                while (second.Count &gt; 0)
                    first.Enqueue(second.Dequeue());

                Queue&lt;T&gt; temp = first; first = second; second = temp;

                return second.Dequeue();
            }
        }
    }
}
</code></pre>

<p><strong>Analysis</strong></p>

<p>Obviously Push works in $O(1)$ time.</p>

<p>Pop works in $O(\sqrt{n})$ amortized time. There are two cases: if $|first| &lt; \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})$.</p>

<p><strong>Final note</strong></p>

<p>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.</p>

CC BY-SA 3.0
2011-04-30T18:36:12.660Z
I think that you should look at the queues as if they were black-boxes with interface consisting of enqueue & dequeue only and only use constant amount of space (other then the queues).
Palmik
CC BY-SA 2.5
2010-10-31T01:41:01.947Z
I edited the first paragraphs so my answer is formulated as an actual answer to the question.
Alex ten Brink
CC BY-SA 2.5
2010-10-31T08:51:27.193Z
You are using an array (reverser) for reversing! I don't think you are allowed to do this.
Kaveh
CC BY-SA 2.5
2010-10-31T12:48:41.840Z
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.
Alex ten Brink
CC BY-SA 2.5
2010-10-31T13:30:10.523Z
"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.
Aaron Sterling
CC BY-SA 2.5
2010-10-31T14:01:42.883Z
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.
Alex ten Brink
CC BY-SA 2.5
2010-10-31T00:28:49.407Z
2010-11-01T12:44:22.423Z
2010-11-01T12:44:22.423Z
Alex ten Brink
<p>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.</p>

<p>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:</p>

<p>$ PUSH^N (PUSH^{\sqrt{N}} POP^{\sqrt{N}})^{\sqrt{N}} $</p>

<p>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.</p>

<p>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:</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-03-29T14:59:31.157Z
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!
Shaun Harker
CC BY-SA 3.0
2013-11-10T03:30:32.353Z
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}}$.
hengxin
CC BY-SA 3.0
2014-03-01T00:18:11.117Z
Apparently Peter's answer contradicts this lower bound?
Joe
CC BY-SA 3.0
2014-07-26T16:31:07.367Z
@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.
Shaun Harker
CC BY-SA 3.0
2014-07-26T16:33:45.207Z
@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.
Shaun Harker
CC BY-SA 3.0
2011-03-25T17:19:05.627Z
2014-07-26T16:22:59.843Z
2014-07-26T16:22:59.843Z
Shaun Harker
<p>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.</p>

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

<p>As far as I know, this is a new idea...</p>

CC BY-SA 3.0
2011-04-30T18:29:54.600Z
See http://cstheory.stackexchange.com/questions/4322/reversing-a-list-using-two-queues/4328
David Eppstein
CC BY-SA 3.0
2011-04-30T21:27:43.297Z
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.
Peter Boothe
CC BY-SA 3.0
2011-04-30T17:12:46.983Z
2011-04-30T17:12:46.983Z
Peter Boothe
<p>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. </p>

CC BY-SA 3.0
2011-09-07T23:27:19.013Z
2011-09-07T23:27:19.013Z
Alpha
<p>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.</p>

<ul>
<li>Using one external bit of data, keep a record of which queue was used last, the left queue $A$ or the right queue $B$.</li>
<li>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.</li>
<li>A pop operation takes off the front of the current queue and does not touch the external state bit.</li>
</ul>

<p>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.</p>

<p>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.</p>

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

CC BY-SA 2.5
2010-10-30T16:06:54.797Z
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.
Dave Clarke
CC BY-SA 2.5
2010-10-30T17:40:03.837Z
Looks like you can! However, it looks like more than one classical queue is necessary to simulate a stack in this way.
Ross Snider
CC BY-SA 2.5
2010-10-30T15:46:11.310Z
2010-10-30T15:46:11.310Z
Ross Snider
<p>Optimal simulation of a stack with $k$ queues takes $Θ(n^{1/k})$ time per operation regardless of whether:<br/>
- the time is worst-case or amortized,<br/>
- we simulate one stack or any fixed number of stacks with $k$ queues total,<br/>
- $n$ is the number of operations or maximum total simultaneous number of items,<br/>
- push (but not pop) is required to be $O(1)$ or not.</p>

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

<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2018-08-14T18:14:13.340Z
2018-08-14T18:14:13.340Z
Dmytro Taranovsky
<p>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?</p>

<p>Without allowing front loading, here is another solution:</p>

<p>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.</p>

<p>The PUSH operation is trivial, it consists of merely: </p>

<pre><code>*primary.enqueue(value);
</code></pre>

<p>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:</p>

<pre><code>while(*primary.size() &gt; 1)
{
    *secondary.enqueue(*primary.dequeue());
}

swap(primary, secondary);
return(*secondary.dequeue());
</code></pre>

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

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

<hr>

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

<p>Upon initialization, Q1 and Q2 are empty and queue_p points to Q1.</p>

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

<pre><code>*queue_p.enqueue(value);
queue_p = (queue_p == &amp;Q1) ? &amp;Q2 : &amp;Q1;
</code></pre>

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

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

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

<p>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.</p>

CC BY-SA 3.0
2013-11-08T02:22:18.717Z
Your second algorithm is helpful to understand the more involved one of Alex.
hengxin
CC BY-SA 2.5
2011-01-18T14:44:16.233Z
2011-01-18T14:44:16.233Z
oosterwal
<p>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 &lt; q1.size() )
// 
O
(
n
)
{
q2.enqueue( q1.dequeue() );
}
sw
apQueues();
return
q2.dequeue();
}
p
rivate
void swapQueues()
{
IQueue Q = q2;
q2 = q1;
q1 = Q;
}
}</p>

CC BY-SA 3.0
2014-01-16T03:51:04.910Z
Did you miss the part in the question about amortized time O(1)?
David Eppstein
CC BY-SA 3.0
2014-01-16T03:25:34.187Z
2014-01-16T03:25:34.187Z
Pradeepkumar
<p>I don't have an actual answer, but here's some evidence that the problem is open:</p>

<ul>
<li><p>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</p></li>
<li><p>It's not mentioned in Martin Hühne, "On the power of several queues", Theor. Comp. Sci. 1993, a follow-on paper.</p></li>
<li><p>It's not mentioned in Holger Petersen, "Stacks versus Deques", COCOON 2001.</p></li>
<li><p>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.</p></li>
</ul>

CC BY-SA 2.5
2010-10-30T15:40:39.977Z
+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.
Sadeq Dousti
CC BY-SA 2.5
2010-10-30T15:10:19.623Z
2010-10-30T15:10:19.623Z
David Eppstein
<h3>background</h3>

<p>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 <a href="http://groups.google.com/group/comp.theory/browse_thread/thread/bb34b65ca22641f8/b2b6ecb44bc3e912">comp.theory</a>, 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].</p>

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

<h3>The Question</h3>

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

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

<p>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.</p>

CC BY-SA 3.0
2013-10-16T00:23:18.607Z
@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"
Charles D Pantoga
CC BY-SA 3.0
2013-11-15T14:45:36.397Z
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".
Thomas Ahle
CC BY-SA 2.5
2010-10-30T12:32:50.143Z
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….
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-30T13:22:27.060Z
@Tsuyoshi: You're right about the limited space assumption. And yes, that was what I said to that (stubborn) TA, but he refused :(
Sadeq Dousti
CC BY-SA 2.5
2010-10-31T08:58:32.677Z
@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).
Kaveh
<ds.algorithms><ds.data-structures><open-problem><time-complexity>
One Stack, Two Queues
Sadeq Dousti
# One Stack, Two Queues

(Asked by: username_0 on 2010-10-30)

### 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](http://groups.google.com/group/comp.theory/browse_thread/thread/bb34b65ca22641f8/b2b6ecb44bc3e912), 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.

**Tags:** ds.algorithms, ds.data-structures, open-problem, time-complexity

> **Comments:**
> **username_3**: 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….  
> **username_0**: @Tsuyoshi: You're right about the limited space assumption. And yes, that was what I said to that (stubborn) TA, but he refused :(  
> **username_4**: @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).  
> **username_1**: @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"  
> **username_2**: 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".  

---

## 10 answers

### Answer by username_12 on 2010-10-30. Score: 48 | Accepted answer

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.

> **Comments:**
> **username_0**: +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.  

---

### Answer by username_5 on 2010-10-31. Score: 17

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 {
    private Queue first = new Queue();
    private Queue second = new Queue();
    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 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.

> **Comments:**
> **username_0**: about deleting an answer, please take a look at http://meta.cstheory.stackexchange.com/q/386/873.  
> **username_0**: I can't understand the line `first.Enqueue(first.Dequeue())`. Have you mistyped something?  
> **username_5**: 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.  
> **username_4**: for me the algorithm was more readable and easier to understand before the edit.  

---

### Answer by username_5 on 2010-10-31. Score: 13

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 username_14.
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 {
    private Queue first = new Queue();
    private Queue second = new Queue();
    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 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 {
    private Queue first = new Queue();
    private Queue second = new Queue();
    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 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.

> **Comments:**
> **username_5**: I edited the first paragraphs so my answer is formulated as an actual answer to the question.  
> **username_4**: You are using an array (reverser) for reversing! I don't think you are allowed to do this.  
> **username_5**: 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.  
> **username_7**: "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.  
> **username_5**: 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.  
> **username_6**: I think that you should look at the queues as if they were black-boxes with interface consisting of enqueue & dequeue only and only use constant amount of space (other then the queues).  

---

### Answer by username_8 on 2011-03-25. Score: 9

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.

> **Comments:**
> **username_8**: 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!  
> **username_9**: 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}}$.  
> **username_10**: Apparently Peter's answer contradicts this lower bound?  
> **username_8**: @username_10 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.  
> **username_8**: @username_9 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.  

---

### Answer by username_11 on 2011-04-30. Score: 6

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

> **Comments:**
> **username_12**: See http://cstheory.stackexchange.com/questions/4322/reversing-a-list-using-two-queues/4328  
> **username_11**: 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.  

---

### Answer by username_13 on 2011-09-07. Score: 1

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.


---

### Answer by username_14 on 2010-10-30. Score: 0

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.

> **Comments:**
> **username_15**: 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.  
> **username_14**: Looks like you can! However, it looks like more than one classical queue is necessary to simulate a stack in this way.  

---

### Answer by username_16 on 2018-08-14. Score: 0

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.


---

### Answer by username_17 on 2011-01-18. Score: 0

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?
Without allowing front loading, here is another solution:
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.

> **Comments:**
> **username_9**: Your second algorithm is helpful to understand the more involved one of Alex.  

---

### Answer by username_18 on 2014-01-16. Score: -3

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;
}
}

> **Comments:**
> **username_12**: Did you miss the part in the question about amortized time O(1)?  

---

