freeCodeCamp Challenge Guide: Create a Priority Queue Class

Create a Priority Queue Class


Problem Explanation

  • Priority Queue is an Abstract Data Type.
  • It can be implemented using other Data Structures but is commonly implemented using a Heap.
  • Each node contains a priority. When we enqueue a node to the queue, it’s “bubbled up” to its place in the queue.
  • In this challenge we need to create a Priority Queue class based on Min-Heap with a few methods:
    • enqueue() - It enqueue’s the new node to it’s appropriate place in queue.
    • dequeue() - It removes the first node from the queue.
    • front() - This method returns the first node to be dequeued.
    • size() - Returns the size of the queue.
    • isEmpty() - Returns if the queue is empty.
  • DS Access Search Insert Delete
    Priority Queue 1 1 logn logn

Relevant Links


Solutions

Solution 1 (Click to Show/Hide)
function PriorityQueue() {
  this.collection = [];
  this.printCollection = function () {
    console.log(this.collection);
  };
  // Only change code below this line
  this.enqueue = function (newitem) {
    if (this.isEmpty()) {
      return this.collection.push(newitem);
    }

    this.collection = this.collection.reverse();
    var found_index = this.collection.findIndex(function (item) {
      return newitem[1] >= item[1];
    });
    if (found_index === -1) {
      this.collection.push(newitem);
    } else {
      this.collection.splice(found_index, 0, newitem);
    }
    this.collection = this.collection.reverse();
  };
  this.dequeue = function () {
    if (!this.isEmpty()) {
      return this.collection.shift()[0];
    } else {
      return "The queue is empty.";
    }
  };
  this.size = function () {
    return this.collection.length;
  };
  this.front = function () {
    return this.collection[0][0];
  };
  this.isEmpty = function () {
    return this.size() > 0 ? false : true;
  };
  // Only change code above this line
}
1 Like