A priority queue does not work on First in First Out principle rather it returns item with highest priority.
We will be designing a priority queue in which we add elements to the queue according to its priority(ie;first item in queue has highest priority)
Properties of our Priority Queue
1.Each item has a priority number associated with it.
2.Items added to queue as per their priority.
3.Items with lowest priority numbers are removed first(first item in queue).
Implementations
1.Create item and queue class
class Item {
constructor(data, number) {
this.data = data;
this.number = number;
}
}
class PriorityQueue {
constructor() {
this.items = [];
}
//add methods
}
The item class stores the item data and it's priority number.
The the priority queue class instantiates an array used to store items.
2.Add methods to class
Enqueue
enqueue(data, number) {
//create new item
let item = new Item(data, number);
let addedFlag = false;
//loop through array, to end of array
for (let idx = 0; idx < this.items.length; idx++) {
//if new item has a lower number
//add new item before current item
if (this.items[idx].number > item.number) {
this.items.splice(idx, 0, item);
addedFlag = true;
break;
}
}
//default action is to add item at the end of queue
if (!addedFlag) {
this.items.push(item);
}
}
The enqueue method adds item to queue according to it's priority. A higher number given to item means the item has a lower priority compared to item with a lower number.
Example;
item A with priority number 2 and item B with priority number 1. Item B is of a higher priority than A. Hence A is pushed to end of queue and B front of queue.
Dequeue
dequeue() {
//if empty do nothing else remove first item in queue
if (this.items.length === 0) {
return;
}
this.items.shift()
}
peek
peek() {
//if not empty return first item in queue
if (this.items.length === 0) {
return "Empty queue";
}
return this.items[0].data;
}
Test Code
const queue = new PriorityQueue();
queue.enqueue(3, 4);
queue.enqueue(6, 5);
queue.enqueue(7, 3);
queue.enqueue(8, 1);
queue.dequeue()//removes 8 from queue
console.log(queue.peek()) //prints 7
console.log(queue);
Top comments (0)