LeetCode Solutions Blog

Implement Queue using Stacks

Number: 232

Difficulty: Easy

Paid? No

Problem Description

Implement a first in first out (FIFO) queue using only two stacks. The queue should support push, pop, peek, and empty operations while only using standard stack operations such as push, pop, peek, and checking if empty. The implementation should also achieve an amortized O(1) time complexity for each operation.

Key Insights

Use two stacks:
- One (input stack) for enqueue operations.
- The other (output stack) for dequeue operations.
When performing pop or peek, if the output stack is empty, transfer all elements from the input stack to the output stack. This reversal makes the oldest element accessible.
Each element is moved at most once between the stacks, ensuring an amortized O(1) cost per operation.
The space complexity is O(n) where n is the number of elements in the queue.

Space and Time Complexity

Time Complexity: Amortized O(1) per operation Space Complexity: O(n)

Solution

We maintain two stacks: an input stack for pushing new elements and an output stack for popping or peeking the front element of the queue. When we need to access the front of the queue (either during a pop or peek), we check if the output stack is empty. If it is, we transfer all elements from the input stack to the output stack. This reversal of order allows us to simulate the FIFO nature of the queue. When performing a push, the element is simply added to the input stack.

Code Solutions

class MyQueue:
    def __init__(self):
        # Stack for enqueue operations.
        self.input_stack = []
        # Stack for dequeue operations.
        self.output_stack = []
    
    def push(self, x: int) -> None:
        # Always push new elements onto the input stack.
        self.input_stack.append(x)
    
    def pop(self) -> int:
        # Ensure the output stack has the current queue order.
        if not self.output_stack:
            while self.input_stack:
                # Move all elements from input_stack to output_stack.
                self.output_stack.append(self.input_stack.pop())
        # The top element of output_stack is the front of the queue.
        return self.output_stack.pop()
    
    def peek(self) -> int:
        # Ensure the output stack has the current queue order.
        if not self.output_stack:
            while self.input_stack:
                # Move all elements from input_stack to output_stack.
                self.output_stack.append(self.input_stack.pop())
        # Peek the top of output_stack without popping.
        return self.output_stack[-1]
    
    def empty(self) -> bool:
        # The queue is empty if both stacks are empty.
        return not self.input_stack and not self.output_stack