JavaScript中隊(duì)列有什么用

這篇文章主要介紹JavaScript中隊(duì)列有什么用，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

隊(duì)列是一種列表，不同的是隊(duì)列只能在隊(duì)尾插入元素，在隊(duì)首刪除元素。隊(duì)列用于存儲(chǔ)按順序排列的數(shù)據(jù)，先進(jìn)先出，這點(diǎn)和棧不一樣(后入先出)。在棧中，最后入棧的元素反而被優(yōu)先處理。我們現(xiàn)在可以把隊(duì)列想象對(duì)我們?nèi)ゲ宛^吃飯的情景，很多人排隊(duì)吃飯，排在最前面的人先打飯。新來(lái)的人只能在后面排隊(duì)。直到輪到他們?yōu)橹埂?/p>

一：對(duì)隊(duì)列的操作

隊(duì)列有2種主要的操作，向隊(duì)尾中插入新元素enqueue()方法和刪除隊(duì)列中的隊(duì)首的元素的dequeue()方法，另外我們還有一個(gè)讀取隊(duì)頭的元素，這個(gè)方法我們可以叫front()方法。該方法返回隊(duì)頭元素等等方法。

看到如上描述，我們很多人可能會(huì)想到數(shù)組，數(shù)組里面也有2個(gè)方法和上面的方法功能類(lèi)似，數(shù)組中push()方法也是往數(shù)組后面加入新元素，數(shù)組中shift()方法則可以刪除數(shù)組里面的第一個(gè)元素。如下代碼：

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

下面我們可以使用上面的數(shù)組中的push()和shift()的2個(gè)方法來(lái)封裝我們的隊(duì)列Queue類(lèi)；

1.  我們可以先定義一個(gè)構(gòu)造函數(shù)Queue類(lèi)，如下：

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

如上：this.dataStore = []; 空數(shù)組時(shí)存儲(chǔ)隊(duì)列中所有的元素的。

2. 向隊(duì)尾中添加一個(gè)元素方法如下：

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

3. 刪除隊(duì)首的元素如下：

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

4. 讀取隊(duì)首的元素如下：

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

5. 讀取隊(duì)尾的元素如下：

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

6. 顯示隊(duì)列中的所有元素

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

7. 判斷隊(duì)列是否為空如下：

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

下面是完整的JS代碼如下：

function Queue() {
  this.dataStore = [];
}
Queue.prototype = {
  // 向隊(duì)尾添加一個(gè)元素
  enqueue: function(element) {
    this.dataStore.push(element);
  },
  // 刪除隊(duì)首的元素
  dequeue: function(){
    return this.dataStore.shift();
  },
  // 讀取隊(duì)首的元素
  front: function(){
    return this.dataStore[0];
  },
  // 讀取隊(duì)尾的元素
  back: function(){
    return this.dataStore[this.dataStore.length - 1];
  },
  // 顯示隊(duì)列內(nèi)的所有元素
  toString: function(){
    var retStr = "";
    for(var i = 0; i < this.dataStore.length; ++i) {
      retStr += this.dataStore[i] + "\n";
    }
    return retStr;
  },
  // 判斷隊(duì)列是否為空
  empty: function(){
    if(this.dataStore.length == 0) {
      return true;
    }else {
      return false;
    }
  }
};

我們現(xiàn)在可以對(duì)以上代碼測(cè)試下：如下：

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

二：使用隊(duì)列對(duì)數(shù)據(jù)進(jìn)行排序

比如對(duì)于 0 ~ 99 的數(shù)字進(jìn)行排序，原理是：先對(duì)個(gè)位上的數(shù)字進(jìn)行排序一次，然后對(duì)十位上的數(shù)字再進(jìn)行排序一次。每個(gè)數(shù)字根據(jù)對(duì)應(yīng)位上的數(shù)值被分在不同的盒子里面，然后對(duì)于個(gè)位上的數(shù)字采用除余數(shù)的方法，對(duì)于10位上的數(shù)字采用除法的方法，那么這種排序叫做 “基數(shù)排序”. 但是它不是最快的排序方法，但是它描述了一些有趣的隊(duì)列使用方法。

