Implement Queue using Stacks

Problem Statement

You need to construct a First In First Out (FIFO) queue utilizing only two stacks. This custom queue class, named MyQueue, implements all traditional queue operations such as enqueueing (pushing) elements to the queue, previewing the front element (peek), dequeueing (popping) the front element, and checking if the queue is empty. To meet the challenge:

• push(int x) adds an element x at the end of the queue.
• pop() removes and returns the element at the front of the queue.
• peek() returns the front element without removing it.
• empty() checks if the queue is empty and returns a boolean accordingly.

The implementation must use only basic stack operations: push to top, pop from top, peek top, size, and empty check. If the language lacks native stacks, simulate them using lists or deques while adhering strictly to the allowed operations.

Examples

Example 1

Input:

["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

Output:

[null, null, null, 1, 1, false]

Explanation:

MyQueue myQueue = new MyQueue();
myQueue.push(1);      // queue is: [1]
myQueue.push(2);      // queue is: [1, 2]
myQueue.peek();       // returns 1
myQueue.pop();        // returns 1, queue becomes [2]
myQueue.empty();      // returns false

Constraints

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, peek, and empty
• All calls to pop and peek are valid (the queue will not be empty)

Approach and Intuition

A queue operates on a FIFO (First In First Out) principle, whereas a stack works in a LIFO (Last In First Out) manner. To implement a queue using only stacks, we use two stacks:

1. stack1 for enqueueing elements (push operation).
2. stack2 for dequeueing or peeking the front element.

Operations:

• push(x) – Always push onto stack1.
• pop() – If stack2 is empty, transfer all elements from stack1 to stack2 (reversing their order), then pop from stack2. If stack2 is not empty, just pop.
• peek() – Same logic as pop() but return the top of stack2 without removing it.
• empty() – Return true if both stack1 and stack2 are empty.

This dual-stack approach ensures that enqueue is efficient and dequeue honors the queue’s FIFO behavior by reversing order when needed. It's a classic exercise in structural transformation using simple building blocks.

Solutions

public int getFront() {
    if (!s2.isEmpty()) {
        return s2.peek();
    }
    return front;
}