Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”. This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Yesterday, I wrote an article on stack structure. This article continues to introduce another linear table – queue structure. If there are any shortcomings or suggestions, welcome to give feedback ~

define

A Queue (pronounced ‘kjuː), a data structure based on First In First Out (FIFO), is a limited linear list that can only be inserted at one end (front) and deleted at the other (rear).

Encapsulating queue structure

There is no existing Queue structure in js, but we can encapsulate a constructor Queue based on the array itself, and implement the five common operations of Queue, Queue, check the first element of the Queue, check whether the Queue is empty, and convert the Queue content into a string:

function Queue() {
  this.items = []
  / / team
  Queue.prototype.push = function (item) {
    this.items.push(item)
  }
  / / out of the team
  Queue.prototype.shift = function () {
    return this.items.shift()
  }
  // Look at the first element of the queue
  Queue.prototype.first = function () {
    return this.items[0]}// Check whether the queue is empty
  Queue.prototype.isEmpty = function () {
    return this.items.length === 0
  }
  // Convert the queue contents to a string
  Queue.prototype.toString = function () {
    return this.items.toString()
  }
}

// new a queue instance
const queue = new Queue()
Copy the code

case

Today lol S11 world tournament will start to play qualifiers, here to write a small game to predict a wave of champions. The rules are as follows: several favorite teams round the circle and count in turn, the person reporting number 7 is eliminated directly, until the last team left, become the predicted champion, the end of the game.

function drinkingGame(crowd, number) {
  // new a queue instance
  const queue = new Queue()
  // Put each item in the crowd into a queue
  crowd.forEach((item) = > queue.push(item))
  while (crowd.length > 1) {
    // Any item less than number is removed from the queue and put back into the queue
    for (let index = 0; index < number - 1; index++) {
      crowd.push(crowd.shift())
    }
    // Delete the number item before the for loop.
    crowd.shift()
  }
  console.log(crowd.toString())
}

drinkingGame(['Rng'.'T1'.'EDG'.'DWG'.'FPX'].7)
Copy the code

Unfortunately XDM, my prediction is DWG, I hope it is the reverse prediction ~

Priority queue

In a normal queue, the newly inserted element is always placed last, while in a priority queue, each element is assigned a priority, and the important relationship between the priority of this element and the priority of other elements in the queue is considered when inserting an element, and the element with a higher priority is placed before the element with a lower priority. For example, if a test bug is submitted, priority 1 should be processed first, and priority 5 should be deferred.

function PriorityQueue() {
  // Create an Item constructor that creates the element to be added to the priority queue
  function Item(item, p) {
    this.element = item
    this.priority = p
  }
  // Inherit the attributes of Queue
  Queue.call(this)
  // Override belongs to the priority queue push method
  PriorityQueue.prototype.push = function (newItem, p) {
    const item = new Item(newItem, p)
    // If the queue is empty, the new element is added directly
    if (this.isEmpty()) {
      this.items.push(item)
    } else {
      let isPush = false // Check whether the record is successfully inserted
      // Insert before the element if it encounters a lower priority than its own
      for (let index = 0; index < this.items.length; index++) {
        if (item.priority < this.items[index].priority) {
          this.items.splice(index, 0, item)
          isPush = true
          break}}// If the priority is higher than their own
      if(! isPush) {this.items.push(item)
      }
    }
  }
}
// Inherit the Queue method
PriorityQueue.prototype = Object.create(Queue.prototype)
Copy the code

You can test it:

const priorityQueue = new PriorityQueue()
priorityQueue.push('five bugs'.5)
priorityQueue.push('level of bugs'.1)
priorityQueue.push('level 3 bugs'.3)
priorityQueue.push('secondary bugs'.2)
console.log(priorityQueue)
Copy the code

The results are as follows: