首頁  >  文章  >  web前端  >  JavaScript佇列原理與用法實例詳解

JavaScript佇列原理與用法實例詳解

小云云
小云云原創
2017-12-18 13:31:232944瀏覽

隊列是一種列表,不同的是隊列只能在隊尾插入元素,在隊首刪除元素。佇列用來儲存依序排列的數據,先進先出,這點和棧不一樣(後入先出)。在堆疊中,最後入棧的元素反而優先處理。我們現在可以把隊列想像對我們去餐廳吃飯的情景,很多人排隊吃飯,排在最前面的人先打飯。新來的人只能在後面排隊。直到輪到他們為止。本文主要介紹了JavaScript資料結構與演算法之隊列原理與用法,較為詳細的說明了隊列的概念、原理,並結合實例形式分析了javascript實現與使用隊列的相關操作技巧與注意事項,需要的朋友可以參考下,希望能幫助大家。

一:對隊列的操作

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

看到如上描述,我們很多人可能會想到數組,數組裡面也有2個方法和上面的方法功能類似,數組中push()方法也是往數組後面加入新元素,數組中shift()方法則可以刪除數組裡面的第一個元素。如下程式碼:


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

下面我們可以使用上面的陣列中的push()shift()的2個方法來封裝我們的隊列Queue類別;

##1.  我們可以先定義一個建構子Queue類,如下:


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

如上:

this.dataStore = []; 空數組時儲存佇列中所有的元素的。

2. 在隊尾中加入一個元素方法如下:


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

3. 刪除隊首的元素如下:


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

4. 讀取隊首的元素如下:


#

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

5. 讀取隊尾的元素如下:


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

6. 顯示佇列中的所有元素


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

7.判斷佇列是否為空如下:


#

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

以下是完整的JS程式碼如下:


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

二:使用佇列對資料進行排序

例如對於0 ~ 99 的數字進行排序,原理是:先將個位上的數字排序一次,然後再對十位上的數字進行排序一次。每個數字根據對應位上的數值被分在不同的盒子裡面,然後對於個位上的數字採用除餘數的方法,對於10位上的數字採用除法的方法,那麼這種排序叫做“基數排序” . 但是它不是最快的排序方法,但是它描述了一些有趣的隊列使用方法。

例如如下數組:


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

1. 經過基數排序--個位元排序後,數字被分配在不同的盒子裡面。 (在JS裡面,我們可以分配在不同的佇列Queue實例類別裡面)。如下


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]

2. 然後根據十位上的數值再將上次排序後的結果分配到不同的盒子中。如下:


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];

如上使用隊列列錶盒子,可以實現這個演算法,我們需要10個隊列,每個隊列對應一個數字,將所有佇列保存在一個陣列中,使用取餘和除法運算決定個位元和十位。演算法的剩餘部分將數字加入對應的佇列,根據個位數值重新排序,然後再根據十位上的數值進行排序,結果加入排序好的數字。

下面根據個位或十位上的數值,將數字分配到對應隊列的函數。


/*
* 根据个位或十位上的数值,将数字分配到相应队列的函数
* @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();
    }
  }
}

由於上面省略了很多步驟,可能描述的不是很清楚,我們現在先來看看流程圖,結合流程圖,最後結合JS的所有程式碼就可以理解"基數排序的"基本原理了;下面我們可以看看如下的流程圖;

最後是所有的JS程式碼如下:


#

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]);
    }
  }
};

下面的是對"基數排序的" JS程式碼進行測試;如下程式碼:


#

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);

相关推荐:

php中队列原理以及写文件的图文代码详解

详解JavaScript队列函数和异步执行

JavaScript队列函数和异步执行详解

以上是JavaScript佇列原理與用法實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn