Queues and Deques

What we're doing: Add and remove values from both ends of a deque, all in O(1).

from collections import deque

dq = deque([2, 3, 4])
dq.appendleft(1)
dq.append(5)
print(dq)
print(dq.popleft())
print(dq.pop())
print(dq)

4

appendleft(1) adds to the LEFT end — 1 becomes the new front, in O(1), with nothing shifted.

5

append(5) adds to the RIGHT end — 5 becomes the new back, also O(1).

deque([1, 2, 3, 4, 5])
1
5
deque([2, 3, 4])

Why this works: appendleft/append built [1, 2, 3, 4, 5] by growing both ends outward from [2, 3, 4]. popleft() then removes 1 (the front), and pop() removes 5 (the back), leaving the original [2, 3, 4] untouched in the middle.

What we're doing: Visit every node in a small graph breadth-first, using a deque as the queue.

from collections import deque

def bfs(graph, start):
    visited = {start}
    order = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order


graph = {'a': ['b', 'c'], 'b': ['d'], 'c': ['d'], 'd': []}
print(bfs(graph, 'a'))

6

'a' starts as both visited and the only item in the queue.

9

popleft() always takes the earliest-discovered node still waiting — the FIFO order that makes this breadth-first.

11

A neighbor is marked visited the moment it is discovered, before it is ever dequeued — this is what stops it from being queued a second time.

['a', 'b', 'c', 'd']

Why this works: 'a' is visited first, discovering 'b' and 'c'. Both are one step away, so both are fully processed — in the order they were discovered — before 'd', which is two steps away, gets its turn. That is exactly the breadth-first guarantee.

What we're doing: Enqueue and dequeue from a fixed-capacity circular queue, and watch a new value reuse a slot without shifting anything.

class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = [None] * capacity
        self.front = 0
        self.size = 0

    def enqueue(self, val):
        if self.size == self.capacity:
            raise OverflowError("queue is full")
        index = (self.front + self.size) % self.capacity
        self.data[index] = val
        self.size += 1

    def dequeue(self):
        val = self.data[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return val


cq = CircularQueue(3)
cq.enqueue('a')
cq.enqueue('b')
cq.enqueue('c')
print(cq.dequeue())
cq.enqueue('d')
print(cq.data)

10

(front + size) % capacity computes where the next value goes — it wraps back to index 0 once the array end is passed.

15

(front + 1) % capacity advances the front pointer the same way, so it wraps too.

a
['d', 'b', 'c']

Why this works: Dequeuing 'a' frees slot 0 without moving 'b' or 'c'. Enqueuing 'd' then computes index (front=1 + size=2) % 3 = 0 — 'd' lands directly in the freed slot 0, reusing it in place instead of appending to a growing array.

What we're doing: Find the maximum of every size-k window as it slides across an array, in one O(n) pass.

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # stores indices, values decreasing front to back
    for i, n in enumerate(nums):
        if dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] < n:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            yield nums[dq[0]]


print(list(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3)))

6

dq[0] <= i - k means the front index is at or before i - k — too old to be inside the current window [i - k + 1, i], so it is dropped.

8

Every back index with a smaller value than the incoming one is popped — it can never be reported as a max again, since something bigger and newer is right behind it.

[3, 3, 5, 5, 6, 7]

Why this works: The window [1, 3, -1] has max 3; sliding to [3, -1, -3] keeps max 3; [-1, -3, 5], [−3, 5, 3], [5, 3, 6] and [3, 6, 7] give 5, 5, 6, 7 in turn — six windows for an 8-element array with k=3, each read straight off the front of the deque.