快捷導(dǎo)航

JS中的算法與數(shù)據(jù)結(jié)構(gòu)之隊列(Queue)實例詳解

更新時間：2019年08月20日 09:20:40 作者：Cryptic

這篇文章主要介紹了JS中的算法與數(shù)據(jù)結(jié)構(gòu)之隊列(Queue),結(jié)合實例形式詳細分析了javascript中隊列的概念、原理、定義及常見操作技巧,需要的朋友可以參考下

本文實例講述了JS中的算法與數(shù)據(jù)結(jié)構(gòu)之隊列(Queue)。分享給大家供大家參考，具體如下：

隊列(Queue)

我們之前說到了棧，它是一種比較高效的數(shù)據(jù)結(jié)構(gòu)，遵循先入后出(LIFO，last-in-first-out) 的原則。而今天我們要討論的隊列，它也是一種特殊的列表，它與棧不同的是，隊列只能在隊尾插入元素，在隊首刪除元素，就像我們平時排隊買票一樣~

隊列用于存儲按順序排列的數(shù)據(jù)，遵循先進先出(FIFO，F(xiàn)irst-In-First-Out) 的原則，也是計算機常用的一種數(shù)據(jù)結(jié)構(gòu)，別用于很多地方，比如提交給操作系統(tǒng)的一系列進程，打印池任務(wù)等。

同棧有點類似，隊列的操作主要也是有兩種：向隊列中插入新元素和刪除隊列中的元素，即入隊和出隊操作，我們采用 enqueue 和 dequeue 兩個方法。

除此之外，隊列還有一些其他的操作，比如讀取隊首的元素，該操作僅返回對頭元素并不將它從隊列中刪除，類似棧的 peek 方法；back 方法讀取隊尾的元素；toString 方法可以打印當前隊列中所有的元素；clear 方法清空當前隊列等。

隊列數(shù)據(jù)定義

我們定義好數(shù)據(jù)類型，可以通過JS中的數(shù)組去實現(xiàn)它。

隊列的實現(xiàn)

//定義隊列

function Queue(){
 this.dataStore = [];
 this.enqueue = enqueue;  //入隊
 this.dequeue = dequeue;  //出隊
 this.front = front;   //查看隊首元素
 this.back = back;   //查看隊尾元素
 this.toString = toString; //顯示隊列所有元素
 this.clear = clear;   //清空當前隊列
 this.empty = empty;   //判斷當前隊列是否為空
}

我們先來實現(xiàn)入隊操作：

enqueue：向隊列添加元素

//向隊列末尾添加一個元素，直接調(diào)用 push 方法即可

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

因為JS中的數(shù)組具有其他語言沒有的有點，可以直接利用 shift 方法刪除數(shù)組的第一個元素，因此，出隊操作的實現(xiàn)就變得很簡單了。

dequeue：刪除隊首的元素

//刪除隊列首的元素，可以利用 JS 數(shù)組中的 shift 方法

function dequeue () {
 if( this.empty() ) return 'This queue is empty';
 else this.dataStore.shift();
}

我們注意的，上面我做了一個判斷，隊列是否還有元素，因為去刪除空隊列的元素是沒有意義的，那么，我們就來看看 empty 方法是如何實現(xiàn)的。

empty：判斷隊列是否為空

//我們通過判斷 dataStore 的長度就可知道隊列是否為空

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

我們先來看看測試一下這幾個方法，

var queue = new Queue();

console.log( queue.empty() );  //true

//添加幾個元素
queue.enqueue('Apple');
queue.enqueue('Banana');
queue.enqueue('Pear');

console.log( queue.empty() );  // false

現(xiàn)在，我不知道誰在第一個，誰是最后一個，我們可以利用 front 和 back 方法分別來查看，

front：查看隊首元素

//查看隊首元素，直接返回數(shù)組首個元素即可

function front(){
 if( this.empty() ) return 'This queue is empty';
 else return this.dataStore[0]；
}

back：查看隊尾元素

//查看隊首元素，直接返回數(shù)組最后一個元素即可

//讀取隊列尾的元素
function back () {
 if( this.empty() ) return 'This queue is empty';
 else return this.dataStore[ this.dataStore.length - 1 ];
}

我們先看看對不對：

//查看隊首元素
console.log( queue.front() ); // Apple
//查看隊尾元素 
console.log( queue.back() ); // Pear

