Resources:
- T. H. Cormen, Ed., Introduction to algorithms, 3. ed. Cambridge, Mass.: MIT Press, 2009.
- M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Data structures and algorithms in Java, 6. ed. Hoboken, NJ: Wiley, 2014.
Queues are one of the most intuitive and widely used data structures in computer science. If you’ve ever waited in line at a coffee shop, ticket counter, or printer, you’ve already experienced a queue in real life!
What is a Queue?
A queue is an abstract data type that follows the FIFO principle – First In, First Out.
- The first element added to the queue is the first one to be removed.
- New elements are added at the rear (also called back or tail).
- Elements are removed from the front (also called head).
Think of it as a line of people:
The person who arrived first (at the front) gets served first. New arrivals join at the back.
Core Operations of a Queue
Most queue implementations support these four fundamental operations:
https://www.geeksforgeeks.org/dsa/basic-operations-for-queue-in-data-structure/
- Enqueue (add an element to the rear)
- Dequeue (remove and return the element from the front)
- Front / Peek (view the front element without removing it)
- isEmpty (check if the queue is empty)
2. Types of Queues
Not all queues are simple lines. Depending on the problem you’re solving, you might need a specialized version:
https://bytebytego.com/guides/explaining-the-4-most-commonly-used-types-of-queues-in-a-single-diagram/
- Simple Queue: Standard FIFO behavior.
- Circular Queue: The last position is connected back to the first, making it efficient for memory reuse.
- Priority Queue: Elements are dequeued based on priority rather than arrival time (common in hospital ERs or OS scheduling).
- Deque (Double-Ended Queue): Elements can be added or removed from both the front and the rear.
3. Complexity Analysis
Queues are highly efficient for their primary purpose. When implemented using an array or a linked list, the time complexities are:
https://www.oreilly.com/library/view/mastering-high-performance/9781788996648/b15f9f5a-94dd-493b-9385-19f4ac23cdca.xhtml
| Operation | Time Complexity |
| Enqueue | O(1) |
| Dequeue | O(1) |
| Peek | O(1) |
| Space | O(n) |