Implement Queue Using Stacks - Leetcode Solution

Problem Statement:

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false

Solution:

We can use two stacks to implement a queue. We will call them "input" and "output". The idea is to push the elements into the "input" stack while the "output" stack is empty. When we need to perform an operation such as pop or peek, we will move the elements from the "input" stack to the "output" stack so that the first element that was pushed into the "input" stack will be at the top of the "output" stack, which will be the first element to be popped or peeked.

The following is the implementation of the MyQueue class:

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

/** Initialize your data structure here. */
public MyQueue() {
    input = new Stack<>();
    output = new Stack<>();
}

/** Push element x to the back of queue. */
public void push(int x) {
    input.push(x);
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
    peek();
    return output.pop();
}

/** Get the front element. */
public int peek() {
    if (output.isEmpty()) {
        while (!input.isEmpty()) {
            output.push(input.pop());
        }
    }
    return output.peek();
}

/** Returns whether the queue is empty. */
public boolean empty() {
    return input.isEmpty() && output.isEmpty();
}

}

Explanation:

• In the constructor, we initialize the "input" and "output" stacks.
• The push operation is simple. We just need to push the element into the "input" stack.
• The pop operation needs the first element of the queue to be removed and returned. To do this, we first call the peek operation to move the elements from the "input" stack to the "output" stack. Then, we pop the top element from the "output" stack and return it.
• The peek operation is similar to the pop operation. We call this operation to move the elements from the "input" stack to the "output" stack, and then return the top element from the "output" stack.
• The empty operation checks if both "input" and "output" stacks are empty. If they are, the queue is considered empty.

The time complexity for push, pop, peek and empty operations is O(1). The space complexity is O(n), where n is the number of elements in the queue.

1