Queues and collections.deque
Push and pop from both ends fast.
First In, First Out
A queue serves items in the order they arrived, like a line at a shop. The first one in is the first one out.
Why Not Use a List
A list can pop from the front, but pop(0) is O(n) because every other item shifts left. That is too slow for big inputs.
q = []
q.pop(0) # O(n), avoid thisAll lessons in this course
- Stacks for Matching Brackets
- Monotonic Stack: Next Greater Element
- Queues and collections.deque
- Sliding Window Maximum with Deque