Detailed explanation of JavaScript queue principles and usage examples-JS Tutorial-php.cn

A queue is a kind of list. The difference is that a queue can only insert elements at the end of the queue and delete elements at the beginning of the queue. Queues are used to store data arranged in order, first in, first out, which is different from stacks (last in, first out). In the stack, the last element pushed onto the stack is processed first. We can now imagine the queue as when we go to a restaurant to eat. Many people line up to eat, and the person at the front gets their meal first. Newcomers can only queue at the back. until it's their turn. This article mainly introduces the principles and usage of queues in JavaScript data structures and algorithms, explains the concepts and principles of queues in more detail, and analyzes the related operating techniques and precautions for implementing and using queues in JavaScript in the form of examples. Friends in need can refer to Next, I hope it can help everyone.

1: Operations on the queue

The queue has two main operations, inserting new elements into the tail of the queueenqueue( ) method and the dequeue() method that deletes the element at the head of the queue. In addition, we also have a method that reads the element at the head of the queue. This method we can call front()method. This method returns the head element and other methods.

After seeing the above description, many of us may think of arrays. There are also two methods in the array that have similar functions to the above methods. The push() method in the array also adds new data to the back of the array. element, the shift() method in the array can delete the first element in the array. The following code:

var arrs = [];
arrs.push("a");
arrs.push("b");
console.log(arrs); // ["a","b"];
arrs.shift();
console.log(arrs); // [&#39;b&#39;];

Copy after login

Below we can use 2 of push() and shift() in the above array Method to encapsulate our queue Queue class;

1. We can first define a constructor Queue class, as follows:

function Queue() {
  this.dataStore = [];
}

Copy after login

As above:

this.dataStore = []; An empty array stores all elements in the queue.

2. The method of adding an element to the tail of the queue is as follows:

function enqueue(element) {
   this.dataStore.push(element);
}

Copy after login

3. The method of deleting the element of the head of the queue is as follows:

function dequeue() {
  return this.dataStore.shift()
}

Copy after login

4. Read the elements at the head of the queue as follows:

function front() {
  return this.dataStore[0];
}

Copy after login

5. Read the elements at the tail of the queue as follows:

function back() {
  return this.dataStore[this.dataStore.length - 1];
}

Copy after login

6. Display all elements in the queue

function toString() {
  var retStr = "";
  for(var i = 0; i < this.dataStore.length; ++i) {
    retStr += this.dataStore[i] + "\n";
  }
  return retStr;
}

Copy after login

7. Determine whether the queue is empty as follows:

function empty(){
  if(this.dataStore.length == 0) {
    return true;
  }else {
    return false;
  }
}

Copy after login

The following is the complete JS code as follows:

function Queue() {
  this.dataStore = [];
}
Queue.prototype = {
  // 向队尾添加一个元素
  enqueue: function(element) {
    this.dataStore.push(element);
  },
  // 删除队首的元素
  dequeue: function(){
    return this.dataStore.shift();
  },
  // 读取队首的元素
  front: function(){
    return this.dataStore[0];
  },
  // 读取队尾的元素
  back: function(){
    return this.dataStore[this.dataStore.length - 1];
  },
  // 显示队列内的所有元素
  toString: function(){
    var retStr = "";
    for(var i = 0; i < this.dataStore.length; ++i) {
      retStr += this.dataStore[i] + "\n";
    }
    return retStr;
  },
  // 判断队列是否为空
  empty: function(){
    if(this.dataStore.length == 0) {
      return true;
    }else {
      return false;
    }
  }
};

Copy after login

We can now test the above code: as follows:

var q = new Queue();
q.enqueue("a");
q.enqueue("b");
q.enqueue("c");
console.log(q.toString()); // a b c
q.dequeue();
console.log(q.toString()); // b c
console.log("Front of queue:" +q.front()); // b
console.log("Back of queue:" +q.back()); // c

Copy after login

Two: Use queues to sort data

For example, for sorting numbers from 0 to 99, the principle is: Sort the numbers in the ones place first, and then sort the numbers in the tens place. Each number is divided into different boxes according to the value of the corresponding digit, and then the remainder method is used for the numbers in the ones place, and the division method is used for the numbers in the 10th digit. Then this sorting is called "radix sorting" . It's not the fastest sorting method, but it describes some interesting ways to use queues.

For example, the following array:

var nums = ["50","12","95","7","90","3","74","81","91","72"];

Copy after login

1. After radix sorting - units sorting, the numbers are distributed in different boxes. (In JS, we can assign it to different Queue instance classes). As follows

queues[0] = 50 或者 90
queues[1] = 81 或者 91
queues[2] = 12 或者 72
queues[3] = 3
queues[4] = 74
queues[5] = 95
queues[6] 
queues[7] = 7
queues[8]
queues[9]

