Queue Implementation Using Two Stacks: Amortized O(1) Push and Pop
Problem Statement
Implement a First-In-First-Out (FIFO) queue using only two standard stacks.
The implemented queue must support `push(x)`, `pop()`, `peek()`, and `empty()`:
- `push x`: Pushes element x to the back of the queue (outputs `null`).
- `pop`: Removes and outputs the element from the front of the queue.
- `peek`: Outputs the element at the front of the queue without removing it.
- `empty`: Outputs `true` if the queue is empty, or `false` otherwise.
### Input Format
- First line contains an integer `n` (number of operations).
- The next `n` lines each contain an operation: `push <val>`, `pop`, `peek`, or `empty`.
### Output Format
- Print space-separated results corresponding to each operation.
### Constraints
- `1 <= n <= 1000`
- `pop` and `peek` are called only on non-empty queues.
Sample Cases
Example 1Sample Case
Input: 5
push 1
push 2
peek
pop
empty
Output: null null 1 1 false
Example 2Sample Case
Input: 5
push 10
push 20
pop
peek
empty
Output: null null 10 20 false
Example 3Sample Case
Input: 3
push 5
pop
empty
Output: null 5 true
Example 4Sample Case
Input: 3
push 42
peek
pop
Output: null 42 42
Constraints
Runtime Limit: 2000 ms per test batch
Memory Limit: 256 MB
Standard I/O stream reading
Official submissions are evaluated against hidden test cases on the server to verify time & memory complexity.