Leetcode: Implement Queue Using Stacks

Difficulty: Easy

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.

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.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Runtime Analysis:

Peek(): O(n)
Pop(): O(n)
Push(x): O(1)

Algorithmic Approach:

This question requires a basic understanding of Queues and Stacks. Queues are First In First Out Structures (FIFO) while Stacks are Last In First Out Structures (LIFO). When you use a Queue, you typically want to keep the original order of the elements added, visiting elements that you added first before elements that you added later. When you use a Stack, you want to reverse the order of elements added, visiting elements that you added last before elements that you added first.

Since the Stack reverses the order of elements added, using 2 Stacks will restore the original order. This is in essence to approach to solve this problem. We will use 2 Stacks to solve this Question: an "IN" Stack and an "OUT" Stack. 

When you:

1. Push(x): You simply add the element to a "IN" Stack.

2. Peek(x): Return the top element in the "OUT" Stack. If "OUT" Stack is empty, remove all elements in the "IN" Stack and push them to the "OUT" Stack (thus restoring the original order of elements), them simply return the top element.

3. Pop(x): Pop the top element in the "OUT" Stack. If "OUT" Stack is empty, remove all elements in the "IN" Stack and push them to the "OUT" Stack (thus restoring the original order of elements), them simply pop off the top element.

Java Code:

class MyQueue {
    
    Stack<Integer> in = new Stack();
    Stack<Integer> out = new Stack();
    
    // Push element x to the back of queue.
    public void push(int x) {
        in.push(x);
    }

    // Removes the element from front of queue.
    public void pop() {
        if(out.isEmpty()){
            while(!in.isEmpty()){
                out.push(in.pop());
            }
        }
        out.pop();
    }

    // Gets element from front of queue.
    public int peek() {
        if(out.isEmpty()){
            while(!in.isEmpty()){
                out.push(in.pop());
            }
        }
        
        return out.peek();
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}