Implement Queue using Stacks
Easy · Stack & Strings · Stack · Design · Queue
Problem
Build a first-in, first-out queue out of two stacks, using only the standard stack operations: push to the top, look at or pop the top, size, and is-empty.
Implement the class MyQueue:
- MyQueue() creates an empty queue.
- void push(int x) adds x to the back of the queue.
- int pop() removes the element at the front and returns it.
- int peek() returns the element at the front without removing it.
- boolean empty() returns whether the queue is empty.
The tests describe a run as two lists: ops names each call (the first is always MyQueue) and vals holds its arguments. The expected output lists what each call returns, with None for calls that return nothing.
Examples
Input: push(4), push(7), push(1), pop(), peek(), empty() Output: 4, then 7, then false
4 went in first, so it leaves first. 7 is then at the front, and the queue still holds 7 and 1.
Input: push(9), pop(), empty() Output: 9, then true
Removing the only element leaves the queue empty.
Input: push(1), push(2), pop(), push(3), pop(), pop() Output: 1, then 2, then 3
A push in the middle still waits behind 2, which arrived earlier.
Constraints
- 1 <= x <= 10^9
- At most 10^4 calls in all
- pop and peek are only called on a non-empty queue
- Follow-up: every call O(1) amortized
Approaches
- Baseline: keep the oldest on top, rebuild on every push — time O(n) per push, O(1) for the rest, space O(n)
Follow-up
The opposite direction, a stack built from queues, has no amortized trick: with one queue, each push rotates the queue so the new element is in front, which is O(n) per push. The asymmetry comes from reversal: two reversals restore order, but a queue never reverses anything.
Related problems
Start free on Cariara · Coding problems · System design studio
