Data Structures
Lessons · #4 of 11

Queues

FIFO — fair order, every time

Queue · FIFO

head
tail 
init

Try it: Enqueue/dequeue on the belt. Flip to ring buffer to see how circular indexing reuses fixed memory — no shifts, ever.

Why it matters

Queues model waiting lines, task scheduling, and breadth-first exploration. Whenever order of arrival matters, you need a queue. They're fundamental to operating systems, networking, and graph algorithms.

The idea

Think of a line at a coffee shop. First person in line gets served first. New customers join at the back.

First In, First Out (FIFO).

Where stacks are about undoing and backtracking, queues are about fairness and order:

Enqueue (add to back) and dequeue (remove from front) are both O(1).

Key takeaways

Going deeper

Double-ended queues (deques) allow insertion/removal at both ends — useful for sliding-window algorithms and the monotonic-deque trick for "max in every window of size k" in O(n) total. Priority queues (covered in the heaps lesson) are "unfair" queues where importance trumps arrival order — generalize this lesson by one knob and you have a heap. Circular buffers implement queues efficiently in fixed-size arrays by wrapping around.

In the wild

Why the ring buffer is O(1) amortized — even though resize is O(n)

A naive array-backed queue dequeues from the front by shifting all n remaining elements left — O(n). The ring buffer dodges this with the modular indices you saw in the demo: front and rear advance modulo capacity, leaving no gaps to fill.

But what happens when the ring fills up? You allocate a new buffer of double the size and copy. That's O(n) — same resize trick the array doubling proof uses. Over n enqueues, total work is 2n − 1, so per-operation it's O(1) amortized. Without doubling — say you grew by a constant each time — total work would balloon to O(n²).

This is the second time you've seen the doubling pattern; you'll see it again in hash-table rehashing and implicitly in heap construction. Recognize the shape: "rare expensive op, paid for by many previous cheap ones" — that's amortized analysis in one sentence.

Math details

Time Complexity
Enqueue: O(1)
Dequeue: O(1)
Peek front: O(1)
Search: O(n)
Circular Buffer
front = (front + 1) mod capacity
rear = (rear + 1) mod capacity

Implementation

Queue with VecDeque

use std::collections::VecDeque;

let mut queue = VecDeque::new();

queue.push_back(1);  // Enqueue
queue.push_back(2);
queue.push_back(3);  // Queue: [1, 2, 3]

let front = queue.pop_front();  // Returns Some(1)
// Queue is now [2, 3]

Classic Applications

Practice

Three queue problems that each lean on a different facet of FIFO discipline:

→ Browse all practice problems