Copy after login

According to the order of the boxes, the results after sorting the first ones digit of the numbers are as follows:

nums = [50,90,81,91,12,72,3,74,95,7]

Copy after login

2. Then distribute the results after the last sorting to different boxes according to the value in the tens digit. As follows:

queues[5] = 50
queues[9] = 90
queues[8] = 81
queues[9] = 91
queues[1] = 12
queues[7] = 72
queues[0] = 3
queues[7] = 74
queues[9] = 95
queues[0] = 7

Copy after login

Finally, take out the numbers in the box and form a new list, which is the sorted number. As follows:

can be generated as follows:

nums = [3,7,12,50,72,74,81,90,91,95];

Copy after login

Using the queue list box as above, this algorithm can be implemented. We need 10 queues, each queue corresponds to A number, save all queues in an array, use remainder and division operations to determine the ones and tens digits. The remainder of the algorithm adds the numbers to the corresponding queue, reorders them based on the ones-digit value, then sorts them based on the tens-digit value, and adds the sorted numbers as a result.

The following function allocates numbers to the corresponding queue according to the value in the ones or tens place.

/*
* 根据个位或十位上的数值，将数字分配到相应队列的函数
* @param digit
* digit=1 表示先按个位来分配
* digit = 10 表示是按十位来分配的
* @param n 表示循环比较多少次 一般数组几个数字就比较多少次
*/
distribute: function(nums,queues,n,digit){
   for(var i = 0; i < n; ++i) {
    if(digit == 1) {
      queues[nums[i] % 10].enqueue(nums[i]);
     }else {
      queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
     }
   }
}

Copy after login

The following is the function to collect numbers from the queue as follows:

// 收集数字的函数
collect: function(queues,nums,n) {
  var i = 0;
  for(var digit = 0; digit < n; ++digit) {
    while(!queues[digit].empty()) {
      nums[i++] = queues[digit].dequeue();
    }
  }
}

Copy after login

Since many steps are omitted above, The description may not be very clear. Let's take a look at the flow chart first, combine it with the flow chart, and finally combine it with all the JS code to understand the basic principle of "radix sorting"; below we can look at the following flow chart;

Finally, all the JS codes are as follows:

function Queue() {
  this.dataStore = [];
}
Queue.prototype = {
  // 向队尾添加一个元素
  enqueue: function(element) {
    this.dataStore.push(element);
  },
  // 删除队首的元素
  dequeue: function(){
    return this.dataStore.shift();
  },
  // 读取队首的元素
  front: function(){
    return this.dataStore[0];
  },
  // 读取队尾的元素
  back: function(){
    return this.dataStore[this.dataStore.length - 1];
  },
  // 显示队列内的所有元素
  toString: function(){
    var retStr = "";
    for(var i = 0; i < this.dataStore.length; ++i) {
      retStr += this.dataStore[i] + "\n";
    }
    return retStr;
  },
  // 判断队列是否为空
  empty: function(){
    if(this.dataStore.length == 0) {
      return true;
    }else {
      return false;
    }
  },
  /*
   * 根据个位或十位上的数值，将数字分配到相应队列的函数
   * @param digit
   * digit=1 表示先按个位来分配
   * digit = 10 表示是按十位来分配的
   * @param n 表示循环比较多少次 一般数组几个数字就比较多少次
   */
  distribute: function(nums,queues,n,digit){
    for(var i = 0; i < n; ++i) {
      if(digit == 1) {
        queues[nums[i] % 10].enqueue(nums[i]);
      }else {
        queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
      }
    }
  },
  // 收集数字的函数
  collect: function(queues,nums,n) {
    var i = 0;
    for(var digit = 0; digit < n; ++digit) {
      while(!queues[digit].empty()) {
        nums[i++] = queues[digit].dequeue();
      }
    }
  },
  dispArray: function(arr) {
    for(var i = 0; i < arr.length; ++i) {
      console.log(arr[i]);
    }
  }
};

Copy after login

The following is a test of the "radix sort" JS code ;The following code:

var q = new Queue();
  q.enqueue("a");
  q.enqueue("b");
  q.enqueue("c");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log("Front of queue:" +q.front());
console.log("Back of queue:" +q.back());
var queues = [];
for(var i = 0; i < 10; ++i) {
   queues[i] = new Queue();
}
var nums = ["50","12","95","7","90","3","74","81","91","72"];
console.log("before radix sort: ");
console.log(nums);
q.distribute(nums,queues,10,1);
q.collect(queues,nums,10);
q.dispArray(nums);
console.log("分割线");
q.distribute(nums,queues,10,10);
q.collect(queues,nums,10);
q.dispArray(nums);

Copy after login