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: []
```
Overview: 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.
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, as a list. Operations that only enqueue contribute nothing to the returned list, so an input with no dequeue and no peek returns an empty list. The input is guaranteed never to dequeue or peek an empty queue.
The intended approach is the classic two-stack construction: an input stack that receives every enqueue, and an output stack that serves dequeues and peeks, refilled by draining the input stack into it only when it runs empty. That gives `O(1)` amortized time per operation and `O(q)` space for `q` queued values. Do not use a queue, deque, linked list, or array front-removal operation internally. This console grades observable output only -- it cannot inspect which containers you used -- so treat the two-stack requirement as the stated expectation an interviewer would hold you to rather than as something the test suite checks.
## Function Signature
```python
def run_two_stack_queue(operations: list[list[int]]) -> list[int]:
...
```
## Example 1
```text
Input: operations = [[1, 10], [1, 20], [3], [2], [1, 30], [2], [2]]
Output: [10, 10, 20, 30]
```
Enqueue 10 and 20. Peek reports 10 without removing it. Dequeue removes and returns 10. Enqueue 30. The next two dequeues return 20 and then 30.
## Example 2
```text
Input: operations = []
Output: []
```
No operations at all, so nothing is dequeued or peeked and the result list is empty.
Constraints
- 0 <= len(operations) <= 500_000
- -1_000_000_000 <= value <= 1_000_000_000 for every enqueue operation
- Every operation is exactly one of [1, value], [2], or [3]
- The input never dequeues or peeks an empty queue
- Aim for O(1) amortized time per operation and O(q) space for q queued values
Examples
Input: ([],)
Expected Output: []
Input: ([[1, 5]],)
Expected Output: []
Hints
- A single stack reverses arrival order. Ask what happens to that order if the contents are poured into a second stack.
- The output stack only needs refilling when it is empty; refilling it while it still holds values would interleave old and new arrivals in the wrong order.
- Dequeue and peek differ by exactly one step, so they can share the same preparation work.