Data Structures. Queue

13 декабря 2023 г.

Basic information

This is a short expanded summary of the section about queues in the book Computer Science Guide by William Springer.

A queue is a sequential list where elements are added only to one end (enqueue) and removed from the other (dequeue). It follows the FIFO principle (First In, First Out).

A queue can be implemented as an array where the “front” moves along with the start of the queue, provided that the maximum number of elements never exceeds the array size.

A queue of unlimited length is better implemented using a doubly linked list.

Main operations

enqueue — add a new element to the end of the queue
dequeue — remove an element from the front of the queue
peek — read the front element without removing it

In JavaScript, arrays can already be used as queues thanks to methods like push() and shift().

The queue implementation using a linked list is based on the example from this website.

JavaScript

1class Queue {
2  constructor() {
3    this.linkedList = new LinkedList();
4  }
5 
6  isEmpty() {
7    return !this.linkedList.head;
8  }
9 
10  peek() {
11    if (!this.linkedList.head) {
12      return null;
13    }
14 
15    return this.linkedList.head.value;
16  }
17 
18  enqueue(value) {
19    this.linkedList.append(value);
20  }
21 
22  dequeue() {
23    const removedHead = this.linkedList.deleteHead();
24    return removedHead ? removedHead.value : null;
25  }
26}

Priority Queue

A priority queue can be implemented using various data structures, but the most efficient approach is to use a heap. In a priority queue, each element is assigned a numerical priority.

It supports the following operations:

Insert an element.
Extract the maximum (or minimum) element.

When extracting the minimum, the element with the smallest value has the highest priority. When extracting the maximum, the element with the largest value has the highest priority.

Below is an example implementation based on a min-heap:

JavaScript

1const comparator = (a, b) => a - b;
2
3class Heap {
4	constructor(comparator) {
5		this.arr = [];
6		this.comparator = comparator;
7	}
8
9	isCorrectOrder(first, second) {
10		return this.comparator(first, second) < 0;
11	}
12
13	getLeftChildIndex(parentIndex) {
14		return 2 * parentIndex + 1;
15	}
16
17	getRightChildIndex(parentIndex) {
18		return 2 * parentIndex + 2;
19	}
20
21	getParentIndex(childIndex) {
22		return Math.floor((childIndex - 1) / 2);
23	}
24
25	leftChild(parentIndex) {
26		return this.arr[this.getLeftChildIndex(parentIndex)];
27	}
28
29	rightChild(parentIndex) {
30		return this.arr[this.getRightChildIndex(parentIndex)];
31	}
32
33	parent(childIndex) {
34		return this.arr[this.getParentIndex(childIndex)];
35	}
36
37	hasParent(childIndex) {
38		return this.getParentIndex(childIndex) >= 0;
39	}
40
41	hasLeftChild(parentIndex) {
42		return this.getLeftChildIndex(parentIndex) < this.arr.length;
43	}
44
45	hasRightChild(parentIndex) {
46		return this.getRightChildIndex(parentIndex) < this.arr.length;
47	}
48
49	isEmpty() {
50		return !this.arr.length;
51	}
52
53	insert(item) {
54		this.arr.push(item);
55		this.heapifyUp();
56		return this;
57	}
58
59	heapifyUp(startIndex) {
60		let currentIndex = startIndex || this.arr.length - 1;
61
62		// While the element has a parent and its value is smaller than the parent's,
63        // swap the element with its parent.
64		while (
65			this.hasParent(currentIndex) &&
66			!this.isCorrectOrder(
67				this.parent(currentIndex),
68				this.arr[currentIndex]
69			)
70		) {
71			let parentIndex = this.getParentIndex(currentIndex);
72			this.swap(currentIndex, parentIndex);
73			currentIndex = parentIndex;
74		}
75	}
76
77	swap(indexOne, indexTwo) {
78		const tmp = this.arr[indexTwo];
79		this.arr[indexTwo] = this.arr[indexOne];
80		this.arr[indexOne] = tmp;
81	}
82
83	extractMin() {
84		if (this.arr.length === 0) {
85			return null;
86		}
87
88		if (this.arr.length === 1) {
89			return this.arr.pop();
90		}
91
92		const item = this.arr[0];
93
94		this.arr[0] = this.arr.pop();
95		this.heapifyDown();
96
97		return item;
98	}
99
100	heapifyDown(customStartIndex = 0) {
101		let currentIndex = customStartIndex;
102		let nextIndex = null;
103
104		while (this.hasLeftChild(currentIndex)) {
105			if (
106				this.hasRightChild(currentIndex) &&
107				this.isCorrectOrder(
108					this.rightChild(currentIndex),
109					this.leftChild(currentIndex)
110				)
111			) {
112				nextIndex = this.getRightChildIndex(currentIndex);
113			} else {
114				nextIndex = this.getLeftChildIndex(currentIndex);
115			}
116
117			if (
118				this.isCorrectOrder(this.arr[currentIndex], this.arr[nextIndex])
119			) {
120				break;
121			}
122
123			this.swap(currentIndex, nextIndex);
124			currentIndex = nextIndex;
125		}
126	}
127}
128
129const queue = new Heap(comparator);
130
131queue.insert(4)
132queue.insert(17)
133queue.insert(57)
134queue.insert(3)
135queue.insert(98)
136queue.insert(6)
137//[ 3, 4, 6, 17, 98, 57 ]
138queue.extractMin()
139//[ 4, 17, 6, 57, 98 ]
140