Search tools and guides ⌘K
I · The linear primitives

Queue

First in, first out.

Pre-history · Implicit since punch-card machines
The story

Older than computer science. Every batch system since the 1940s queued jobs. The interesting question is the implementation: circular buffer, linked list, lock-free ring? Each has a different concurrency story.

How it works

Enqueue at tail, dequeue at head. Two pointers chase each other around a fixed buffer (ring) or grow as needed (linked).

Where it lives

Every web server's pending-request buffer. BFS. Print spoolers. OS scheduler runqueues. Kafka, RabbitMQ, NATS: at the bottom of every message broker.

The key insight

Lock-free queues (Michael-Scott 1996, LMAX Disruptor) are an entire research field. Adding concurrency turns "trivial" into a PhD topic.

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. Deque Both ends, equally. Ring buffer A fixed-size queue that never allocates.
Across the cabinet
II Heap (binary heap) A priority queue you can grep. 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.
← All data structures