Implement Queue using Stacks

Build a first-in, first-out queue, MyQueue, using only two stacks for storage. You may use only standard stack operations on them: push onto the top, look at or remove the top element, check the size, and check whether a stack is empty. In Python or JavaScript, a list or array used only through append/push and pop plays the role of a stack.

Implement:

• MyQueue() creates an empty queue.
• push(x) adds x to the back of the queue.
• pop() removes the element at the front of the queue and returns it.
• peek() returns the front element without removing it.
• empty() returns true if the queue holds no elements.

Each test is a list of method calls and their arguments; the expected output lists every call's return value, with null for the constructor and push.

Example 1

Example 2

Example 3

Constraints

• 1 <= x <= 109
• At most 104 calls are made in total.
• pop and peek are only called when the queue is not empty.

Pattern Path · Design · problem 161 of 169

Start simple

Keep one stack in queue order; on every push, move everything to the second stack, push the new element, and move everything back: O(n) per push.

The key idea

A stack gives elements back in reverse order. Reverse twice and you get the original order, which is what a queue needs. So use two stacks with fixed roles:

• inbox receives every new element on push;
• outbox holds elements in pop order, with the oldest element on top.

For pop and peek, if outbox is empty, move every element from inbox to outbox. That reversal puts the oldest remaining element on top. Then answer from the top of outbox.

The important rule is to refill only when outbox is empty. Everything already in outbox is older than anything in inbox, so pouring in newer elements on top of it would break the order.

A single transfer can take O(n) time, but each element is moved from inbox to outbox at most once in its life, so each operation costs O(1) amortised. The queue is empty only when both stacks are.

Complexity

• Time: O(1) amortised per operation
• Space: O(n)

Python

class MyQueue:
    def __init__(self):
        self.inbox = []   # new elements are pushed here
        self.outbox = []  # elements waiting to leave, oldest on top

    def push(self, x):
        self.inbox.append(x)

    def pop(self):
        self._refill()
        return self.outbox.pop()

    def peek(self):
        self._refill()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox

    def _refill(self):
        # Only refill when outbox is empty; otherwise newer elements
        # would be stacked on top of older ones.
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

JavaScript

class MyQueue {
  constructor() {
    this.inbox = [];  // new elements are pushed here
    this.outbox = []; // elements waiting to leave, oldest on top
  }

  push(x) {
    this.inbox.push(x);
  }

  pop() {
    this.refill();
    return this.outbox.pop();
  }

  peek() {
    this.refill();
    return this.outbox[this.outbox.length - 1];
  }

  empty() {
    return this.inbox.length === 0 && this.outbox.length === 0;
  }

  refill() {
    // Only refill when outbox is empty; otherwise newer elements
    // would be stacked on top of older ones.
    if (this.outbox.length === 0) {
      while (this.inbox.length > 0) this.outbox.push(this.inbox.pop());
    }
  }
}

What the interviewer is checking

This checks whether you understand how stacks and queues order elements, and whether you can explain amortised cost: one operation can be slow, but the total work stays linear.

Mistakes to avoid

• Moving elements to the out stack while it still holds older elements, which mixes up the order.
• Moving everything back to the in stack after each pop, turning every operation into O(n).
• Checking only one stack in empty().
• Duplicating the transfer logic in pop and peek instead of sharing a helper, which invites subtle differences.

Follow-ups to expect

• Can you implement a stack using queues? (Rotate the queue after each push.)
• Why is pop O(1) amortised and not worst case? (Each element transfers only once.)
• How would you make it safe for concurrent producers and consumers? (Locks, or a lock-free ring buffer.)

In real software

Functional languages build immutable queues from two lists in exactly this way, and the amortised-transfer idea also underlies batching buffers in message pipelines.

Practice next