A queue composed of the letters a, b, c, and d. a is the first (rightmost) item, then b, then c, and then d.

Queue

Data Structure

Quick reference

Worst Case
space
enqueue
dequeue
peek

A queue stores items in a first-in, first-out (FIFO) order.

Picture a queue like the line outside a busy restaurant. First come, first served.

Loading...

Strengths:

  • Fast operations. All queue operations take time.

Uses

  • Breadth-first search uses a queue to keep track of the nodes to visit next.
  • Printers use queues to manage jobs—jobs get printed in the order they're submitted.
  • Web servers use queues to manage requests—page requests get fulfilled in the order they're received.
  • Processes wait in the CPU scheduler's queue for their turn to run.

Implementation

Queues are easy to implement with linked lists:

  • To enqueue, insert at the tail of the linked list.
  • To dequeue, remove at the head of the linked list.

You could implement a queue with an array or dynamic array, but it would get kinda messy. Try drawing it out. You'll notice that you'd need to build out a "scoot over" or "re-center" operation that automatically fires when your queue items hit the bottom edge of the array.

. . .