Implement Queue using Stacks

Implement Queue using Stacks

Implement a first-in-first-out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue: push, pop, peek, and empty.

Implement the MyQueue class:

• push(x): Pushes element x to the back of the queue.
• pop(): Removes the element from the front of the queue and returns it.
• peek(): Returns the element at the front of the queue without removing it.
• empty(): Returns true if the queue is empty, false otherwise.

Notes:

• You must use only standard stack operations: push to top, pop from top, peek at top, size, and is empty.
• Assume all operations are valid (e.g., no pop or peek on an empty queue).

Examples

Example 1:

Input:
  push(1), push(2), peek(), pop(), empty()
Output:
  null, null, 1, 1, false
Explanation:
  MyQueue queue = new MyQueue();
  queue.push(1); // queue is: [1]
  queue.push(2); // queue is: [1, 2]
  queue.peek();  // return 1
  queue.pop();   // return 1, queue is: [2]
  queue.empty(); // return 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.

Expected Complexity

• Time: O(1) amortized per operation
• Space: O(n)