Implement Queue Operations Using Two Stacks
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Implement Queue Operations Using Two Stacks
Process a sequence of queue operations using exactly two LIFO stacks as the queue's internal data structures.
Each operation is an integer list:
- `[1, value]` enqueues `value`.
- `[2]` dequeues and returns the oldest queued value.
- `[3]` returns the oldest queued value without removing it.
Return the results of all dequeue and peek operations in order. The input is guaranteed not to dequeue or peek an empty queue. Do not use a queue, deque, linked list, or array front-removal operation internally.
## Function Signature
```python
def run_two_stack_queue(operations: list[list[int]]) -> list[int]:
...
```
## Constraints
- `0 <= len(operations) <= 500_000`
- `-1_000_000_000 <= value <= 1_000_000_000` for every enqueue operation.
- Every operation is one of the valid forms above.
- Aim for `O(1)` amortized time per operation and `O(q)` space for `q` queued values.
## Example
```text
Input: operations = [[1, 10], [1, 20], [3], [2], [1, 30], [2], [2]]
Output: [10, 10, 20, 30]
```
```text
Input: operations = []
Output: []
```
Quick Answer: Implement queue enqueue, dequeue, and peek operations using exactly two LIFO stacks. The challenge tests transfer invariants, output ordering, amortized O(1) reasoning, large operation sequences, empty input, and compliance with restrictions against queue-like shortcuts.