Implement Queue using Stacks — Problem & Solution
Implement Queue using Stacks solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Implement Queue using Stacks is an easy coding problem on stack and queue, asked in Amazon, Microsoft, Bloomberg and Apple interviews.
- Difficulty: Easy
- Topics: Stack, Queue
- Asked at: Amazon, Microsoft, Bloomberg, Apple
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Implement a first-in-first-out (FIFO) queue using only stacks. Write the class MyQueue:
MyQueue()creates an empty queue.void push(int x)addsxto the back of the queue.int pop()removes the element at the front of the queue and returns it.int peek()returns the element at the front of the queue without removing it.boolean empty()returnstrueif the queue is empty,falseotherwise.
Your queue may use only the standard stack operations: push to the top, peek at or pop from the top, size, and is-empty. (In a language without a stack type, a list used only through those operations is fine.)
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for push.
Example 1
Input: ["MyQueue","push","push","peek","pop","empty"]
[[],[3],[8],[],[],[]]
Output: [null,null,null,3,3,false]
Explanation: 3 arrives before 8, so it is at the front: peek and pop both give 3, and 8 is still queued.
Example 2
Input: ["MyQueue","push","pop","push","push","peek","pop","pop","empty"]
[[],[6],[],[2],[5],[],[],[],[]]
Output: [null,null,6,null,null,2,2,5,true]
Explanation: 6 leaves at once; then 2 and 5 come out in arrival order and the queue is empty.
Constraints
1 <= x <= 9At most 100 calls are made to push, pop, peek and emptyEvery call to pop and peek is made on a non-empty queue
Follow-up: Can you make every operation amortized O(1) — n operations in O(n) total time, even if one of them takes longer?
Hints for Implement Queue using Stacks
Hint 1
Pouring one stack into another reverses the order of its elements — and reversed LIFO order is FIFO order.
Hint 2
Use an
instack that takes every push, and anoutstack that serves pops and peeks.Hint 3
Only when
outis empty, move everything fromintoout. Each element is moved at most once, so the cost averages out to O(1).
How to solve Implement Queue using Stacks
Two stacks make a queue: new elements land on in; the front of the queue is the top of out. When out runs dry, pouring in into it reverses those elements so the oldest ends on top.
Approach
push(x): pushxontoin.pop()/peek(): ifoutis empty, pop every element ofinand push it ontoout. Then pop / read the top ofout.empty(): the queue is empty when both stacks are.
Why it works
Every element in out is older than every element in in, because out is only refilled when empty, from elements that were all pushed earlier than anything pushed afterwards. Within out the order is reversed arrival order, so its top is the oldest element overall — the queue's front.
Complexity
- Time —
amortized O(1) per operation - Space —
O(n)
Pitfalls
- Pouring
inintooutwhileoutstill holds elements breaks the order — only transfer whenoutis empty. empty()must check both stacks.
Reference solution
Python
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x: int) -> None:
self.inbox.append(x)
def _shift(self) -> None:
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.outboxJava
class MyQueue {
private Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
public MyQueue() {
}
public void push(int x) {
in.push(x);
}
private void shift() {
if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
}
public int pop() {
shift();
return out.pop();
}
public int peek() {
shift();
return out.peek();
}
public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
}C++
class MyQueue {
stack<int> in, out;
void shift() {
if (out.empty()) while (!in.empty()) { out.push(in.top()); in.pop(); }
}
public:
MyQueue() {}
void push(int x) {
in.push(x);
}
int pop() {
shift();
int x = out.top();
out.pop();
return x;
}
int peek() {
shift();
return out.top();
}
bool empty() {
return in.empty() && out.empty();
}
};JavaScript
var MyQueue = function() {
this.inbox = [];
this.outbox = [];
};
MyQueue.prototype.push = function(x) {
this.inbox.push(x);
};
MyQueue.prototype.shiftStacks = function() {
if (this.outbox.length === 0) while (this.inbox.length > 0) this.outbox.push(this.inbox.pop());
};
MyQueue.prototype.pop = function() {
this.shiftStacks();
return this.outbox.pop();
};
MyQueue.prototype.peek = function() {
this.shiftStacks();
return this.outbox[this.outbox.length - 1];
};
MyQueue.prototype.empty = function() {
return this.inbox.length === 0 && this.outbox.length === 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 111 stack problems · the whole catalogue
Learn the technique: Stack Data Structure · Queues and Deques