//出隊
queue.dequeue();

//查看隊首元素
console.log( queue.front() ); // Banana
//查看隊尾元素 
console.log( queue.back() ); // Pear

沒問題！現(xiàn)在，我想看看，總共有多少水果，toString方法來實現(xiàn)，

toString：查看隊列中所有元素

//查看對了所有元素，我這里采用數(shù)組的 join 方法實現(xiàn)

function toString(){
 return this.dataStore.join('\n');
}

現(xiàn)在，你可以看看你還有什么水果沒吃的了,

console.log( queue.toString() )  // Apple
         // Banana
         // Pear

我們就剩下一個 clear 方法了，如果你已經(jīng)把所有水果都吃完了，那么你應(yīng)該使用 clear 方法，

//清空當前隊列，也很簡單，我們直接將 dataStore 數(shù)值清空即可

function clear(){
 delete this.dataStore;
 this.dataStor = [];
}

至此，我們已經(jīng)用JS實現(xiàn)了一個隊列，怎么樣，是不是覺得JS的數(shù)組超級好用，省去了不少麻煩，有木有??！

//清空隊列

queue.clear();

console.log( queue.empty() ); // true

下面，我們利用隊列來實現(xiàn)基數(shù)排序。

基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時間復(fù)雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。

先看一下基數(shù)排序的的實現(xiàn)步驟（以兩位數(shù)為例），需要掃描兩次，第一次按個位數(shù)字進行排序，第二次按十位數(shù)字排序，每個數(shù)字根據(jù)對應(yīng)的數(shù)值分配到到不同的盒子里，最后將盒子的數(shù)字依次取出，組成新的列表即為排序好的數(shù)字。

假設(shè)我們有一串數(shù)字，分別為 73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根據(jù)個位數(shù)字排序，放到不同的盒子里，如下圖

第一次排序
接下來將這些盒子中的數(shù)值重新串接起來，成為以下的數(shù)列：81, 22, 73, 93, 43, 14, 55, 65, 28, 39
然后根據(jù)十位數(shù)字排序，再放到不同的盒子里，如下圖

第二次排序
接下來將這些盒子中的數(shù)值重新串接起來，整個數(shù)列已經(jīng)排序完畢：14, 22, 28, 39, 43, 55, 65, 73, 81, 93

我們已經(jīng)了解了基數(shù)排序的算法思想，接著我們要結(jié)合隊列去實現(xiàn)它，一起來看看吧。

//基數(shù)排序

var queues = []; //定義隊列數(shù)組
var nums = [];  //定義數(shù)字數(shù)組

//選十個0~99的隨機數(shù)進行排序
for ( var i = 0 ; i < 10 ; i ++ ){
 queues[i] = new Queue();
 nums[i] = Math.floor( Math.random() * 101 );
}

//排序之前
console.log( 'before radix sort: ' + nums );

//基數(shù)排序
distribution( nums , queues , 10 , 1 );
collect( queues , nums );
distribution( nums , queues , 10 , 10 );
collect( queues , nums );

//排序之后
console.info('after radix sort: ' + nums );

//根據(jù)相應(yīng)的（個位和十位）數(shù)值，將數(shù)字分配到相應(yīng)隊列

function distribution ( nums , queues , n , digit ) { //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ù)字

function collect ( queues , nums ) {
 var i = 0;
 for ( var digit = 0 ; digit < 10 ; digit ++ ){
  while ( !queues[digit].empty() ){
   nums[ i++ ] = queues[digit].front();
   queues[digit].dequeue();
  }
 }
}

我這里貼出兩組測試的結(jié)果，大家自己動手實踐一下。

//第一組測試

before radix sort: 23,39,2,67,90,41,47,21,98,13
after radix sort: 2,13,21,23,39,41,47,67,90,98

//第二組測試

before radix sort: 29,62,38,16,55,26,33,54,76,65
after radix sort: 16,26,29,33,38,54,55,62,65,76

至此，我們隊列也就告一段落了，大家還可以往深入拓展，比如優(yōu)先隊列，循環(huán)隊列等，希望大家能發(fā)散思維，多動手實踐，一起加油！

感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運行工具：http://tools.jb51.net/code/HtmlJsRun測試上述代碼運行效果。

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)學運算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)》

希望本文所述對大家JavaScript程序設(shè)計有所幫助。

您可能感興趣的文章: