Katkat
Back

Implement Queue Operations Using Two Stacks

OracleSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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

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

Input: operations = [[1, 10], [1, 20], [3], [2], [1, 30], [2], [2]]
Output: [10, 10, 20, 30]

Input: operations = []
Output: []