Skip to main content

DSAPath7 mincore

Queues

A queue is a first-in, first-out container. The earliest enqueued item is the first dequeued, which makes queues natural for BFS, scheduling, buffering, and producer-consumer systems.

Why This Matters

Queues model waiting order. Breadth-first search uses a queue so vertices are processed by increasing distance. Operating systems and services use queueing to absorb bursts; that same queue can also create latency when consumers fall behind.

Core Idea

A queue supports enqueue(x) at the back and dequeue() at the front.

OperationCost with ring buffer
enqueueamortized O(1)O(1)
dequeueO(1)O(1)
peek frontO(1)O(1)
searchO(n)O(n)

Worked example: in BFS, the start vertex enters the queue first. Its neighbors enter next, so all distance-1 vertices are processed before any distance-2 vertex.

Common Mistakes

  • Implementing queues with repeated front removal from a plain array. That shifts the whole suffix.
  • Using a queue for priority scheduling. If priorities matter, use a heap-backed priority queue.
  • Forgetting bounded queues. Production systems need backpressure when a queue grows too large.

Exercises

  • Trace a queue through enqueue(A), enqueue(B), dequeue(), enqueue(C).
  • Explain why BFS needs FIFO order.
  • Implement a fixed-size ring buffer.

Next Topics

References

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 10, 20.
  • Skiena. The Algorithm Design Manual (3rd ed., 2020). Ch. 5.