2017-09-28 10:52:12 -04:00
|
|
|
/* Queue
|
2023-10-03 23:08:19 +02:00
|
|
|
* A Queue is a data structure that allows you to add an element to the end of
|
|
|
|
|
* a list and remove the item at the front. A queue follows a FIFO (First In First Out)
|
|
|
|
|
* system, where the first item to enter the queue is the first to be removed,
|
|
|
|
|
* All these operation complexities are O(1).
|
|
|
|
|
* This implementation following the linked list structure.
|
|
|
|
|
*/
|
2017-09-28 10:52:12 -04:00
|
|
|
|
2021-11-25 10:18:26 +05:30
|
|
|
class Queue {
|
2022-05-06 22:20:55 +06:00
|
|
|
#size
|
|
|
|
|
|
2023-10-03 23:08:19 +02:00
|
|
|
constructor() {
|
2022-05-06 22:20:55 +06:00
|
|
|
this.head = null
|
|
|
|
|
this.tail = null
|
|
|
|
|
this.#size = 0
|
|
|
|
|
|
|
|
|
|
return Object.seal(this)
|
2018-03-30 16:03:13 +02:00
|
|
|
}
|
2017-09-28 10:52:12 -04:00
|
|
|
|
2023-10-03 23:08:19 +02:00
|
|
|
get length() {
|
2022-05-06 22:20:55 +06:00
|
|
|
return this.#size
|
2020-05-03 09:05:12 +02:00
|
|
|
}
|
2017-09-28 10:52:12 -04:00
|
|
|
|
2022-05-06 22:20:55 +06:00
|
|
|
/**
|
|
|
|
|
* @description - Add a value to the end of the queue
|
|
|
|
|
* @param {*} data
|
|
|
|
|
* @returns {number} - The current size of queue
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
enqueue(data) {
|
2022-05-06 22:20:55 +06:00
|
|
|
const node = { data, next: null }
|
|
|
|
|
|
|
|
|
|
if (!this.head && !this.tail) {
|
|
|
|
|
this.head = node
|
|
|
|
|
this.tail = node
|
|
|
|
|
} else {
|
|
|
|
|
this.tail.next = node
|
|
|
|
|
this.tail = node
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
return ++this.#size
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
* @description - Removes the value at the front of the queue
|
|
|
|
|
* @returns {*} - The first data of the queue
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
dequeue() {
|
2022-05-06 22:20:55 +06:00
|
|
|
if (this.isEmpty()) {
|
2020-05-03 21:26:52 -03:00
|
|
|
throw new Error('Queue is Empty')
|
2017-09-28 10:52:12 -04:00
|
|
|
}
|
|
|
|
|
|
2022-05-06 22:20:55 +06:00
|
|
|
const firstData = this.peekFirst()
|
|
|
|
|
|
|
|
|
|
this.head = this.head.next
|
|
|
|
|
|
|
|
|
|
if (!this.head) {
|
|
|
|
|
this.tail = null
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
this.#size--
|
|
|
|
|
|
|
|
|
|
return firstData
|
2020-05-03 09:05:12 +02:00
|
|
|
}
|
2017-09-28 10:52:12 -04:00
|
|
|
|
2022-05-06 22:20:55 +06:00
|
|
|
/**
|
|
|
|
|
* @description - Return the item at the front of the queue
|
|
|
|
|
* @returns {*}
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
peekFirst() {
|
2022-05-06 22:20:55 +06:00
|
|
|
if (this.isEmpty()) {
|
|
|
|
|
throw new Error('Queue is Empty')
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
return this.head.data
|
2020-05-03 09:05:12 +02:00
|
|
|
}
|
2017-09-28 10:52:12 -04:00
|
|
|
|
2022-05-06 22:20:55 +06:00
|
|
|
/**
|
|
|
|
|
* @description - Return the item at the tail of the queue
|
|
|
|
|
* @returns {*}
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
peekLast() {
|
2022-05-06 22:20:55 +06:00
|
|
|
if (this.isEmpty()) {
|
2021-11-25 10:18:26 +05:30
|
|
|
throw new Error('Queue is Empty')
|
|
|
|
|
}
|
|
|
|
|
|
2022-05-06 22:20:55 +06:00
|
|
|
return this.tail.data
|
2020-05-03 09:05:12 +02:00
|
|
|
}
|
2017-09-28 10:52:12 -04:00
|
|
|
|
2022-05-06 22:20:55 +06:00
|
|
|
/**
|
|
|
|
|
* @description - Return the array of Queue
|
|
|
|
|
* @returns {Array<*>}
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
toArray() {
|
2022-05-06 22:20:55 +06:00
|
|
|
const array = []
|
|
|
|
|
let node = this.head
|
|
|
|
|
|
|
|
|
|
while (node) {
|
|
|
|
|
array.push(node.data)
|
|
|
|
|
node = node.next
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
return array
|
2020-05-03 09:05:12 +02:00
|
|
|
}
|
2018-03-30 16:03:13 +02:00
|
|
|
|
2022-05-06 22:20:55 +06:00
|
|
|
/**
|
2023-10-03 23:08:19 +02:00
|
|
|
* @description - Return is queue empty or not
|
|
|
|
|
* @returns {boolean}
|
|
|
|
|
*/
|
|
|
|
|
isEmpty() {
|
2022-05-06 22:20:55 +06:00
|
|
|
return this.length === 0
|
2021-11-25 10:18:26 +05:30
|
|
|
}
|
|
|
|
|
}
|
2017-09-28 10:52:12 -04:00
|
|
|
|
2022-05-06 22:20:55 +06:00
|
|
|
export default Queue
|
