Queues
A queue is a linear data structure that handles items based on the order in which they are added. We add items to the back of the queue and remove items from the front, all in O(1) time. Queues operate in first-in-first-out (FIFO) order. The first item added (the one that has been in the queue the longest) is the first one that will be removed.
A queue data structure is exactly how we handle lines at stores. The first person (the one who has been waiting the longest) is going to be at the front of the line and will be helped first.
Cheat Sheet
| Big O Complexity | |
|---|---|
| enqueue | O(1) |
| dequeue | O(1) |
| peek | O(1) |
| space | O(n) |
- Fast Access at the EndsWe can add an item to the back and remove an item from the front in O(1) time.
- OrderedThe data is ordered where items added first are at the front and items added last are at the back.
- Slow LookupsTo access any item other than the front, it will take O(n) time to iterate through the queue and find it.
Queues in Interviews
- Build a stack using queues
- Task scheduling or ordering items
- Caching or storing some fixed number of items
Queues Explained
Queues are fundamental data structures to how we execute code, but they also easily map to real-world scenarios. Anytime we wait in line, we are behaving just like a queue — the first person who arrived will be helped first. Call centers function in the same manner. The operators handle calls based on who phoned in first.
Queues are utilized in programming in many ways:
- A CPU handling multiple processes and scheduling
- Events and message queues (ex. RabbitMQ, ZeroMQ, pub/sub)
- LRU Cache
- Fundamental to the JavaScript event loop
- Breadth-first search