Interview Cheat Sheets | Queues Cheat Sheet
December 28th, 2023
Introduction to Queues
A queue, a linear collection, follows the First In, First Out (FIFO) principle, allowing element addition at one end (enqueue) and removal from the other end (dequeue). As an abstract data type, queues can be implemented using arrays or singly linked lists. Queues are vital for applications like breadth-first search.
Implementations
| Language | API |
|---|
| C++ | std::queue |
| Java | java.util.Queue (use java.util.ArrayDeque) |
| Python | queue |
| JavaScript | N/A |
Time Complexity
| Operation | Big-O |
|---|
| Enqueue/Offer | O(1) |
| Dequeue/Poll | O(1) |
| Front | O(1) |
| Back | O(1) |
| isEmpty | O(1) |
Things to Look Out for During Interviews
- Beware of using arrays (JavaScript) as a queue without a built-in Queue class, as the dequeue operation can be
O(n) due to element shifting.
Corner Cases
- Empty queue
- Queue with one item
- Queue with two items
Essential Questions
- Implement Stack using Queues
Recommended Practice Questions
- Implement Queue using Stacks - My solution
- Design Circular Queue