Interview Cake
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.
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.
See also:
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
