Stacks & Queues
Loading
Loading
Stacks & Queues
First in, first out — and the double-ended version that a window needs.
By the end of this chapter
Enqueue at the back, dequeue from the front. This is the shape of anything processed in arrival order: breadth-first search levels, request expiry, task scheduling.
A double-ended queue allows push and pop at both ends in constant time. That is what lets a sliding window discard stale items from the front while still pushing new candidates at the back.
from collections import deque live = deque()live.append(x) # push rightlive.appendleft(x) # push leftlive.pop() # pop rightlive.popleft() # pop left — O(1), unlike list.pop(0)Sign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: try 2 practice problems.