Implement a Queue using Stacks

Table of Contents +

This one looks simple. But the interviewer is testing something sneaky. A queue and a stack work in opposite ways. So how do you build one out of the other? They want to see if you understand the order each structure follows. They also want to see if you can spot a clever trick to flip that order. Let me show you how.

First, a quick reminder. A queue is First In First Out, or FIFO. The first person who joins the line is the first one served. A stack is Last In First Out, or LIFO. The last plate you put on the pile is the first one you take off. So a stack hands things back in reverse. That reverse is the whole secret here.

🔄 The Problem

You have to build a queue. But the only tool you are allowed is the stack. You can push to the top and pop from the top. The trick is that you may use more than one stack. Using these, you must support two queue operations. enqueue(x) adds an element to the back. dequeue() removes and returns the element from the front.

enqueue(1)
enqueue(2)
enqueue(3)
dequeue()   ->  1
dequeue()   ->  2
enqueue(4)
dequeue()   ->  3
dequeue()   ->  4

See the order? Whatever goes in first must come out first. But a single stack would give you 3, 2, 1. That is backwards. So we need a way to flip it.

🤔 The Simple Idea (and why it hurts)

The first approach people try is making enqueue do all the hard work. You keep one main stack. Every time a new element comes in, you first move everything out to a helper stack, push the new element at the bottom, then move everything back. Now the oldest element always sits on top, ready for dequeue.

This works. But it is slow. Every single enqueue shuffles the whole queue twice. So adding n elements costs you a lot of repeated moving. We can do better by being lazy.

🚀 The Better Idea: Two Stacks, Move Only When Needed

Here is the smarter plan. We keep two stacks. Call them inStack and outStack.

When you enqueue, just push onto inStack. That is it. Fast and done.

When you dequeue, look at outStack first. If it has something, pop from it. If it is empty, pour everything from inStack into outStack one by one. That pouring reverses the order. So the oldest element ends up on top of outStack. Now pop it.

The trick is we only pour when outStack runs dry. We do not move things on every operation. Each element is pushed onto inStack once, moved to outStack once, and popped once. That is a constant amount of work per element. So even though one dequeue might do a big pour, the cost spread over all operations stays small. That is what we call amortized O(1). On average each operation is constant time, even if one of them now and then is heavier.

Steps to dequeue

Check if outStack is empty.
If it is empty, pop every element from inStack and push each one onto outStack. This flips the order.
Now pop the top of outStack. That is your front element.
For enqueue, you simply push the new element onto inStack.

Here is the full queue with enqueue and dequeue, plus a small demo that prints results.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    # enqueue: just push onto the input stack
    def enqueue(self, x):
        self.in_stack.append(x)

    # dequeue: pour into out_stack only when it is empty, then pop
    def dequeue(self):
        if not self.out_stack:
            # move everything from in_stack to out_stack (this reverses order)
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack.pop()


q = MyQueue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 1
print(q.dequeue())  # 2
q.enqueue(4)
print(q.dequeue())  # 3
print(q.dequeue())  # 4

The output of the above code will be:

⏱️ Time and Space Complexity

Let me compare the two ideas so you can see why the lazy one wins.

Approach	Enqueue	Dequeue	Space
Heavy enqueue (shuffle every time)	O(n)	O(1)	O(n)
Two stacks, lazy pour	O(1)	O(1) amortized	O(n)

In the lazy version a single dequeue can cost O(n) when it has to pour. But that pour happens rarely. Each element is pushed onto inStack once, moved to outStack once, and popped once. That is a constant amount of work per element. So spread across all the calls, the average cost per operation stays O(1).

Tip

When the interviewer asks for the dequeue cost, do not just say O(1). Say “amortized O(1)” and explain why. Each element is pushed onto inStack once, moved to outStack once, and popped once. That one sentence shows you really understand the trick, not just the code.

🧩 Key Takeaways

✅ A stack reverses order, and two reverses bring you back to the original order. That is how a queue comes out of stacks.
✅ Keep enqueue cheap by always pushing onto inStack. Do the work later.
✅ Only pour inStack into outStack when outStack is empty. Never pour while it still has elements, or you will mix up the order.
✅ The cost is amortized O(1) because each element is pushed once, moved once, and popped once. That is constant work per element.
✅ Always say “amortized” out loud in the interview and explain it. That is the answer they are listening for.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Min Stack
Queue Using Linked List

Previous Min Stack Next Maximum Depth of a Binary Tree

Share & Connect

Share on LinkedIn