Implement Stack using Queues — Problem & Solution
Implement Stack using Queues solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Implement Stack using Queues is an easy coding problem on stack and queue, asked in Amazon, Microsoft and Bloomberg interviews.
- Difficulty: Easy
- Topics: Stack, Queue
- Asked at: Amazon, Microsoft, Bloomberg
- 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 last-in-first-out (LIFO) stack using only queues. Write the class MyStack:
MyStack()creates an empty stack.void push(int x)pushesxonto the top of the stack.int pop()removes the element on the top of the stack and returns it.int top()returns the element on the top of the stack without removing it.boolean empty()returnstrueif the stack is empty,falseotherwise.
Your stack may use only the standard queue operations: push to the back, peek at or pop from the front, size, and is-empty. (In a language without a queue type, a list or deque 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: ["MyStack","push","push","top","pop","empty"]
[[],[4],[7],[],[],[]]
Output: [null,null,null,7,7,false]
Explanation: After pushing 4 then 7, the top is 7; pop removes 7, leaving 4, so the stack is not empty.
Example 2
Input: ["MyStack","empty","push","push","push","pop","top","pop","pop","empty"]
[[],[],[1],[9],[5],[],[],[],[],[]]
Output: [null,true,null,null,null,5,9,9,1,true]
Explanation: The stack starts empty. 1, 9, 5 are pushed; they come off in the order 5, 9, 1, after which the stack is empty again.
Constraints
1 <= x <= 9At most 100 calls are made to push, pop, top and emptyEvery call to pop and top is made on a non-empty stack
Follow-up: Can you implement the stack with only one queue?
Hints for Implement Stack using Queues
Hint 1
A queue hands elements back oldest first, a stack newest first. Arrange the queue so that its front is always the newest element.
Hint 2
When a new element is pushed to the back of the queue, every older element is in front of it.
Hint 3
After pushing
x, rotate the queuesize - 1times (pop from the front, push to the back). Nowxis at the front, sopopandtopare ordinary front operations.
How to solve Implement Stack using Queues
Keep one queue in stack order — newest element at the front. A push appends the new element and then rotates every older element behind it; after that, pop, top and empty are plain queue operations.
Approach
push(x): enqueuex, then repeatsize - 1times: dequeue the front element and enqueue it again.pop(): dequeue and return the front element.top(): return the front element without removing it.empty(): return whether the queue is empty.
Why it works
By induction the queue, read front to back, is the stack from top to bottom. Pushing x puts it last; rotating the size - 1 older elements from the front to the back moves them behind x in their existing order, so x is now first and the rest keep their stack order.
Complexity
- Time —
push O(n); pop, top and empty O(1) - Space —
O(n)
Pitfalls
- Rotating
sizetimes instead ofsize - 1puts the new element back at the end. - The two-queue version (move all but the last element across on each pop) is also accepted; it makes
popthe O(n) operation instead ofpush.
Reference solution
Python
from collections import deque
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): # bring x to the front
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) == 0Java
class MyStack {
private Queue<Integer> q = new ArrayDeque<>();
public MyStack() {
}
public void push(int x) {
q.offer(x);
for (int i = 1; i < q.size(); i++) q.offer(q.poll()); // bring x to the front
}
public int pop() {
return q.poll();
}
public int top() {
return q.peek();
}
public boolean empty() {
return q.isEmpty();
}
}C++
class MyStack {
queue<int> q;
public:
MyStack() {}
void push(int x) {
q.push(x);
for (size_t i = 1; i < q.size(); i++) { q.push(q.front()); q.pop(); } // bring x to the front
}
int pop() {
int x = q.front();
q.pop();
return x;
}
int top() {
return q.front();
}
bool empty() {
return q.empty();
}
};JavaScript
var MyStack = function() {
this.q = [];
};
MyStack.prototype.push = function(x) {
this.q.push(x);
for (var i = 1; i < this.q.length; i++) this.q.push(this.q.shift()); // bring x to the front
};
MyStack.prototype.pop = function() {
return this.q.shift();
};
MyStack.prototype.top = function() {
return this.q[0];
};
MyStack.prototype.empty = function() {
return this.q.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