algoadvance

Leetcode 225. Implement Stack using Queues

Problem Statement

Design and implement a stack using queues. Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns that element.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

• You must use only standard operations of a queue – which means only enqueue to add an item to the back of the queue, dequeue to remove the front item of the queue, peek, and empty checks are allowed.
• You can use only one queue.

Clarifying Questions

1. Should the implementation handle special cases like pushing to an already full stack or popping an element from an empty stack?
2. Is there a constraint on the size of the number that can be pushed?
3. Should thread-safety be considered in this implementation?

Code

Here’s the Java implementation of a stack using a single queue:

import java.util.LinkedList;
import java.util.Queue;

class MyStack {

    private Queue<Integer> queue;

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

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

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

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

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

    public static void main(String[] args) {
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.top());    // returns 2
        System.out.println(stack.pop());    // returns 2
        System.out.println(stack.empty());  // returns false
    }
}

Strategy

1. Push Operation: Add the new element to the queue and then rotate the elements in the queue such that the new element is at the front (to imitate the behavior of a stack).
   • Queue before push: [1, 2]
   • Add 3: [1, 2, 3]
   • Rotate: [3, 1, 2]
2. Pop Operation: Remove the front element of the queue.
3. Top Operation: Peek at the front element of the queue.
4. Empty Operation: Check if the queue is empty.

This approach ensures that the most recently added element is always at the front of the queue, mimicking the LIFO (last-in, first-out) order of a stack.

Time Complexity

• Push: O(n) - Each push operation requires rotating the elements already present in the queue.
• Pop: O(1) - Directly removes the front element of the queue.
• Top: O(1) - Directly accesses the front element of the queue.
• Empty: O(1) - Simply checks if the queue is empty.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?