Implement Queue using Stacks

Problem Description

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.

Notes:

• You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.

Examples

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.

Inversion Stack with Amortized Cost

To implement a FIFO queue using two stacks, we split operations into input and output stacks.

1. When pushing an element, push it directly onto the input stack.
2. When popping or peeking, if the output stack is empty, pop all elements from the input stack and push them onto the output stack. This reverses their order, bringing the oldest elements to the top.
3. Pop or peek from the output stack. This amortizes the time complexity of all operations to O(1), since each element is pushed and popped a fixed number of times.

Solution 1: Input and Output Stacks

Divide operations between an input stack and a lazy output inversion stack.

import java.util.Stack;

class MyQueue {
    private Stack<Integer> input;
    private Stack<Integer> output;

    public MyQueue() {
        input = new Stack<>();
        output = new Stack<>();
    }

    public void push(int x) {
        input.push(x);
    }

    public int pop() {
        peek(); // ensure output stack is populated
        return output.pop();
    }

    public int peek() {
        if (output.isEmpty()) {
            while (!input.isEmpty()) {
                output.push(input.pop());
            }
        }
        return output.peek();
    }

    public boolean empty() {
        return input.isEmpty() && output.isEmpty();
    }
}

class MyQueue:
    def __init__(self):
        self.input = []
        self.output = []

    def push(self, x: int) -> None:
        self.input.append(x)

    def pop(self) -> int:
        self.peek()  # ensure output stack is populated
        return self.output.pop()

    def peek(self) -> int:
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())
        return self.output[-1]

    def empty(self) -> bool:
        return not self.input and not self.output

#include <stack>

class MyQueue {
private:
    std::stack<int> input;
    std::stack<int> output;

public:
    MyQueue() {}

    void push(int x) {
        input.push(x);
    }

    int pop() {
        peek(); // ensure output stack is populated
        int val = output.top();
        output.pop();
        return val;
    }

    int peek() {
        if (output.empty()) {
            while (!input.empty()) {
                output.push(input.top());
                input.pop();
            }
        }
        return output.top();
    }

    bool empty() {
        return input.empty() && output.empty();
    }
};

Complexity Analysis

• Time Complexity: push and empty take O(1) time. pop and peek take O(1) amortized time, since elements are moved between stacks at most once.
• Space Complexity: O(n) auxiliary space to store elements in the two stacks.

Where It Breaks

If we perform a sequence that repeatedly alternates between pushing and popping from an empty output stack with single items, it doesn’t break the amortized bounds because each item only shifts once.

Common Mistakes

• Incorrect inversion timing: Inverting the input stack on every push operation, which destroys the FIFO ordering and degrades performance to O(n) per push.
• Forgetting to check both stacks: Checking only one stack in the empty check, which ignores elements stored in the other stack.

Frequently Asked Questions

Why is pop/peek amortized O(1)? An element is pushed to input stack once, popped from input stack once, pushed to output stack once, and popped from output stack once. Across the lifespan of the queue, the total operations per element is 4, which averages out to O(1) per call.

Can we implement this with only one stack? No, a single stack cannot reverse elements to achieve FIFO behavior without allocating recursive calls on the runtime stack, which still uses O(n) stack memory.

← All Problems