DEV Community

Ivy-Walobwa
Ivy-Walobwa

Posted on

Priority Queue

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
}
Enter fullscreen mode Exit fullscreen mode

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);
    }
    }
Enter fullscreen mode Exit fullscreen mode

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()
    }

Enter fullscreen mode Exit fullscreen mode

peek

peek() {
        //if not empty return first item in queue
        if (this.items.length === 0) {
            return "Empty queue";
        }
        return this.items[0].data;
    }
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

Top comments (0)