The queue data structure is a linear dynamic set of entities in a specific sequence. It can be modified by adding entities, at one end of the structure, and removing them from the other. Thus, a queue implements a FIFO policy (i.e., first-in, first-out). In other words, the first element added to the queue will be the first element to be removed.
In the queue, elements are added at the end of the sequence, and removed at the beginning. By convention, the end is also known as back, rear, or tail (we will stick to this term), and the beginning is known as front or head (we will stick to this term).
The queue has three main operations: insertion (i.e., enqueue), deletion (i.e., dequeue), and peek.
Unlike other structures, such as arrays or linked lists, the queue cannot be accessed via index (not even to search if the queue has a value). You would have to delete and get the element as many times as you need. However, this can be synthetically done with an auxiliary buffer to avoid modifications.
Queue Nodes
The following is the implementation of the Queue Node.
1class QueueNode {
2 constructor(value, next = null) {
3 this.value = value
4 this.next = next
5 }
6}
While you can perform certain operations using this data structure, you must be careful because accessing the queue elements is done via referencing the head node. As a result, the head accessor can be lost, or if many objects could reference a node that was supposed to be the head, it has changed.
1head = new QueueNode(1, new QueueNode(2, new QueueNode(3)));
2console.log("Head:\n", head);
3while(head){
4 head = head.next;
5}
6console.log("Head:\n", head);
1Head:
2 QueueNode {
3 value: 1,
4 next: QueueNode { value: 2, next: QueueNode { value: 3, next: null } }
5}
6Head:
7 null
To solve this nuance we can use a Queue wrapper that keeps track of the head and tail adding and removing elements in and out of the set.
The Queue (Wrapper)
Let’s use a basic implementation of the Queue wrapper to see how using it avoids losing track of the head unless we actually delete an element of the queue.
Note: I’ll be changing the Queue implementation to explain better, in a concise manner each operation. The full implementation of the QueueNode, the Queue, the QueueNode and Queue tests can be checked for further analysis.
1class BasicQueue {
2 constructor() {
3 this.head = null;
4 this.tail = null;
5 }
6
7 enqueue(value) {
8 const node = new QueueNode(value);
9
10 if (!this.head) {
11 this.head = node;
12 this.tail = node;
13
14 return this;
15 }
16
17 this.tail.next = node;
18 this.tail = node;
19
20 return this;
21 }
22
23 toString() {
24 const nodes = [];
25 let currentNode = this.head;
26 while (currentNode) {
27 nodes.push(currentNode.value);
28 currentNode = currentNode.next;
29 }
30 nodes.push('null');
31 return nodes.join('=>');
32 }
33}
Let’s test the previous case using this basic queue wrapper.
1queue = new BasicQueue()
2queue
3 .enqueue(1)
4 .enqueue(2)
5 .enqueue(3)
6 .enqueue(4)
7 .enqueue(5)
8
9console.log("Queue:\n", queue.toString(), "\n");
10head = queue.head;
11console.log("Head:\n", head);
12while(head){
13 head = head.next;
14}
15console.log("=== After losing head's track ===")
16console.log("Head:\n", head);
17console.log("Queue:\n", queue.toString(), "\n");
1Queue:
2 1=>2=>3=>4=>5=>null
3
4Head:
5 QueueNode {
6 value: 1,
7 next: QueueNode {
8 value: 2,
9 next: QueueNode { value: 3, next: [QueueNode] }
10 }
11}
12=== After losing head's track ===
13Head:
14 null
15Queue:
16 1=>2=>3=>4=>5=>null
Again, despite having lost track of the nodes in the head variable, the queue is still intact because the wrapper has the track of the head.
Operations
queue.enqueue
Enqueue is the insertion operation. The insertion occurs at the end of the queue. When the queue is empty the insertion adds a queue node and the wrapper tracks it in the head. As the node is the only element in the queue it has been tracked in the head but in the tail as well.
However, as more elements are enqueued to the set, the tail keeps pointing to the tail.
Enqueueing has $O(1)$ time complexity because the node is always added at the end of the queue.
queue.dequeue
Dequeue is the deletion operation. The deletion occurs at the beginning of the queue. When the queue is empty the deletion is not performed. On the other hand, when the queue has elements the head reference goes to its current next, and the head is returned to the caller. This has no impact on the tail reference.
Dequeueing has $O(1)$ time complexity too because the head reference is moved to the next node.
1class QueueWithEnqueueAndDequeue {
2 constructor() {
3 this.head = null;
4 this.tail = null;
5 }
6
7 enqueue(value) {
8 const node = new QueueNode(value);
9
10 if (!this.head) {
11 this.head = node;
12 this.tail = node;
13
14 return this;
15 }
16
17 this.tail.next = node;
18 this.tail = node;
19
20 return this;
21 }
22
23 dequeue() {
24 if (!this.head) return null;
25
26 let deletedNode = this.head;
27 if (this.head === this.tail) this.tail = null;
28 this.head = this.head.next;
29 this.size--;
30
31 return deletedNode;
32 }
33
34 toString() {
35 const nodes = [];
36 let currentNode = this.head;
37 while (currentNode) {
38 nodes.push(currentNode.value);
39 currentNode = currentNode.next;
40 }
41 nodes.push('null');
42 return nodes.join('=>');
43 }
44}
1queue = new QueueWithEnqueueAndDequeue()
2queue
3 .enqueue(1)
4 .enqueue(2)
5 .enqueue(3)
6 .enqueue(4)
7 .enqueue(5)
8
9
10console.log("Queue:\n", queue.toString(), "\n");
11queue.dequeue()
12console.log("Queue:\n", queue.toString(), "\n");
1Queue:
2 1=>2=>3=>4=>5=>null
3
4Queue:
5 2=>3=>4=>5=>null
queue.peek
The peek function looks at the head of the queue without popping it out from the queue. With this operation, we always have a way to look at the head value. No matter how many elements are enqueued, this operation will always look to the head.
1class QueueWithPeek {
2 constructor() {
3 this.head = null;
4 this.tail = null;
5 }
6
7 enqueue(value) {
8 const node = new QueueNode(value);
9
10 if (!this.head) {
11 this.head = node;
12 this.tail = node;
13
14 return this;
15 }
16
17 this.tail.next = node;
18 this.tail = node;
19
20 return this;
21 }
22
23 peek() {
24 if (!this.head) return null;
25
26 return this.head.value;
27 }
28}
1queue = new QueueWithPeek()
2queue
3 .enqueue(1)
4 .enqueue(2)
5 .enqueue(3)
6 .enqueue(4)
7 .enqueue(5)
8
9console.log("Peeking: ", queue.peek())
1Peeking: 1
Runtime Complexity Overview
| Operation | Runtime Complexity |
|---|---|
| Enqueue | $O(1)$ |
| Dequeue | $O(1)$ |
| Peek | $O(1)$ |
Space Complexity
Queues have $O(n)$ space complexity.