Search tools and guides ⌘K
I · The linear primitives

Deque

Both ends, equally.

1972 · Don Knuth · TAOCP Vol. 1
The story

A queue that allows insert and delete at both ends: a "double-ended queue". Knuth catalogued it as the unifying abstraction over stacks and queues. C++ std::deque made it ubiquitous; Python collections.deque is the same idea in a single line.

How it works

Most efficient implementation is a sequence of fixed-size blocks linked in a list, with separate front and back pointers. Random access is O(1); both-end ops are O(1) amortised.

Where it lives

C++ STL deque. Sliding-window algorithms. Browser history. Work-stealing schedulers (each worker has a deque; thieves steal from the back, owner from the front).

The key insight

The work-stealing deque is the magic behind Java's ForkJoinPool, Go's scheduler, Rust's Rayon, .NET's TPL. One data structure, one paper, every modern parallel runtime.

More in The linear primitives
Array A row of equal-sized boxes. Dynamic array (vector) An array that grows itself. Linked list A chain you can splice. Stack Last in, first out. Queue First in, first out. Ring buffer A fixed-size queue that never allocates.
Across the cabinet
II Skip list Probabilistic balance, beautifully. II Trie (prefix tree) A tree you walk one character at a time. II Segment tree Range queries in logarithmic time. II Fenwick tree (BIT) Prefix sums, with constant tweaks. II Treap BST and heap, secretly the same tree. II Splay tree No metadata — and surprising amortised guarantees. III Hash table O(1), almost always. III Cuckoo hashing Two slots, no chains.
← All data structures