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.
- 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
|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
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: