Implement Queue using Stacks is Day 17 of the Tekraze DSA series, and it moves us from stacks into queues. You only get stack operations, yet you must hand items back in first in, first out order. Two stacks pull that off neatly.
Also Read: Daily Temperatures, Day 16, which wrapped up our stacks chapter with a monotonic stack.
What is the Implement Queue using Stacks problem?
You build a class MyQueue that behaves like a normal FIFO queue with push(x), pop(), peek() and empty(). The catch is that you may only use standard stack operations: push to top, pop from top, peek at top, size and is empty. On LeetCode this is problem 232, and calls are guaranteed to be valid, so you never pop from an empty queue.
java
MyQueue q = new MyQueue(); q.push(1); // queue is [1] q.push(2); // queue is [1, 2] q.peek(); // returns 1 q.pop(); // returns 1, queue is [2] q.empty(); // returns false
How should you think about Implement Queue using Stacks in plain words?
A stack flips order. If you pour one stack into another, the order flips again, and the oldest item lands on top.
So keep one stack as an inbox for new items and one as an outbox for serving them. Refill the outbox only when it runs dry. The front of the queue is then always waiting on top of the outbox. That is the whole trick to implement queue using stacks.
What does the brute force approach to Implement Queue using Stacks look like?
Use one main stack and a helper. On every push, move everything into the helper, push the new item, then move everything back. The oldest item always sits on top of the main stack, so pop and peek are instant.
python
class MyQueueBrute:
def __init__(self):
self.main, self.helper = [], []
def push(self, x):
while self.main:
self.helper.append(self.main.pop())
self.main.append(x)
while self.helper:
self.main.append(self.helper.pop())
def pop(self):
return self.main.pop()
def peek(self):
return self.main[-1]
def empty(self):
return not self.main
The brute force way to implement queue using stacks works, but every push costs O(n) because the whole queue moves twice. Over many pushes that adds up to O(n squared) total work.
How do you implement queue using stacks in the optimal way?
Push always goes onto the inbox in O(1). For pop or peek, check the outbox first. If it is empty, pop every item from the inbox and push it onto the outbox, which reverses the order so the oldest item ends up on top. If the outbox already has items, use them directly. The queue is empty only when both stacks are empty.
Time is O(1) for push and empty, and amortized O(1) for pop and peek. Each item moves from inbox to outbox at most once in its life. A single pop can cost O(n) when it triggers a refill, but averaged over all operations the cost stays constant, which is the idea behind amortized analysis. Space is O(n) for the stored items. For a refresher on amortized and worst case thinking, see our Big O helper post.
Java solution for Implement Queue using Stacks
Java’s own docs recommend ArrayDeque over the old Stack class, so both stacks use it here.
java
import java.util.ArrayDeque;
import java.util.Deque;
class MyQueue {
private final Deque<Integer> in = new ArrayDeque<>();
private final Deque<Integer> out = new ArrayDeque<>();
public void push(int x) { in.push(x); }
public int pop() { shift(); return out.pop(); }
public int peek() { shift(); return out.peek(); }
public boolean empty() { return in.isEmpty() && out.isEmpty(); }
// Move items only when out is empty, so each item moves once
private void shift() {
if (out.isEmpty()) {
while (!in.isEmpty()) out.push(in.pop());
}
}
public static void main(String[] args) {
MyQueue q = new MyQueue();
q.push(1); q.push(2);
check(q.peek() == 1, "peek 1");
check(q.pop() == 1, "pop 1");
check(!q.empty(), "not empty");
q.push(3);
check(q.pop() == 2, "pop 2");
check(q.pop() == 3, "pop 3");
check(q.empty(), "empty");
for (int i = 0; i < 5; i++) q.push(i);
for (int i = 0; i < 5; i++) check(q.pop() == i, "order " + i);
System.out.println("All Java tests passed");
}
static void check(boolean ok, String name) {
if (!ok) throw new AssertionError("Failed: " + name);
}
}
Python solution for Implement Queue using Stacks
In Python, a plain list works as a stack, as the official tutorial explains.
python
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x: int) -> None:
self.inbox.append(x)
def _shift(self) -> None:
# Refill outbox only when it is empty, so each item moves once
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def pop(self) -> int:
self._shift()
return self.outbox.pop()
def peek(self) -> int:
self._shift()
return self.outbox[-1]
def empty(self) -> bool:
return not self.inbox and not self.outbox
if __name__ == "__main__":
q = MyQueue()
q.push(1); q.push(2)
assert q.peek() == 1
assert q.pop() == 1
assert not q.empty()
q.push(3)
assert q.pop() == 2
assert q.pop() == 3
assert q.empty()
for i in range(5):
q.push(i)
assert [q.pop() for _ in range(5)] == list(range(5))
print("All Python tests passed")
Rust solution for Implement Queue using Stacks
Rust uses a Vec as the stack. Note that peek takes &mut self because it may trigger the refill.
rust
struct MyQueue {
inbox: Vec<i32>,
outbox: Vec<i32>,
}
impl MyQueue {
fn new() -> Self {
MyQueue { inbox: Vec::new(), outbox: Vec::new() }
}
fn push(&mut self, x: i32) {
self.inbox.push(x);
}
// Refill outbox only when it is empty, so each item moves once
fn shift(&mut self) {
if self.outbox.is_empty() {
while let Some(x) = self.inbox.pop() {
self.outbox.push(x);
}
}
}
fn pop(&mut self) -> i32 {
self.shift();
self.outbox.pop().expect("queue is empty")
}
fn peek(&mut self) -> i32 {
self.shift();
*self.outbox.last().expect("queue is empty")
}
fn empty(&self) -> bool {
self.inbox.is_empty() && self.outbox.is_empty()
}
}
fn main() {
let mut q = MyQueue::new();
q.push(1);
q.push(2);
assert_eq!(q.peek(), 1);
assert_eq!(q.pop(), 1);
assert!(!q.empty());
q.push(3);
assert_eq!(q.pop(), 2);
assert_eq!(q.pop(), 3);
assert!(q.empty());
for i in 0..5 {
q.push(i);
}
for i in 0..5 {
assert_eq!(q.pop(), i);
}
println!("All Rust tests passed");
}
Each program runs the classic push 1, push 2, peek, pop, empty sequence. It also tests a push that arrives between pops, draining to empty, and a five item run that checks strict FIFO order.
What are the tips and tricks for an easy Implement Queue using Stacks solution?
- Spot the pattern. Whenever you need to implement queue using stacks, or reverse order once, think of pouring one stack into another.
- Refill lazily. Move items only when the outbox is empty. Moving on every call breaks the order and the complexity.
- Share one helper. Put the refill logic in a small
shiftmethod so pop and peek stay in sync. - Check both stacks in empty(). Items can live in either stack.
- Test the order with five or more pushes. A run of pushes followed by pops catches refill bugs that a two item test hides.
- Explain amortized cost out loud in interviews. Each item is pushed twice and popped twice in total, so n operations cost O(n) overall.
What are the common mistakes in Implement Queue using Stacks?
- Moving items from inbox to outbox even when the outbox still has items, which mixes up the order.
- Checking only the inbox in
empty(). - Claiming pop is always O(1) instead of amortized O(1).
- Duplicating the transfer code in pop and peek and letting the two copies drift apart.
- Using a language deque as a real queue, which skips the whole point of the exercise.
Where is the Implement Queue using Stacks pattern used in the real world?
The two stack queue shows up in functional programming, where immutable lists act like stacks and a pair of them gives a fast persistent queue. It also appears in undo and redo buffers and in message batching, where producers write to one buffer while consumers drain another. The same trick powers the min queue used in sliding window maximum and minimum problems.
Which earlier posts in the series should you read?
Start with Day 1, Two Sum for hash map basics and Day 2, Best Time to Buy and Sell Stock for tracking a running minimum. Days 3 to 5 build the counting toolkit, and Days 6 to 9 cover two pointers. Days 10 to 12 walk through sliding window.
The stacks chapter matters most before this one. Read Day 13, Valid Parentheses, Day 14, Min Stack and Day 16, Daily Temperatures first. Keep our data structures cheat sheet handy to compare stacks and queues with other structures.
Final thoughts
Close the tab and implement queue using stacks again from memory with an inbox, an outbox and one shift method. If you can explain why each item moves only once, you have the amortized argument that interviewers want to hear.
Frequently asked questions
What is the Implement Queue using Stacks problem?
You build a first in, first out queue with push, pop, peek and empty while only using stack operations like push to top and pop from top.
Why do we need two stacks to build a queue?
One stack reverses order. Pouring it into a second stack reverses it again, so the oldest item ends up on top and can be served first.
What is the time complexity of a queue built with two stacks?
Push and empty are O(1). Pop and peek are amortized O(1), since each item moves from the inbox to the outbox only once. Space is O(n).
What does amortized O(1) mean here?
A single pop can take O(n) when it refills the outbox, but across any sequence of operations the average cost per operation stays constant.
Where is the two stack queue used in practice?
Persistent queues in functional languages, producer and consumer buffers, undo and redo systems, and min or max queues for sliding window problems.
