“This is the 8th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Hi, here is the pig bully with Teacher Coderwhy JS data structure learning summary, the New Year more to teach ducks!

Learning portal:

  • JS Data Structure & Algorithm learning – Concept Portal
  • JS data structure & Algorithm learning – Array portal
  • JS data structure & Algorithm learning — Stack portal
  • JS data structure & algorithm learning – queue this article!
  • JS data structure & Algorithm learning – Priority queue to be summarized
  • JS data structure & Algorithm learning — Linked list to be summarized
  • JS data Structure & Algorithm learning — Bidirectional linked list to be summarized
  • JS data Structure & Algorithm learning — Set to be summarized
  • JS data structure & Algorithm learning — Hash table to be summarized
  • JS data structure & Algorithm learning — Red black tree to be summarized
  • Waiting to learn!!

The queue

In the previous stack, it was a constrained linear structure, first in, last out. What about the characteristics of the queue with the same linear structure?

concept

A queue is a limited linear, first-in, first-out table that only allows us to delete at the front of the table and add at the back.

Application of life

  1. In life, the most commonly seen queue scene is queuing, that is, when we are queuing, the head of the queue is our table head, it allows out, can not jump the queue is to add operation, and the tail, that is, our table tail, it allows someone to queue, that is, add operation
  2. When we check in the train, we normally queue up, while special groups such as soldiers and the elderly can be dealt with first, which is the priority queue.

applications

  1. Take JS as an example, the event queue is relatively common, because JS is a single-threaded language, that is, when we trigger our function, there will be an event queue, which will be executed in accordance with the triggering order of the event, that is, first trigger first execution, which is a manifestation of the queue
  2. Of course, thread queue is also a kind of queue. We usually use multithreading in order to process tasks in parallel, but multiple threads occupy a lot of memory. Therefore, at this time, we can use thread queue to start threads in order and process corresponding tasks.

The queue structure

Of course, queue structures, like stacks, can be implemented through arrays and linked lists

First, let’s encapsulate the queue

function queue(){
    // Attributes of the queue
    this.items = []
    
    // Queue related operations
}

var queue = new queue()

Copy the code

Because the JS class is based on objects, we encapsulate a queue class, in the class we can define the attributes and methods of the queue, after encapsulation we can call to achieve some operations on the queue

Common operation and packaging

  1. Enqueue (Element) : Adds elements to the end of the queue
  2. Dequeue () : removes the first element of the queue and returns its value
  3. Front () : Returns the first element of the queue
  4. IsEmpty: checks whether the queue isEmpty
  5. Size: Returns the queue length
  6. ToString () : Converts strings

Enqueue (Element) : Use the push method for queue encapsulation

queue.prototype.enqueue = function (element) {
      this.items.push(element)
}
Copy the code

Dequeue () : Performs queue operation via shift method provided by JS

queue.prototype.delet = function () {
      return this.items.shift()
}
Copy the code

Front () : Returns the first element directly by array subscript

queue.prototype.front = function () {
      return this.items[0]}Copy the code

IsEmpty () : Nulls the stack by the length of the array

queue.prototype.isEmpty = function () {
      return this.items.length == 0
}
Copy the code

size()

queue.prototype.size = function () {
      return this.items.length
}
Copy the code

ToString () : traverses the stack by declaring string variables, concatenates strings through the characteristics of JS string, and finally returns its string. Its implementation principle is the same as toString of stack.

queue.prototype.toString = function () {
      var reString = ' '
      for (let i = 0; i < this.items.length; i++) {
        reString += this.items[i] + ' '
      }
      return reString
    }
Copy the code

use

Once it’s wrapped, we can start making the call

queue.enqueue(1)
queue.enqueue(19)
queue.enqueue(11)
console.log(queue)
Copy the code

queue.delet()
console.log(queue)
Copy the code

You can try to write your own and experience the queue operations

musical

I believe that we have played the game of drum spread flowers, when the drum transfer flowers, drums stop, flowers in the hands of those who will be punished

Now there are different rules of the game, that is, students gather in a circle and count according to the Order of Arabic numbers. When someone reaches the number of people present, they will be eliminated

We will now implement the game with a queue and return the name of the final winner

  1. Algorithm principle:

Now we put everyone in a queue in order, and we start from the head of the queue, so that when there is a number of people present, it happens to be the head of the queue, and we do it multiple times, and we get the result

  1. Algorithm implementation:

    1. Create a queue and enqueue everyone

      var queue = new queue
    for (let i = 0; i < list.length; i++) {
     queue.enqueue(nameList[i])
}
Copy the code

    2. It starts to loop in and out of queues until the queue length is 1

        while (queue.size() > 1) {
      If num is not the number of players in the team, enter the team again. If num is the number of players present, exit the team.
      for (let i = 0; i < num - 1; i++) {
        queue.enqueue(queue.dequeue())
      }
      // Remove target which is now the team leader
      queue.dequeue()
    }
Copy the code