The queue data structure is one of the simplest and most fundamental data structures and has a wide range of applications. Some more advanced data structures may use queues internally depending upon the implementation strategy. Having full knowledge and understanding of this fundamental data structure is important for any serious programmer or computer science student. In this article, we'll discuss some of the places queues are used, different ways we can implement queues and their benefits & drawbacks, and provide example queue implementations in multiple programming languages.
Queue
A queue is a sequence of items which can be modified by adding items to one end and removing items from the other end. This propery makes it a first in, first out (FIFO) data structure. In other words, once an item n is added to the queue, subsequent items which are added cannot themselves be removed until after n is removed. Queues have a wide variety of applications, including:
- Task management: in a system which manages when certain tasks should be executed, a queue can be used to help determine when tasks should be executed based on when they are requested.
- Printers and devices: since printers can only print one document at a time, the operating system can use a queue to hold subsequent requests until the printer is available to print more documents.
- Throttling API requests: an API server might throttle requests by implementing a queue to reduce its own system load.
- Graph traversals: queues can be used to facilitate breadth-first search within trees and graphs.
How to Implement a Queue
There are many ways in which a queue can be implemented. In the table below, we'll outline a few possible approaches, discuss their space and time complexity for different operations, and give some general notes. If you're not familiar with Big O notation: n represents the number of elements, O(n) means the operation takes n steps, and O(1) means the operation takes a small number of steps, regardless of how large n is.
Space | Enqueue | Dequeue | Notes | |
---|---|---|---|---|
Array | O(n) | O(1) | O(n) | Depending upon how the number of elements in the queue changes, the array may need to resize itself, thus causing potential slowdowns. |
Linked List with Tail Reference | O(n) | O(1) | O(1) | Items can be enqueued quickly if the linked list has an additional tail reference. |
Hybrid Approach | O(n) | O(1) | O(1) | Using links of fixed-size arrays can give a performance improvement over pure linked lists in queues with a large number of elements if implemented correctly. |
In the section below, we will implement a queue using a linked list. This will let us take advantage of the performant dequeue operation without getting into the complexity of any type of hybrid approach. If you are not familiar with linked lists, or would like to learn more about them, please visit our introduction to linked lists.
Coding a Queue with a Linked List
In this implementation, we will use two classes:
- Node: an encapsulation of a node in the linked list, which will store a value and the reference to the next item in the list.
- Queue: an encapsulation of the entire queue. This will hold a reference to the head and tail of the list to facilitate queue and dequeue operations.
When modifying the queue, we will need to make sure we update node references properly and handle any edge cases:
- Enqueue: when we add an item to the queue, we will update the tail so its next node points to a new node which encapsulates the value we're inserting. Then, we will replace the tail reference itself with that new node. If the list was empty before this insertion, we will instead set both the head and tail references to that new node.
- Dequeue: when we remove an item from the queue, we will get the value from the current head node, then update the head node to point to the next node in the sequence, thus removing the original head node.
We will also maintain a length property to keep track of how many items we have. This is not strictly necessary for a queue but can be beneficial in certain situations. The property will be incremented and decremented when items are added to and removed from the queue.
Coding a Queue with a Circular Buffer
If we have a queue which we know will have at most n items, we can use an array instead of a linked list. The array can be initialized to have a fixed size of n, and since we only have n items, we will never need to increase the size of the array afterwords. With some additional logic, we can implement a circular buffer to allow us to take advantage of the array's fast indexing. Furthermore, this structure will hold reference in a way that prevents the need for a shift operation on the internal array. For a detailed introduction with code examples, please visit our introduction below: