Introduction of the queue

What is a queue? A queue is a first-in, first-out (FIFO) data structure. What’s the use of a queue? Queues are often used to describe algorithms or some first-in, first-out scenario in life, such as:

• In the breadth-first traversal of a graph, we need to use queues to record the adjacent nodes of each node so that they can be accessed first later to achieve breadth-first traversal.
• In the JavaScript Event Loop, there is a Task Queue, which also handles asynchronous events first in first out.
• In life, queues can be used to map the scene of waiting for a meal.

Write queue classes in JavaScript

The constructor function is also used to write the queue class. Write a queue class that can run the following tests:

var queue = new Queue();
expect(queue.isEmpty()).toBeTruthy();
queue.enqueue('Joe');
queue.enqueue('bill');
queue.enqueue('Cathy');
expect(queue.front()).toBe('Joe');
expect(queue.toString()).toBe('Three, four, five.');
expect(queue.size()).toBe(3);
expect(queue.isEmpty()).toBeFalsy();
queue.dequeue();
queue.dequeue();
expect(queue.toString()).toBe('Cathy');
Copy the code

Queue class is relatively simple, directly on the code:

function Queue() {
  // The private variable items is used to record arrays,
  let items = []
  / / team
  this.enqueue = function (element) {
    items.push(element)
  }
  / / out of the team
  this.dequeue = function () {
    return items.shift()
  }
  // View the first element of the queue
  this.front = function () {
    return items[0]}// Check whether the queue is empty
  this.isEmpty = function () {
    return items.length == 0
  }
  // Check the length of the queue
  this.size = function () {
    return items.length
  }
  // Convert the array to a string and put it back
  this.toString = function () {
    return items.toString()
  }
}

module.exports = Queue

Copy the code

Note the four methods for adding and deleting arrays to avoid confusion:

• Push: Adds a new element to the tail
• Pop: Removes and returns the tail element
• Unshift: Adds a new element to the header
• Shift: Removes and returns the header element

So, the way out of the team is shift. In addition, using arrays to create queues is not a good idea if you consider the time complexity, because all the elements will move out of the queue, resulting in poor performance. A linked list is even better because it is not contiguous, and you can add or delete elements only by changing their references.

Priority queues: Extra queues are so capricious

The normal queue class, which is a method that calls the native Array object, is simpler, but there is another queue called a priority queue. In the priority queue, some people are bullies and can be added to the queue. However, if there is a bully more than him, he has to wait in the back. Take an example! Suppose there are three people: Zhang SAN, Li Si and Wang Wu. Wang Wu is an honest man without skill. Zhang SAN is a hooligan who often bullies Wang Wu. Li si? It’s a bureaucrat. The three of them queued up, the rascal Zhang SAN came first, the official Li Si came second, and the honest Wang Wu came last. As a result, Zhang SAN gave way to Li Si, and Wang Wu ranked last. In the priority queue, we use priority to describe the degree of bullying.

var priorityQueue = new PriorityQueue();
priorityQueue.enqueue('Joe'.2);
priorityQueue.enqueue('bill'.1);
priorityQueue.enqueue('Cathy'.3);
expect(priorityQueue.toString()).toBe('Li Si-1, Zhang San-2, Wang Wu-3');
Copy the code

In the code above, the number after the name is the priority. The queued result looks like the last assertion: ‘Li 4-1, Zhang 3-2, Wang Wu-3’. To implement the above test case, we need to rewrite the enqueue and toString methods:

function PriorityQueue() {
  let items = [];

  // Create a queue element using the constructor function
  let QueueElement = function(element, priority) {
    this.element = element;
    this.priority = priority
  }

  this.enqueue = function(element, priority) {
    let queueElement = new QueueElement(element, priority);

    // Zhang SAN's situation
    if (this.isEmpty()) {
      items.push(queueElement);
    } else {
      let added = false
      for (let i = 0; i < items.length; i++) {
        if (queueElement.priority < items[i].priority) {
          items.splice(i, 0, queueElement)
          added = true
          break}}// About Wang Wu
      if(! added) { items.push(queueElement) } } } ...this.toString = function () {
    let string = ' '
    for (let i = 0; i < items.length; i++) {
      string += items[i].element + The '-' + items[i].priority + (items.length - i > 1 ? ', ' : ' ')}return string
  }
}

module.exports = PriorityQueue;
Copy the code

The other methods are just like normal queues, but the toString method simply prints one more priority.

Example code: github.com/gin280/java…