Implement Stack using Queues
Implement Stack using Queues is a easy stack problem solved with the stack basics pattern.
The best approach, optimal (single queue, rotate on push), runs in O(n) push, O(1) pop/top/empty time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (two queues, dig out the last element) up.
Problem
Build a last-in-first-out stack, MyStack, using only queues and their standard operations (add to the back, read or remove the front, size, is-empty). MyStack() creates an empty stack.
push(int x) places x on top of the stack. pop() removes the top element and returns it, and top() returns the top element without removing it. empty() returns true when the stack holds no elements and false otherwise.
Examples
Example 1
- Input
MyStack(), push(4), push(7), top(), push(1), pop(), pop(), empty(), top()- Output
7, 1, 7, false, 4- Why
- The most recent value always leaves first: 1 goes out before 7, and 4 is left on top.
Example 2
- Input
MyStack(), empty(), push(3), pop(), empty()- Output
true, 3, true- Why
- A new stack is empty; after pushing and popping 3 it is empty again.
Constraints
1 <= x <= 9- At most
100calls topush,pop,topandempty. popandtopare only called on a non-empty stack.- Use only standard queue operations: add to the back, look at / remove from the front, size and is-empty.
- Follow-up: can you do it with a single queue?
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (two queues, dig out the last element) | O(1) push, O(n) pop/top | O(n) |
| Optimal (single queue, rotate on push) | O(n) push, O(1) pop/top/empty | O(n) |
1Brute force (two queues, dig out the last element)
O(1) push, O(n) pop/topEach pop or top walks all n elements through the helper queue once.O(n)The two queues hold n elements together.Push simply appends to the main queue. To pop or read the top, move all but the last element into a helper queue, deal with the last one, then swap the roles of the two queues.
- push(x): add x to the back of
main. - pop(): move size - 1 elements from
maintohelper; remove the last one frommainand remember it; swapmainandhelper; return the value. - top(): same as pop, but also add the last element to
helperbefore swapping so it stays stored. - empty(): return whether
mainis empty.
class MyStack {
private Queue<Integer> main = new ArrayDeque<>();
private Queue<Integer> helper = new ArrayDeque<>();
public MyStack() {}
public void push(int x) {
main.offer(x);
}
public int pop() {
while (main.size() > 1) helper.offer(main.poll());
int last = main.poll();
Queue<Integer> tmp = main;
main = helper;
helper = tmp;
return last;
}
public int top() {
while (main.size() > 1) helper.offer(main.poll());
int last = main.poll();
helper.offer(last);
Queue<Integer> tmp = main;
main = helper;
helper = tmp;
return last;
}
public boolean empty() {
return main.isEmpty();
}
}class MyStack:
def __init__(self):
self.main = deque()
self.helper = deque()
def push(self, x: int) -> None:
self.main.append(x)
def pop(self) -> int:
while len(self.main) > 1:
self.helper.append(self.main.popleft())
last = self.main.popleft()
self.main, self.helper = self.helper, self.main
return last
def top(self) -> int:
while len(self.main) > 1:
self.helper.append(self.main.popleft())
last = self.main.popleft()
self.helper.append(last)
self.main, self.helper = self.helper, self.main
return last
def empty(self) -> bool:
return len(self.main) == 0class MyStack {
queue<int> mainQ, helper;
public:
MyStack() {}
void push(int x) {
mainQ.push(x);
}
int pop() {
while (mainQ.size() > 1) {
helper.push(mainQ.front());
mainQ.pop();
}
int last = mainQ.front();
mainQ.pop();
swap(mainQ, helper);
return last;
}
int top() {
while (mainQ.size() > 1) {
helper.push(mainQ.front());
mainQ.pop();
}
int last = mainQ.front();
mainQ.pop();
helper.push(last);
swap(mainQ, helper);
return last;
}
bool empty() {
return mainQ.empty();
}
};class MyStack {
constructor() {
this.main = [];
this.helper = [];
}
push(x) {
this.main.push(x);
}
pop() {
while (this.main.length > 1) this.helper.push(this.main.shift());
const last = this.main.shift();
[this.main, this.helper] = [this.helper, this.main];
return last;
}
top() {
while (this.main.length > 1) this.helper.push(this.main.shift());
const last = this.main.shift();
this.helper.push(last);
[this.main, this.helper] = [this.helper, this.main];
return last;
}
empty() {
return this.main.length === 0;
}
}2Optimal (single queue, rotate on push)
O(n) push, O(1) pop/top/emptyEach push rotates the n - 1 older elements once; the other operations touch only the front.O(n)One queue holding the n elements.Keep the queue ordered so its front is always the stack's top. When x is added at the back, move the size - 1 older elements from the front to the back one by one. After that rotation x is at the front, and the older elements follow in newest-to-oldest order.
- push(x): add x to the back; then repeat size - 1 times: remove the front and add it to the back.
- pop(): remove and return the front.
- top(): return the front without removing it.
- empty(): return whether the queue is empty.
class MyStack {
private final Queue<Integer> q = new ArrayDeque<>();
public MyStack() {}
public void push(int x) {
q.offer(x);
for (int i = 0; i < q.size() - 1; i++) {
q.offer(q.poll());
}
}
public int pop() {
return q.poll();
}
public int top() {
return q.peek();
}
public boolean empty() {
return q.isEmpty();
}
}class MyStack:
def __init__(self):
self.q = deque()
def push(self, x: int) -> None:
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self) -> int:
return self.q.popleft()
def top(self) -> int:
return self.q[0]
def empty(self) -> bool:
return len(self.q) == 0class MyStack {
queue<int> q;
public:
MyStack() {}
void push(int x) {
q.push(x);
for (int i = 0; i < (int)q.size() - 1; i++) {
q.push(q.front());
q.pop();
}
}
int pop() {
int v = q.front();
q.pop();
return v;
}
int top() {
return q.front();
}
bool empty() {
return q.empty();
}
};class MyStack {
constructor() {
this.q = [];
}
push(x) {
this.q.push(x);
for (let i = 0; i < this.q.length - 1; i++) {
this.q.push(this.q.shift());
}
}
pop() {
return this.q.shift();
}
top() {
return this.q[0];
}
empty() {
return this.q.length === 0;
}
}Edge cases to test
emptyon a brand-new stack- Pushing again after the stack was emptied
- Interleaved pushes and pops, so new values must land on top of older ones
Hints
Hint 1
A queue gives you the oldest element. To reach the newest one, everything in front of it must be moved out of the way.
Hint 2
Moving elements from the front of a queue to its back keeps them in the same queue but rotates the order.
Hint 3
After adding x at the back, rotate the other size - 1 elements behind it. Now x is at the front, exactly where a stack's top should be.
FAQ
What is the best time complexity for Implement Stack using Queues?
Optimal (single queue, rotate on push) runs in O(n) push, O(1) pop/top/empty time and O(n) extra space. Each push rotates the n - 1 older elements once; the other operations touch only the front.
Which pattern does Implement Stack using Queues use?
It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.
Is there a brute force solution for Implement Stack using Queues?
Yes. Brute force (two queues, dig out the last element) takes O(1) push, O(n) pop/top time and O(n) space. Push simply appends to the main queue.
Which edge cases should I test for Implement Stack using Queues?
empty on a brand-new stack; Pushing again after the stack was emptied; Interleaved pushes and pops, so new values must land on top of older ones.