LeetCode 225 Implement Stack using Queues - Two Solutions (Easy, Java, O(n))

LeetCode 225. Implement Stack using Queues This post compares two solutions for LeetCode problem 225, which involves implementing a stack using queues. The first solution uses a single queue with O(n) push and O(1) pop/top operations, while the second uses two queues for O(1) push and O(n) pop/top operations. Below, we summarize their time complexities in a table and provide the full code for each.

Problem Overview

We need to implement a stack with:

• push(x): Add an element to the top of the stack.
• pop(): Remove and return the top element.
• top(): Return the top element without removing it.
• empty(): Check if the stack is empty.

Queues operate on FIFO (First In, First Out), so we must manipulate them to achieve LIFO (Last In, First Out) stack behavior.

Time Complexity Comparison

The following table compares the time complexities of the two solutions for each operation, where n is the number of elements in the stack:

• Single-Queue Solution: Rotates the queue after each push to keep the newest element at the front, making push O(n) but pop and top O(1). Space complexity is O(n).
• Two-Queue Solution: Adds elements directly to one queue (O(1) push), but moves elements between queues for pop and top (O(n)). Space complexity is O(n) but requires two queues.

When to Use Each

• Single-Queue: Preferred for simplicity, lower space usage (one queue), and when pop/top operations are frequent.
• Two-Queue: Ideal when push operations are frequent, as they are O(1), but requires more space (two queues).

Solution 1: Single-Queue Implementation

This solution uses one LinkedList as a queue, rotating elements after each push to ensure the newest element is at the front.

Code

class MyStack {
    private Queue<Integer> queue;

    public MyStack() {
        this.queue = new LinkedList<Integer>();
    }

    public void push(int x) {
        this.queue.add(x);
        for (int i = 1; i < queue.size(); i++) {
            queue.add(queue.remove());
        }
    }

    public int pop() {
        int res = queue.peek();
        queue.remove();
        return res;
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

Explanation

• Push: Adds the element to the queue and rotates the queue by re-adding all other elements to the end, placing the newest element at the front (O(n)).
• Pop: Removes and returns the front element (O(1)).
• Top: Returns the front element without removing it (O(1)).
• Empty: Checks if the queue is empty (O(1)).
• The rotation in push ensures the queue's front always holds the stack's top, mimicking LIFO behavior.

Usage Example

MyStack obj = new MyStack();
obj.push(1);       // Stack: [1]
obj.push(2);       // Stack: [2, 1]
System.out.println(obj.top());    // Output: 2
System.out.println(obj.pop());    // Output: 2, Stack: [1]
System.out.println(obj.empty());  // Output: false
obj.pop();         // Stack: []
System.out.println(obj.empty());  // Output: true

Solution 2: Two-Queue Implementation

This solution uses two LinkedList queues. Elements are pushed to one queue, and for pop/top, elements are moved to the second queue to access the most recent one.

Code

class MyStack {
    private Queue<Integer> q1;
    private Queue<Integer> q2;

    public MyStack() {
        this.q1 = new LinkedList<>();
        this.q2 = new LinkedList<>();
    }

    public void push(int x) {
        q1.add(x);
    }

    public int pop() {
        while (q1.size() > 1) {
            q2.add(q1.remove());
        }
        int res = q1.remove();
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
        return res;
    }

    public int top() {
        while (q1.size() > 1) {
            q2.add(q1.remove());
        }
        int res = q1.peek();
        q2.add(q1.remove());
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
        return res;
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

Explanation

• Push: Adds the element to q1 (O(1)).
• Pop: Moves all but the last element from q1 to q2, removes and returns the last element, then swaps q1 and q2 (O(n)).
• Top: Similar to pop, but preserves the last element by moving it to q2 before swapping (O(n)).
• Empty: Checks if q1 is empty (O(1)).
• The queue swapping ensures q1 remains the primary storage, with q2 empty after each pop/top.

Usage Example

MyStack obj = new MyStack();
obj.push(1);       // Stack: [1]
obj.push(2);       // Stack: [2, 1]
System.out.println(obj.top());    // Output: 2
System.out.println(obj.pop());    // Output: 2, Stack: [1]
System.out.println(obj.empty());  // Output: false
obj.pop();         // Stack: []
System.out.println(obj.empty());  // Output: true

Conclusion

• Single-Queue: Simpler, uses less space, and is efficient for pop/top-heavy workloads.
• Two-Queue: Optimizes for push-heavy workloads but requires more space and has slower pop/top operations. Choose based on the expected operation frequency and space constraints. Both solutions effectively implement a stack using queues, meeting all problem requirements.