Language Selection
Choose your preferred programming language
Showing: Python
Implement Stack using Queues
Problem Statement
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 onto the stackint pop()Removes the element on top of the stack and returns itint top()Returns the element on top of the stackboolean empty()Returns true if the stack is empty, false otherwise
Examples
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 100 calls will be made to
push,pop,top, andempty - All the calls to
popandtopare valid
Approach 1: Two Queues (Costly Push)
Algorithm
A queue is first-in-first-out, so to make it behave like a stack the newest element must always sit at the front. Keep the stack in outputQueue with the top element at its front, and use inputQueue as scratch space.
Steps:
push(x): addxto the emptyinputQueue- Move every element of
outputQueuebehind it, preserving their order - Swap the two queues, so
outputQueuenow holds the new element at the front followed by the older ones popandtopread the front ofoutputQueue, andemptychecks whether it is empty
Implementation
Python:
from collections import deque
class MyStack:
"""
Stack implementation using two queues
Time: O(n) push, O(1) pop/top/empty
Space: O(n)
"""
def __init__(self):
self.input_queue = deque()
self.output_queue = deque()
def push(self, x: int) -> None:
"""Push element x onto stack"""
self.input_queue.append(x)
self._transfer_if_needed()
def pop(self) -> int:
"""Remove element on top of stack and return it"""
return self.output_queue.popleft()
def top(self) -> int:
"""Return element on top of stack"""
return self.output_queue[0]
def empty(self) -> bool:
"""Return true if stack is empty"""
return len(self.input_queue) == 0 and len(self.output_queue) == 0
def _transfer_if_needed(self):
"""Move older elements behind the new one, then swap so output front is the top"""
while self.output_queue:
self.input_queue.append(self.output_queue.popleft())
self.input_queue, self.output_queue = self.output_queue, self.input_queue
Java:
import java.util.LinkedList;
import java.util.Queue;
class MyStack {
/**
* Stack implementation using two queues
* Time: O(n) push, O(1) pop/top/empty
* Space: O(n)
*/
private Queue<Integer> inputQueue;
private Queue<Integer> outputQueue;
public MyStack() {
inputQueue = new LinkedList<>();
outputQueue = new LinkedList<>();
}
public void push(int x) {
inputQueue.offer(x);
transferIfNeeded();
}
public int pop() {
return outputQueue.poll();
}
public int top() {
return outputQueue.peek();
}
public boolean empty() {
return inputQueue.isEmpty() && outputQueue.isEmpty();
}
private void transferIfNeeded() {
// Move older elements behind the new one, then swap so output front is the top
while (!outputQueue.isEmpty()) {
inputQueue.offer(outputQueue.poll());
}
Queue<Integer> temp = inputQueue;
inputQueue = outputQueue;
outputQueue = temp;
}
}
Go:
type MyStack struct {
inputQueue []int
outputQueue []int
}
// Constructor - Initialize stack
func Constructor() MyStack {
return MyStack{
inputQueue: make([]int, 0),
outputQueue: make([]int, 0),
}
}
// Push - Push element x onto stack
func (this *MyStack) Push(x int) {
this.inputQueue = append(this.inputQueue, x)
this.transferIfNeeded()
}
// Pop - Remove element on top of stack and return it
func (this *MyStack) Pop() int {
top := this.outputQueue[0]
this.outputQueue = this.outputQueue[1:]
return top
}
// Top - Return element on top of stack
func (this *MyStack) Top() int {
return this.outputQueue[0]
}
// Empty - Return true if stack is empty
func (this *MyStack) Empty() bool {
return len(this.inputQueue) == 0 && len(this.outputQueue) == 0
}
// transferIfNeeded - Move older elements behind the new one, then swap so output front is the top
func (this *MyStack) transferIfNeeded() {
for len(this.outputQueue) > 0 {
front := this.outputQueue[0]
this.outputQueue = this.outputQueue[1:]
this.inputQueue = append(this.inputQueue, front)
}
this.inputQueue, this.outputQueue = this.outputQueue, this.inputQueue
}
JavaScript:
/**
* Stack implementation using two queues
* Time: O(n) push, O(1) pop/top/empty
* Space: O(n)
*/
class MyStack {
constructor() {
this.inputQueue = [];
this.outputQueue = [];
}
push(x) {
this.inputQueue.push(x);
this.transferIfNeeded();
}
pop() {
return this.outputQueue.shift();
}
top() {
return this.outputQueue[0];
}
empty() {
return this.inputQueue.length === 0 && this.outputQueue.length === 0;
}
transferIfNeeded() {
// Move older elements behind the new one, then swap so output front is the top
while (this.outputQueue.length > 0) {
this.inputQueue.push(this.outputQueue.shift());
}
[this.inputQueue, this.outputQueue] = [this.outputQueue, this.inputQueue];
}
}
C#:
using System.Collections.Generic;
public class MyStack {
/// <summary>
/// Stack implementation using two queues
/// Time: O(n) push, O(1) pop/top/empty
/// Space: O(n)
/// </summary>
private Queue<int> inputQueue;
private Queue<int> outputQueue;
public MyStack() {
inputQueue = new Queue<int>();
outputQueue = new Queue<int>();
}
public void Push(int x) {
inputQueue.Enqueue(x);
TransferIfNeeded();
}
public int Pop() {
return outputQueue.Dequeue();
}
public int Top() {
return outputQueue.Peek();
}
public bool Empty() {
return inputQueue.Count == 0 && outputQueue.Count == 0;
}
private void TransferIfNeeded() {
// Move older elements behind the new one, then swap so output front is the top
while (outputQueue.Count > 0) {
inputQueue.Enqueue(outputQueue.Dequeue());
}
(inputQueue, outputQueue) = (outputQueue, inputQueue);
}
}
Complexity Analysis
- Time Complexity: O(n) for push, O(1) for pop, top and empty
- Space Complexity: O(n) for the two queues
Key Insights
- Two Queue Approach: Use input queue for push, output queue for pop/top
- Amortized Analysis: Transfer elements only when output queue is empty
- Lazy Transfer: Defer expensive operations until necessary
- LIFO Behavior: Maintain last-in-first-out order using queue operations
- Space Efficiency: Use two queues to simulate stack behavior
Edge Cases
- Empty Stack: All operations on empty stack
- Single Element: Stack with one element
- Multiple Operations: Mix of push, pop, top operations
- Large Input: Many consecutive push operations
- Alternating Operations: Push-pop-push-pop pattern
Follow-up Questions
- Implement Queue using Stacks: How would you implement a queue using stacks?
- Thread Safety: How would you make it thread-safe?
- Memory Management: How would you optimize memory usage?
- Performance: How would you optimize for high-frequency operations?
Common Mistakes
- Transfer Timing: Not transferring elements at the right time
- Queue Management: Incorrect queue operations
- Empty Check: Not properly checking for empty stack
- Order Maintenance: Not maintaining LIFO order correctly
Interview Tips
- Clarify Requirements: Ask about time complexity requirements
- Discuss Approaches: Mention both amortized and simple approaches
- Handle Edge Cases: Discuss empty stack and single element scenarios
- Explain Algorithm: Walk through the two-queue approach
- Consider Optimizations: Discuss space and time optimizations