โ† Expedia questions

Implement Queue with two stacks

Filed under Expedia

Free read 2 of 3

Confirm amortized time complexity expectations for the queue operations.

The question

Implement a first-in, first-out (FIFO) queue using only two stacks. The implemented queue should support all standard queue operations: push, peek/pop, and empty.

Constraints

  • At most 100 calls will be made to push, pop, peek, and empty.
  • All the calls to pop and peek are valid.

Examples

Input
["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Why
Queue instantiates, pushes 1 then 2. Peek returns 1. Pop removes and returns 1. Empty checks if queue is empty.

Approach

  1. Confirm amortized time complexity expectations for the queue operations.

Solution

O(1) amortized time per operation, O(N) space

Python
class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def pop(self) -> int:
        self.peek()
        return self.out_stack.pop()

    def peek(self) -> int:
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack[-1]

    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack

Tips

  • What they are testing: Test alternating push and pop operations to ensure amortized O(1) performance works correctly.
  • Common mistake: Unnecessarily transferring elements back and forth between stacks on every single push or pop operation.

Related Expedia questions

Collected from public candidate posts and coding forums. Updated Nov 2026.