比如如下數(shù)組：

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

1. 經(jīng)過(guò)基數(shù)排序--個(gè)位排序后，數(shù)字被分配在不同的盒子里面。（在JS里面，我們可以分配在不同的隊(duì)列Queue實(shí)例類(lèi)里面）。如下

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]

根據(jù)盒子的順序，對(duì)數(shù)字第一次個(gè)位排序后結(jié)果如下：

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

2. 然后根據(jù)十位上的數(shù)值再將上次排序后的結(jié)果分配到不同的盒子中。如下：

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

最后，將盒子中的數(shù)字取出，組成一個(gè)新的列表，該列表即為排序好的數(shù)字。如下：

即可生成如下：

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

如上使用隊(duì)列列表盒子，可以實(shí)現(xiàn)這個(gè)算法，我們需要10個(gè)隊(duì)列，每個(gè)隊(duì)列對(duì)應(yīng)一個(gè)數(shù)字，將所有隊(duì)列保存在一個(gè)數(shù)組中，使用取余和除法操作決定個(gè)位和十位。算法的剩余部分將數(shù)字加入相應(yīng)的隊(duì)列，根據(jù)個(gè)位數(shù)值進(jìn)行重新排序，然后再根據(jù)十位上的數(shù)值進(jìn)行排序，結(jié)果加入排序好的數(shù)字。

下面根據(jù)個(gè)位或十位上的數(shù)值，將數(shù)字分配到相應(yīng)隊(duì)列的函數(shù)。

/*
* 根據(jù)個(gè)位或十位上的數(shù)值，將數(shù)字分配到相應(yīng)隊(duì)列的函數(shù)
* @param digit
* digit=1 表示先按個(gè)位來(lái)分配
* digit = 10 表示是按十位來(lái)分配的
* @param n 表示循環(huán)比較多少次 一般數(shù)組幾個(gè)數(shù)字就比較多少次
*/
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]);
     }
   }
}

下面是從隊(duì)列中收集數(shù)字的函數(shù)如下：

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

由于上面省略了很多步驟，可能描述的不是很清楚，我們現(xiàn)在先來(lái)看看流程圖，結(jié)合流程圖，最后結(jié)合JS的所有代碼就可以理解"基數(shù)排序的"基本原理了；下面我們可以看看如下的流程圖；

最后是所有的JS代碼如下：

function Queue() {
  this.dataStore = [];
}
Queue.prototype = {
  // 向隊(duì)尾添加一個(gè)元素
  enqueue: function(element) {
    this.dataStore.push(element);
  },
  // 刪除隊(duì)首的元素
  dequeue: function(){
    return this.dataStore.shift();
  },
  // 讀取隊(duì)首的元素
  front: function(){
    return this.dataStore[0];
  },
  // 讀取隊(duì)尾的元素
  back: function(){
    return this.dataStore[this.dataStore.length - 1];
  },
  // 顯示隊(duì)列內(nèi)的所有元素
  toString: function(){
    var retStr = "";
    for(var i = 0; i < this.dataStore.length; ++i) {
      retStr += this.dataStore[i] + "\n";
    }
    return retStr;
  },
  // 判斷隊(duì)列是否為空
  empty: function(){
    if(this.dataStore.length == 0) {
      return true;
    }else {
      return false;
    }
  },
  /*
   * 根據(jù)個(gè)位或十位上的數(shù)值，將數(shù)字分配到相應(yīng)隊(duì)列的函數(shù)
   * @param digit
   * digit=1 表示先按個(gè)位來(lái)分配
   * digit = 10 表示是按十位來(lái)分配的
   * @param n 表示循環(huán)比較多少次 一般數(shù)組幾個(gè)數(shù)字就比較多少次
   */
  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]);
      }
    }
  },
  // 收集數(shù)字的函數(shù)
  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]);
    }
  }
};

下面的是對(duì) "基數(shù)排序的" JS代碼進(jìn)行測(cè)試；如下代碼：

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("分割線(xiàn)");
q.distribute(nums,queues,10,10);
q.collect(queues,nums,10);
q.dispArray(nums);

以上是“JavaScript中隊(duì)列有什么用”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！