Skip to main content
DSA patterns

Implement Queue using Stacks

easyStack and queueAccentureWiproInfosys

Problem statement

Build a first-in-first-out (FIFO) queue, but you're only allowed to use stacks internally — no list, deque, or queue from the language's library, just the standard stack operations: push something on top, look at or remove the top, check the size, and check if it's empty.

Implement a MyQueue class with:

  • push(x) — adds x to the back of the queue.
  • pop() — removes and returns the value at the front of the queue.
  • peek() — returns the value at the front without removing it.
  • empty() — returns true if the queue holds nothing.

A stack only ever lets you reach the item you pushed most recently (last in, first out), which is the opposite order from a queue (first in, first out). The trick is arranging two stacks so that, from the outside, they still behave like one queue.

Examples

Example 1

Input: ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]

Output: [null, null, null, 1, 1, false]

Explanation: MyQueue() creates an empty queue. push(1) then push(2) leave the queue holding 1 then 2, with 1 at the front since it was pushed first. peek() returns 1 without removing it. pop() removes and returns 1, leaving only 2. empty() returns false because 2 is still there.

Hints

Hint 1: A single stack always hands back the item pushed most recently — exactly backwards from what a queue needs. Reversing that order is the whole problem.

Approach

Optimal: Two stacks, amortized

Intuition

Instead of doing the reversal work on every push, do it lazily — only when it's actually needed. Keep two stacks: inStack collects new pushes in whatever order they arrive (newest on top), and outStack holds items in front-to-back order (front on top), ready to be popped or peeked directly. push is trivial: just add to inStack. When pop or peek is called and outStack is empty, dump everything from inStack into outStack in one go — this reverses their order exactly once, putting the oldest pushed item on top. As long as outStack still has items left, later pop/peek calls use it directly with no extra work. That's what makes it faster on average than the brute-force approach: an item is only moved once per stack it passes through, not on every single push.

Steps

  1. Keep two stacks, inStack and outStack, both empty at the start.
  2. push(x): push x onto inStack — nothing else happens.
  3. Before a pop or peek: if outStack is empty, pop every item off inStack and push it onto outStack (this reverses their order).
  4. pop() pops and returns the top of outStack; peek() looks at the top of outStack without removing it.
  5. empty() returns true only when both inStack and outStack are empty.

Dry run

push(1), push(2), push(3), pop(), push(4), pop(), pop(), pop():

call inStack outStack shift happens? returns
push(1) [1] [] no —
push(2) [1,2] [] no —
push(3) [1,2,3] [] no —
pop() [] [3,2,1] yes (outStack was empty) 1
push(4) [4] [3,2] no —
pop() [4] [3] no (outStack not empty) 2
pop() [4] [] no 3
pop() [] [] yes (outStack was empty) 4

Every value comes out in the order it was pushed — 1, 2, 3, 4 — even though push(4) happened in the middle. Notice the shift only happens twice across eight calls, which is what keeps the average cost low.

Edge cases: empty() has to check both stacks, since items can be waiting in either one. pop/peek only trigger a shift when outStack is already empty — if it still holds items from an earlier shift, they're used first, which is what keeps the front-to-back order correct.

Complexity

Time Every - operation is amortized O(1). A single `pop` or `peek` can still cost O(n) on the rare call where a transfer happens, but each item only ever gets moved from `inStack` to `outStack` once across its whole lifetime in the queue, so the cost spreads out to O(1) per operation on average over many calls.

Space O(n) - the items are split between `inStack` and `outStack`, but together they still hold exactly the n items currently in the queue.

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

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def _shift(self) -> None:
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

    def pop(self) -> int:
        self._shift()
        return self.out_stack.pop()

    def peek(self) -> int:
        self._shift()
        return self.out_stack[-1]

    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack


if __name__ == "__main__":
    q = MyQueue()
    out = [None]
    q.push(1); out.append(None)
    q.push(2); out.append(None)
    out.append(q.peek())
    out.append(q.pop())
    out.append(q.empty())
    print(out)
RecapThe whole problem in a few lines, for the night before
  • Spot it: build a FIFO queue from two LIFO stacks
  • Idea: push to an input stack; on pop or peek, if the output stack is empty, move everything from input to output, which reverses the order
  • Cost: O(1) amortized per operation, O(n) space
  • Trap: only move items when the output stack is empty, or the order breaks

Interview follow-ups

  • Do the same thing in reverse: implement a stack using only queues.

    Use two queues, or even a single queue. With one queue: to push x, add it to the back as usual, then rotate the queue by dequeuing and re-enqueuing every element that was already there (all size - 1 of them) so that x ends up at the front. That makes push O(n) and pop/peek (just look at or remove the front) O(1) — the mirror image of the brute-force queue approach shown above.

  • How would you make push, pop, peek and empty safe to call from multiple threads at once?

    Wrap access to inStack and outStack in a single lock (or use two separate locks with a fixed acquisition order to avoid deadlock), so that a shift from inStack to outStack can't happen in the middle of another thread reading outStack. This turns amortized O(1) into amortized O(1) under contention, at the cost of threads blocking on each other during a shift — a lock-free version needs considerably more care to keep pushes, pops and shifts from corrupting each other.

Frequently asked questions

Any single pop or peek call can still trigger a full shift and cost O(n) — amortized doesn't mean every call is fast. It means that if you add up the cost of n operations total, the total work is O(n), because each item only gets physically moved from inStack to outStack exactly once during its entire time in the queue. Spread that one move across all the operations touching that item, and the average per operation comes out to O(1).

That's a valid variant with the same overall behaviour: push becomes O(1) (just push onto the stack) and the reversal work moves to pop/peek instead. The two-stack version shown here is really that idea taken further — it still does the reversal lazily, but keeps the already-reversed order around in outStack so that a run of pops after a single shift stays O(1) each, rather than re-reversing on every single pop.

It checks whether you understand the actual guarantees a data structure gives you, not just how to call its methods. The same skill — building a FIFO ordering out of a more restrictive primitive — comes up when a message broker only exposes LIFO semantics internally, or when you're limited to whatever operations a particular client library actually supports.

The problem's constraints guarantee that never happens (every pop/peek call in the input is valid), so neither approach checks for it. In your own production code you'd still want to raise a clear error or return an Optional instead of letting pop() on an empty stack throw a raw runtime exception.