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); // ['b'];
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 = []; }
this.dataStore = []; An empty array stores all elements in the queue.
function enqueue(element) { this.dataStore.push(element); }
function dequeue() { return this.dataStore.shift() }
function front() { return this.dataStore[0]; }
function back() { return this.dataStore[this.dataStore.length - 1]; }
function toString() { var retStr = ""; for(var i = 0; i < this.dataStore.length; ++i) { retStr += this.dataStore[i] + "\n"; } return retStr; }
function empty(){ if(this.dataStore.length == 0) { return true; }else { return false; } }
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; } } };
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
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"];
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]
nums = [50,90,81,91,12,72,3,74,95,7]
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
nums = [3,7,12,50,72,74,81,90,91,95];
/* * 根据个位或十位上的数值,将数字分配到相应队列的函数 * @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(); } } }
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]); } } };
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);
相关推荐:
The above is the detailed content of Detailed explanation of JavaScript queue principles and usage examples. For more information, please follow other related articles on the PHP Chinese website!