Deques

The log file you can rewind from both ends

Open a terminal and run tail -f on a busy log file. New lines appear at the bottom. The terminal holds the last thousand or so — older lines silently roll off the top. So far, that is just a queue with a bounded length. Now suppose you also want the slowest request in that window, live, updated as new lines come in. New lines at one end. Old lines at the other end. And a side computation that has to peek at — and sometimes drop from — both ends. A queue handles one end. The structure that handles both is a deque, and once you have seen it, you start seeing it everywhere: undo histories, browser tab caches, the work-stealing scheduler in Go's runtime, the LRU cache in front of every database. The queue from the last lesson handled one end. We are about to add the second one.

Symmetric ends, same buffer

A deque keeps the same circular buffer the queue used. The change is that both ends are now first-class: pushFront and pushBack both insert in O(1); popFront and popBack both remove in O(1). The two cursors — head and tail — still walk forward through the buffer, but each one now belongs to both a push and a pop, depending on which end you ask for.

class ArrayDeque<T> {
  buf = new Array(this.cap);
  head = 0; tail = 0; size = 0;
  constructor(public cap: number) {}
}

The visualiser starts with an empty 8-slot buffer. Watch what happens when we drive pushBack('A'), pushBack('B'), pushBack('C') — that is the queue-style pattern from last lesson. The tail cursor walks rightward; the head cursor stays at slot 0. Familiar. Then pushFront('Z') runs, and something new happens: head moves backward. The slot it was pointing at — slot 0 — has nothing to the left of it in the buffer, so the cursor wraps to the right end of the array, slot 7. Then the value Z lands in slot 7. The front of the deque now logically begins at slot 7 and runs Z, A, B, C rightward across the wrap.

That negative-direction movement is the new motion of this lesson. The queue's head only moved forward. The deque's head moves backward when you push at the front and forward when you pop the front. Two directions, one cursor, and the modulus that handles the wrap has to handle both.

The wrap formula reveals a JavaScript footgun that bites every from-scratch implementation once.

(-1) % 8 returning -1 is one of those quiet language details that does not bite until it bites. The fix is to add cap before the modulo: (head - 1 + cap) % cap. This is why the production code looks slightly more verbose than the queue's tail = (tail + 1) % cap — the front-end push has to defend against negative arithmetic.

Reading the live region

After a few mixed pushes the deque ends up in a state most beginners find unintuitive: head is at a high index, tail is at a low index, and the live elements occupy slots that wrap across the array boundary. Visually, two tinted regions on opposite ends of the row — physically split, logically continuous.

class ArrayDeque<T> {
  buf: (T | undefined)[];
  head = 0;
  tail = 0;
  size = 0;

  constructor(public cap: number) {
    this.buf = new Array(cap);
  }

  pushBack(v: T) {
    if (this.size === this.cap) this.grow();
    this.buf[this.tail] = v;
    this.tail = (this.tail + 1) % this.cap;
    this.size++;
  }

  pushFront(v: T) {
    if (this.size === this.cap) this.grow();
    this.head = (this.head - 1 + this.cap) % this.cap;
    this.buf[this.head] = v;
    this.size++;
  }

  popFront(): T | undefined {
    if (this.size === 0) return undefined;
    const v = this.buf[this.head];
    this.buf[this.head] = undefined;
    this.head = (this.head + 1) % this.cap;
    this.size--;
    return v;
  }

  popBack(): T | undefined {
    if (this.size === 0) return undefined;
    this.tail = (this.tail - 1 + this.cap) % this.cap;
    const v = this.buf[this.tail];
    this.buf[this.tail] = undefined;
    this.size--;
    return v;
  }
}

Look at the cursor moves. pushBack writes then advances tail. pushFront decrements head then writes. popFront reads then advances head. popBack decrements tail then reads. There is a pattern hiding in plain sight: pushes happen at the cursor's current position or one step away, and pops happen at the cursor's current position or one step away — depending on whether the cursor sits on the next-free slot (the back) or the next-occupied slot (the front).

That asymmetry trips beginners. Practising the four operations until each one is mechanical is the goal of this lesson — the structures further down the curriculum (monotonic deques, LRU caches, work-stealing schedulers) will assume you can predict the cursor moves without thinking.

The mental rule is: front and back move in opposite directions on push, and the same direction on pop. pushFront moves head backward; popFront moves head forward. pushBack moves tail forward; popBack moves tail backward. Both cursors end up on the next operation's position. That is the entire kinematic story.

When the buffer fills

Eventually the deque fills. With both ends pushing, the buffer reaches size === capacity faster than a one-ended queue would. The next push triggers a grow(): allocate a new buffer of double size, copy the live elements in, reset the cursors, throw the old buffer away.

The subtle part is the copy. The live region might span the wrap — the elements are scattered across the old array starting at head, running rightward until the end of the array, then continuing from slot 0 up to tail - 1. The new buffer has no wrap; it is empty and twice the size. The copy has to lay the elements out in logical order: the element under head becomes new slot 0, the next logical element becomes new slot 1, and so on, regardless of where they sat physically in the old buffer.

The watch-out is the modulus: the read indexes against the old capacity, not the new one. Double cap before the copy and the modulus will read past the live region into uninitialised slots, scrambling the queue. Copy in physical order instead of logical order and the elements come out shuffled — the logical front is no longer first. Both bugs are silent: nothing throws, the deque just starts returning the wrong values.

