Implement Queue using Stacks

Implement a queue using two stacks with O(1) amortized time complexity for all operations.

Language Selection

Choose your preferred programming language

Showing: Python

Implement Queue using Stacks

Problem Statement

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

void push(int x) Pushes element x to the back of the queue
int pop() Removes the element from the front of the queue and returns it
int peek() Returns the element at the front of the queue
boolean empty() Returns true if the queue is empty, false otherwise

Examples

Example 1:

Input:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

Output:
[null, null, null, 1, 1, false]

Explanation:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek();  // return 1
myQueue.pop();   // return 1, queue is [2]
myQueue.empty(); // return false

Constraints

1 <= x <= 9
At most 100 calls will be made to push, pop, peek, and empty
All the calls to pop and peek are valid

Approach 1: Two Stacks with Amortized O(1) (Optimal)

Algorithm

Use two stacks: one for input and one for output. Transfer elements from input to output only when output is empty.

Steps:

Use inputStack for push operations
Use outputStack for pop and peek operations
When output stack is empty, transfer all elements from input to output
This ensures amortized O(1) time complexity

Implementation

Python:

class MyQueue:
    """
    Queue implementation using two stacks
    Time: O(1) amortized for all operations
    Space: O(n)
    """
    
    def __init__(self):
        self.input_stack = []
        self.output_stack = []
    
    def push(self, x: int) -> None:
        """Push element x to the back of queue"""
        self.input_stack.append(x)
    
    def pop(self) -> int:
        """Remove element from front of queue and return it"""
        self._transfer_if_needed()
        return self.output_stack.pop()
    
    def peek(self) -> int:
        """Return element at front of queue"""
        self._transfer_if_needed()
        return self.output_stack[-1]
    
    def empty(self) -> bool:
        """Return true if queue is empty"""
        return len(self.input_stack) == 0 and len(self.output_stack) == 0
    
    def _transfer_if_needed(self):
        """Transfer elements from input to output stack if needed"""
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())

Java:

class MyQueue {
    /**
     * Queue implementation using two stacks
     * Time: O(1) amortized for all operations
     * Space: O(n)
     */
    
    private Stack<Integer> inputStack;
    private Stack<Integer> outputStack;
    
    public MyQueue() {
        inputStack = new Stack<>();
        outputStack = new Stack<>();
    }
    
    public void push(int x) {
        inputStack.push(x);
    }
    
    public int pop() {
        transferIfNeeded();
        return outputStack.pop();
    }
    
    public int peek() {
        transferIfNeeded();
        return outputStack.peek();
    }
    
    public boolean empty() {
        return inputStack.isEmpty() && outputStack.isEmpty();
    }
    
    private void transferIfNeeded() {
        if (outputStack.isEmpty()) {
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }
    }
}

Go:

type MyQueue struct {
    inputStack  []int
    outputStack []int
}

// Constructor - Initialize queue
func Constructor() MyQueue {
    return MyQueue{
        inputStack:  make([]int, 0),
        outputStack: make([]int, 0),
    }
}

// Push - Push element x to the back of queue
func (this *MyQueue) Push(x int) {
    this.inputStack = append(this.inputStack, x)
}

// Pop - Remove element from front of queue and return it
func (this *MyQueue) Pop() int {
    this.transferIfNeeded()
    top := this.outputStack[len(this.outputStack)-1]
    this.outputStack = this.outputStack[:len(this.outputStack)-1]
    return top
}

// Peek - Return element at front of queue
func (this *MyQueue) Peek() int {
    this.transferIfNeeded()
    return this.outputStack[len(this.outputStack)-1]
}

// Empty - Return true if queue is empty
func (this *MyQueue) Empty() bool {
    return len(this.inputStack) == 0 && len(this.outputStack) == 0
}

// transferIfNeeded - Transfer elements from input to output stack if needed
func (this *MyQueue) transferIfNeeded() {
    if len(this.outputStack) == 0 {
        for len(this.inputStack) > 0 {
            top := this.inputStack[len(this.inputStack)-1]
            this.inputStack = this.inputStack[:len(this.inputStack)-1]
            this.outputStack = append(this.outputStack, top)
        }
    }
}

JavaScript:

/**
 * Queue implementation using two stacks
 * Time: O(1) amortized for all operations
 * Space: O(n)
 */
class MyQueue {
    constructor() {
        this.inputStack = [];
        this.outputStack = [];
    }
    
    push(x) {
        this.inputStack.push(x);
    }
    
    pop() {
        this.transferIfNeeded();
        return this.outputStack.pop();
    }
    
    peek() {
        this.transferIfNeeded();
        return this.outputStack[this.outputStack.length - 1];
    }
    
    empty() {
        return this.inputStack.length === 0 && this.outputStack.length === 0;
    }
    
    transferIfNeeded() {
        if (this.outputStack.length === 0) {
            while (this.inputStack.length > 0) {
                this.outputStack.push(this.inputStack.pop());
            }
        }
    }
}

C#:

public class MyQueue {
    /// <summary>
    /// Queue implementation using two stacks
    /// Time: O(1) amortized for all operations
    /// Space: O(n)
    /// </summary>
    
    private Stack<int> inputStack;
    private Stack<int> outputStack;
    
    public MyQueue() {
        inputStack = new Stack<int>();
        outputStack = new Stack<int>();
    }
    
    public void Push(int x) {
        inputStack.Push(x);
    }
    
    public int Pop() {
        TransferIfNeeded();
        return outputStack.Pop();
    }
    
    public int Peek() {
        TransferIfNeeded();
        return outputStack.Peek();
    }
    
    public bool Empty() {
        return inputStack.Count == 0 && outputStack.Count == 0;
    }
    
    private void TransferIfNeeded() {
        if (outputStack.Count == 0) {
            while (inputStack.Count > 0) {
                outputStack.Push(inputStack.Pop());
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(1) amortized for all operations
Space Complexity: O(n) for the two stacks

Key Insights

Two Stack Approach: Use input stack for push, output stack for pop/peek
Amortized Analysis: Transfer elements only when output stack is empty
Lazy Transfer: Defer expensive operations until necessary
FIFO Behavior: Maintain queue order using stack operations
Space Efficiency: Use two stacks to simulate queue behavior

Edge Cases

Empty Queue: All operations on empty queue
Single Element: Queue with one element
Multiple Operations: Mix of push, pop, peek operations
Large Input: Many consecutive push operations
Alternating Operations: Push-pop-push-pop pattern

Follow-up Questions

Implement Stack using Queues: How would you implement a stack using queues?
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
Stack Management: Incorrect stack operations
Empty Check: Not properly checking for empty queue
Order Maintenance: Not maintaining FIFO order correctly

Interview Tips

Clarify Requirements: Ask about time complexity requirements
Discuss Approaches: Mention both amortized and simple approaches
Handle Edge Cases: Discuss empty queue and single element scenarios
Explain Algorithm: Walk through the two-stack approach
Consider Optimizations: Discuss space and time optimizations