Deques

A double-ended queue supports constant-time insertion and removal at both ends, generalising both the stack and the queue.

Insertion at both ends

A deque, pronounced deck and short for double-ended queue, allows push and pop at both the front and the back, each in O(1). A stack uses one end; a queue uses one end for adding and the other for removing; a deque uses both ends freely, so it can act as either.

How it is built

The two usual implementations are a doubly linked list and a circular dynamic array. The linked-list version wires new nodes onto either the head or the tail. The array version keeps head and tail indices that wrap and grows by reallocation when full, much like a ring buffer that can extend.

• Push or pop front: O(1)
• Push or pop back: O(1)
• Access by index (array-backed): O(1)
• Insert or delete in the middle: O(n)

A worked use: sliding-window maximum

A classic application is finding the maximum of every window of width k in an array. A deque holds candidate indices in decreasing value order; as the window slides, indices that fall out of range are popped from the front and smaller values are popped from the back. Each index is pushed and popped at most once, giving O(n) total for the whole scan.

from collections import deque
def window_max(a, k):
    dq, out = deque(), []
    for i, x in enumerate(a):
        while dq and a[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(a[dq[0]])
    return out

When to use it

Choose a deque when an algorithm needs to add and drop items at both ends, as in sliding windows, work-stealing schedulers, and certain graph traversals. If only one end is ever used, a plain stack or queue is simpler.