This album is based on the video “JavaScript data structures and Algorithms”, the author of this article has the notes, source code, test environment hosted on GitHub, welcome students Star and Fork.

It is recommended that you learn the structure of the directory in order, from the simple to the deep, step by step, easy to figure out the data structure and algorithm.

scenario

Priority queue scenarios in life:

  • Priority queue, priority processing. (Buy tickets, check out, WC).
  • In the queue, people with emergency (special condition) can be dealt with first.

Priority queue

Priority queues are mainly concerned with:

  • Each element is no longer just a piece of data, but also a priority.
  • During the addition process, elements are placed in the correct position according to priority.

Implementation of priority queue

Code implementation

// The element class inside the priority queue
class QueueElement {
  constructor(element, priority) {
    this.element = element;
    this.priority = priority; }}// Priority Queue class (inherited from Queue)
export class PriorityQueue extends Queue {

  constructor() {
    super(a); }// enqueue(Element, priority) enqueue, which adds elements to the queue according to their priority
  / / rewrite the enqueue ()
  enqueue(element, priority) {
    // Create QueueElement based on the element passed in
    const queueElement = new QueueElement(element, priority);

    // Check whether the queue is empty
    if (this.isEmpty()) {
      // If the value is empty, add it directly without judging the priority
      this.items.push(queueElement);
    } else {
      // Define a variable to record whether the new element was successfully added
      let added = false;

      for (let i = 0; i < this.items.length; i++) {
        // Compare the priority of the newly inserted element. The lower the priority, the higher the priority
        if (queueElement.priority < this.items[i].priority) {
          // Inserts the element at the specified position
          this.items.splice(i, 0, queueElement);
          added = true;
          break; }}// If the priority of all elements is higher than that of the newly inserted element, the newly inserted element is inserted to the end
      if(! added) {this.items.push(queueElement); }}}// dequeue() removes the front-end element from the queue and returns the deleted element
  // Inherit dequeue() from Queue
  dequeue() {
    return super.dequeue();
  }

  // front() looks at the front element of the queue
  // Inherit Queue front()
  front() {
    return super.front();
  }

  // isEmpty() to see if the queue isEmpty
  // Inherit isEmpty() from Queue
  isEmpty() {
    return super.isEmpty();
  }

  // size() Checks the number of elements in the queue
  // Inherit Queue size()
  size() {
    return super.size();
  }

  // toString() returns the queue element as a string
  / / rewrite the toString ()
  toString() {
    let result = ' ';
    for (let item of this.items) {
      result += item.element + The '-' + item.priority + ' ';
    }
    returnresult; }}Copy the code

The test code

const priorityQueue = new PriorityQueue();

// Enqueue () test
priorityQueue.enqueue('A'.10);
priorityQueue.enqueue('B'.15);
priorityQueue.enqueue('C'.11);
priorityQueue.enqueue('D'.20);
priorityQueue.enqueue('E'.18);
console.log(priorityQueue.items);
//--> output:
// QueueElement {element: "A", priority: 10}
// QueueElement {element: "C", priority: 11}
// QueueElement {element: "B", priority: 15}
// QueueElement {element: "E", priority: 18}
// QueueElement {element: "D", priority: 20}

// Dequeue () test
priorityQueue.dequeue();
priorityQueue.dequeue();
console.log(priorityQueue.items);
//--> output:
// QueueElement {element: "B", priority: 15}
// QueueElement {element: "E", priority: 18}
// QueueElement {element: "D", priority: 20}

/ / isEmpty () test
console.log(priorityQueue.isEmpty()); //--> false

/ / the size () test
console.log(priorityQueue.size()); / / -- > 3

/ / the toString () test
console.log(priorityQueue.toString()); //--> B-15 E-18 D-20
Copy the code

Array, stack, and queue diagrams

Album series

  • Learn JavaScript data structures and algorithms from 0
  • Learn JavaScript data structures and algorithms from 0 (2) arrays
  • Learn JavaScript data structures and algorithms from 0 onwards (iii) stack
  • Learn JavaScript data structures and algorithms from 0 (iv) queue