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.
- Fast operations. All queue operations take time.
- 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.
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.