Implement Queue using Stacks

01 · Question

Implement a first in first out (FIFO) queue using only two stacks.

02 · Analysis

s1 holds incoming values; s2 exposes the oldest value at its top. Transfer s1 to s2 only when s2 is empty, or new arrivals would jump ahead of older ones. Each value is pushed into s1, moved once, and popped from s2 once: amortized O(1) per operation, O(n) space. One pop/peek may transfer n values and cost O(n). pop/peek require a nonempty queue. Test push 1, push 2, peek, push 3, then pop: it must return 1.

03 · Solution

Reference solution

1class MyQueue:
2    def __init__(self):
3        self.s1 = []
4        self.s2 = []
5
6    def push(self, x: int) -> None:
7        self.s1.append(x)
8
9    def pop(self) -> int:
10        self._move()
11        return self.s2.pop()
12
13    def peek(self) -> int:
14        self._move()
15        return self.s2[-1]
16
17    def empty(self) -> bool:
18        return not self.s1 and not self.s2
19
20    def _move(self) -> None:
21        if not self.s2:
22            while self.s1:
23                self.s2.append(self.s1.pop())

Evaluate Reverse Polish Notation