Implement a Queue using Stacks

Queues and Stacks are fundamental data structures that organize data differently: Stacks follow a Last-In, First-Out (LIFO) principle, while Queues adhere to a First-In, First-Out (FIFO) principle. This classic challenge tests your understanding of these core data structures and your ability to adapt one's behavior using the primitives of another, offering valuable insight into low-level data structure mechanics and resource-constrained problem-solving.

Problem Description

You are tasked with implementing a MyQueue class that provides the standard queue operations: push, pop, peek, and empty. The critical constraint is that you must achieve this using only two standard stack data structures internally. You are not allowed to use any other built-in queue data structure, lists, or similar complex collections.

Your MyQueue class should support the following operations:

• MyQueue(): Initializes an empty queue instance.
• push(x): Adds element x to the rear of the queue.
• pop(): Removes and returns the element from the front of the queue.
• peek(): Returns the element at the front of the queue without removing it.
• empty(): Returns true if the queue is empty, false otherwise.

You should assume that a standard stack data structure provides the following common operations:

• push(item): Adds an item to the top of the stack.
• pop(): Removes and returns the item at the top of the stack.
• peek(): Returns the item at the top of the stack without removing it (often called top).
• isEmpty(): Returns true if the stack contains no elements, false otherwise.
• size(): Returns the number of elements in the stack.

The implementation should strive for optimal time complexity for all operations, particularly considering amortized constant time for most.

Examples

Example 1:

Input:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();   // returns 1
queue.pop();    // returns 1
queue.empty();  // returns false

Explanation:

1. MyQueue(): Initializes an empty queue.
2. queue.push(1): The queue now conceptually holds [1].
3. queue.push(2): The queue now conceptually holds [1, 2].
4. queue.peek(): The front element of the queue is 1. This operation returns 1.
5. queue.pop(): The front element 1 is removed and returned. The queue now conceptually holds [2].
6. queue.empty(): The queue is not empty (it contains 2), so it returns false.

Example 2:

Input:
MyQueue queue = new MyQueue();
queue.push(10);
queue.push(20);
queue.pop(); // returns 10
queue.push(30);
queue.peek(); // returns 20
queue.pop(); // returns 20
queue.pop(); // returns 30
queue.empty(); // returns true

Explanation:

1. MyQueue(): Initializes an empty queue.
2. queue.push(10): Queue: [10]
3. queue.push(20): Queue: [10, 20]
4. queue.pop(): Returns 10. Queue: [20]
5. queue.push(30): Queue: [20, 30]
6. queue.peek(): Returns 20. Queue: [20, 30]
7. queue.pop(): Returns 20. Queue: [30]
8. queue.pop(): Returns 30. Queue: []
9. queue.empty(): Returns true, as the queue is now empty.

Constraints

• 1 <= x <= 9 for any element x pushed into the queue.
• At most 100 calls will be made to push, pop, peek, and empty in total.
• All calls to pop and peek are guaranteed to be made when the queue is not empty.
• You are only allowed to use the standard stack operations: push, pop, peek, isEmpty, and size.

Notes

• Consider how a stack's LIFO property can be strategically manipulated to simulate FIFO behavior. This commonly involves using a second stack to reverse the order of elements when necessary.
• Think about the time complexity for each operation. Some operations might take O(N) in the worst case, but can they be designed to have an amortized O(1) time complexity over a sequence of operations?
• Focus on maintaining the correct conceptual order of elements for pop and peek operations, ensuring they always return the front element of the queue, just as a true queue would.
• The goal is to strictly implement the queue interface using only stack operations. Avoid introducing any temporary arrays, lists, or other data structures beyond the two required stacks.