Implement Stack using Queues
EasyPrompt
Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).
Implement the MyStack class:
void push(int x)Pushes element x to 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.boolean empty()Returnstrueif the stack is empty,falseotherwise.
Notes:
- You must use only standard operations of a queue, which means that only
push to back,peek/pop from front,sizeandis emptyoperations are valid. - Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.
Example 1:
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
Constraints:
1 <= x <= 9- At most
100calls will be made topush,pop,top, andempty. - All the calls to
popandtopare valid.
Follow-up: Can you implement the stack using only one queue?
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses two queues to implement a stack. The main idea is to keep one queue as the main storage and use the second queue as temporary storage during pop operations.
Algorithm
- Initialize two queues q1 and q2
- For push operation:
- Add element to q1
- For pop operation:
- Move all elements except last from q1 to q2
- Get and remove the last element from q1
- Swap q1 and q2
- For top operation:
- Similar to pop but return the last element without removing
- For empty operation:
- Check if q1 is empty
Walkthrough
In this approach, we maintain two queues: q1 and q2. The push operation is straightforward - we simply add elements to q1. For pop operations, we move all elements except the last one from q1 to q2, get the last element from q1, and then swap q1 and q2.
class MyStack { private Queue<Integer> q1; private Queue<Integer> q2; public MyStack() { q1 = new LinkedList<>(); q2 = new LinkedList<>(); } public void push(int x) { q1.offer(x); } public int pop() { // Move all elements except last from q1 to q2 while (q1.size() > 1) { q2.offer(q1.poll()); } // Get the last element int result = q1.poll(); // Swap q1 and q2 Queue<Integer> temp = q1; q1 = q2; q2 = temp; return result; } public int top() { // Move all elements except last from q1 to q2 while (q1.size() > 1) { q2.offer(q1.poll()); } // Get the last element int result = q1.peek(); // Move the last element to q2 q2.offer(q1.poll()); // Swap q1 and q2 Queue<Integer> temp = q1; q1 = q2; q2 = temp; return result; } public boolean empty() { return q1.isEmpty(); }}Complexity
Time
Push: O(1), Pop/Top: O(n) where n is the number of elements in the stack
Space
O(n) where n is the number of elements in the stack
Trade-offs
Pros
Push operation is O(1)
Implementation is straightforward
Memory usage is proportional to the number of elements
Cons
Pop and Top operations are inefficient O(n)
Requires two queues
Extra space needed for temporary storage during operations
This approach uses only one queue to implement a stack. The main idea is to reorder the elements after each push operation to maintain stack order.
Algorithm
- Initialize one queue
- For push operation:
- Add new element to queue
- Rotate queue by moving all elements except the new one to the back
- For pop operation:
- Simply remove and return the front element
- For top operation:
- Return the front element without removing
- For empty operation:
- Check if queue is empty
Walkthrough
In this approach, we use a single queue. When pushing a new element, we first add it to the queue, then we rotate the queue by moving all elements except the newly added one to the back of the queue. This ensures that the newest element is always at the front of the queue.
class MyStack { private Queue<Integer> queue; public MyStack() { queue = new LinkedList<>(); } public void push(int x) { queue.offer(x); // Rotate the queue to move the new element to front for (int i = 0; i < queue.size() - 1; i++) { queue.offer(queue.poll()); } } public int pop() { return queue.poll(); } public int top() { return queue.peek(); } public boolean empty() { return queue.isEmpty(); }}Complexity
Time
Push: O(n), Pop/Top: O(1) where n is the number of elements in the stack
Space
O(n) where n is the number of elements in the stack
Trade-offs
Pros
Uses only one queue
Pop and Top operations are O(1)
Less space overhead compared to two-queue approach
Cons
Push operation is inefficient O(n)
Requires reordering of elements after each push
May not be suitable for large number of push operations
Solutions
Solution
import java.util.Deque ; class MyStack { private Deque < Integer > q1 = new ArrayDeque <>(); private Deque < Integer > q2 = new ArrayDeque <>(); public MyStack () { } public void push ( int x ) { q2 . offer ( x ); while (! q1 . isEmpty ()) { q2 . offer ( q1 . poll ()); } Deque < Integer > q = q1 ; q1 = q2 ; q2 = q ; } public int pop () { return q1 . poll (); } public int top () { return q1 . peek (); } public boolean empty () { return q1 . isEmpty (); } } /** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * boolean param_4 = obj.empty(); */class MyStack { public: MyStack () { } void push ( int x ) { q2 . push ( x ); while ( ! q1 . empty ()) { q2 . push ( q1 . front ()); q1 . pop (); } swap ( q1 , q2 ); } int pop () { int x = q1 . front (); q1 . pop (); return x ; } int top () { return q1 . front (); } bool empty () { return q1 . empty (); } private: queue < int > q1 ; queue < int > q2 ; }; /** * Your MyStack object will be instantiated and called as such: * MyStack* obj = new MyStack(); * obj->push(x); * int param_2 = obj->pop(); * int param_3 = obj->top(); * bool param_4 = obj->empty(); */# one queue ''' push(1), [1] push(2), [1,2] => [2,1] push(3), [2,1,3] => [1,3,2] => [3,2,1] push(4), [3,2,1,4] => switch 3 time to get [4,3,2,1] push(5), [4,3,2,1,5] => switch 4 time to get [5,4,3,2,1] ''' class Stack : def __init__ ( self ): self . _queue = collections . deque () def push ( self , x ): q = self . _queue q . append ( x ) for _ in range ( len ( q ) - 1 ): q . append ( q . popleft ()) def pop ( self ): return self . _queue . popleft () def top ( self ): return self . _queue [ 0 ] def empty ( self ): return not len ( self . _queue ) # Your MyStack object will be instantiated and called as such: # obj = MyStack() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.top() # param_4 = obj.empty() ############ from collections import deque # two queues class MyStack : def __init__ ( self ): self . q1 = deque () self . q2 = deque () def push ( self , x : int ) -> None : self . q1 . append ( x ) def pop ( self ) -> int : while len ( self . q1 ) != 1 : self . q2 . append ( self . q1 . popleft ()) val = self . q1 . popleft () self . q1 , self . q2 = self . q2 , self . q1 return val def top ( self ) -> int : while len ( self . q1 ) != 1 : self . q2 . append ( self . q1 . popleft ()) # tried to re-use while part, but seems not achievable, since val is retrieved in-between val = self . q1 [ 0 ] self . q2 . append ( self . q1 . popleft ()) # note: add back to q2, so q1 will always be empty self . q1 , self . q2 = self . q2 , self . q1 return val def empty ( self ) -> bool : return not self . q1 # Your MyStack object will be instantiated and called as such: # obj = MyStack() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.top() # param_4 = obj.empty()Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.