After grow finishes, head = 0 and tail = size. The wrap is gone — the live elements occupy slots 0 through size - 1 of the new buffer, contiguous and in order. The next pushFront will wrap head again as soon as it hits slot 0, and the cycle continues at twice the capacity.

The same name, two different complexities

Most languages ship a deque in their standard library. The interfaces look interchangeable. The implementations are not. Two production deques in particular are worth distinguishing, because reading code in one and porting it to the other is a quiet way to introduce an O(n) regression.

Java's ArrayDeque is a circular buffer — the structure the visualiser shows. Indexing into the middle of the deque is a single offset modulo capacity: buf[(head + i) & mask]. Constant time. This is what most beginners assume "deque" means.

Python's collections.deque is something different. Internally it is a doubly-linked list of fixed-size blocks, each holding 64 element pointers. Pushes and pops at either end are O(1) and almost always allocation-free — the block fills up before a new one is created. But indexing into the middle, d[500_000] on a million-element deque, has to chase blocks across the linked list. There is no constant-time offset. Python documents the complexity honestly: O(1) at the ends, O(n) in the middle. Most people do not read deeply enough to notice.

The reason collections.deque made this trade is cache locality without per-element allocation. A pure doubly-linked list allocates a node per element and chases pointers on every push. A pure circular buffer needs to grow, and the grow involves an O(n) copy. The block-list compromise allocates 64 elements at a time and amortises both costs. CPython's source (Modules/_collectionsmodule.c) calls out the 64 explicitly: "Larger numbers reduce the number of calls to the memory allocator, give faster indexing and rotation, and reduce the link-to-data overhead ratio." Block size 64 because it is a power of two; mod and div compile to bitmasks.

The takeaway is not that one implementation is right. The takeaway is that the complexity table for a deque depends on the implementation, and "deque" in the standard library tells you the interface, not the cost. If your inner loop indexes into the middle of a Python deque, you have written a quadratic loop without seeing it.

Where this shows up in real systems

Java's ArrayDeque is the recommended FIFO and LIFO structure on the JVM. The Java documentation flat-out says it is faster than Stack for stack workloads and faster than LinkedList for queue workloads — by something like 2× in the typical benchmark, because the array layout wins on every cache miss the linked structure would have taken. Spring Framework spent a release migrating remaining LinkedList uses to ArrayDeque for exactly this reason (spring-framework #25650).

The Linux kernel uses doubly-linked deques everywhere. The list_head macro in include/linux/list.h provides intrusive linkage — the prev and next pointers live inside the structures themselves, no separate node allocation. Process lists, scheduler runqueues, file descriptors, modules, network buffers. Anywhere you can insert and remove from either end in O(1) with no allocator overhead, the kernel reaches for list_head. The intrusive design is what makes the linked layout viable in this context — without per-insert allocation, the cache-miss cost shrinks.

The Go runtime's scheduler is a concurrent variant of the same idea. Each P (logical processor) owns a fixed-capacity local run queue treated as a deque (runtime/proc.go, look at runqput and runqgrab). The owning goroutine pushes and pops the head LIFO-style for cache locality. Stealing processors grab from the tail FIFO-style. Two ends, two access patterns, in the same buffer. Tokio, the Rust async runtime, uses a deque structurally identical to Go's — the Tokio docs note it directly. The pattern goes back to Cilk's 1995 work-stealing scheduler and David Chase and Yossi Lev's 2005 lock-free algorithm for the unbounded variant.

Closer to home, every IDE's "recently opened files" list, every browser's bounded back/forward navigation, every text editor's bounded undo stack — these are all deques. New entries push at one end, the oldest entries fall off the other end when the cap fills, and the user can also dismiss from the active end. Bounded history with both-ends access is exactly the deque shape.

Why a deque, not a stack and a queue

The natural question after seeing the four operations is: why not just use a stack and a queue, side by side, and pick whichever end you need? The answer is that the two interfaces look similar but the algorithms that demand a deque demand it for a specific reason — they push at one end while popping from the same end on a different element. That is a pop-while-pushing pattern that two separate structures cannot express.

The cleanest example is the next topic in the curriculum: the monotonic deque. In a sliding-window maximum, you maintain a deque of candidate indices — indices whose values might still be the maximum for some future window. When a new value arrives, you walk the deque from the back, dropping every candidate whose value is smaller than the new one (because the new value will dominate them as long as it is in the window). Then you push the new index at the back. Meanwhile, when the window slides, you drop indices from the front that have aged out of the window.

The frame above is one cycle of that maintenance — drop stale from the front, drop dominated from the back, push the new index. Notice that both pops happen in the same operation: a popBack while the same hand is mid-push, and a popFront against the other end. A queue cannot drop from the back. A stack cannot drop from the front. The pattern requires a single ordered structure where both ends support pop, simultaneously, in the same algorithmic step.

That is the closing thought of this lesson. The next lesson — monotonic deques in the intermediate tier — solves the sliding-window-maximum problem in full and shows the same pattern applied to half a dozen other windowed-max-style problems. For now: notice the shape. The deque is the structure that can drop something from the back while you are still pushing into the back. Once you see that move, you will see deques in every algorithm that needs it.

What to learn next

• Monotonic deques — the pattern teased above, solved in full, then applied to sliding-window maximum, the largest rectangle in a histogram, and the 0-1 BFS shortest-path variant.
• Heaps and priority queues — what "queue" means when you want max-or-min instead of FIFO. A heap is structurally a tree, not a buffer, and the operations are O(log n) rather than O(1).
• Trees, general — the next big jump in data-structure territory. Linked-list logic carries over; the layout becomes hierarchical instead of linear.