Stacks, queues, deques and ring buffers

Stacks are LIFO, queues FIFO, and deques support both ends. Stacks serve undo, bracket matching and explicit DFS. Queues serve BFS and ordered work intake; FIFO dequeue does not imply FIFO completion across concurrent workers.

A ring buffer wraps head/tail modulo capacity. Distinguish full and empty using a size counter, spare slot or generation bit. Specify overwrite, block or reject behaviour. Advancing a head index avoids shifting array contents.

A monotonic deque for sliding-window maxima discards smaller candidates that can no longer win. Each index enters and leaves at most once, so total cost is O(n) despite nested loops. This combines amortised analysis with an invariant. Test empty pops and capacity boundaries.

from collections import deque

def window_max(a, k):
    if not 1 <= k <= len(a):
        raise ValueError("invalid window")
    q, out = deque(), []
    for i, x in enumerate(a):
        while q and q[0] <= i-k: q.popleft()
        while q and a[q[-1]] <= x: q.pop()
        q.append(i)
        if i >= k-1: out.append(a[q[0]])
    return out
assert window_max([2,1,5,3], 3) == [5,5]