Data structures · foundation
Queue
A queue is a collection that adds elements at the back and removes them from the front, preserving first-in-first-out order.
Why it matters
Queues preserve arrival order in scheduling, buffering, message handling, and breadth-first traversal, making fairness and level order explicit.
Mental model
How to reason about queue
New work joins the tail and the head is served next. The structure separates arrival from service while retaining their order.
Analogy
Customers join the back of a checkout line and the customer waiting longest is served from the front.
Examples
See the boundary, not just the happy path
Worked example · Breadth-first frontier
queue.add(start); node = queue.removeFirst()Nodes discovered earlier are expanded earlier, which produces level-order traversal and shortest unweighted path distances.
Worked example · Bounded work buffer
producer -> queue(capacity=100) -> consumerThe capacity limits outstanding work and can force producers to wait or reject work when consumers fall behind.
Avoid · Costly array front removal
items.removeAt(0)In a contiguous dynamic array this may shift every remaining element. A deque or ring buffer supports efficient removal at the front.
Common mistakes
Misconceptions to remove early
Assuming FIFO implies completion order
A queue controls dequeue order. Multiple workers can finish jobs out of order unless completion is separately coordinated.
Leaving a queue unbounded
If producers outrun consumers, an unbounded queue converts overload into growing memory and latency. Define a capacity and overload policy.
Quick check
Can you predict the result?
1. After enqueueing A, B, and C, which item is dequeued first?
- • A
- • C
- • Whichever item is largest
2. What does a bounded queue add beyond FIFO ordering?
Keep building