快捷導(dǎo)航

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

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

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

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

隊(duì)列(Queue)

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

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

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

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

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

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

隊(duì)列的實(shí)現(xiàn)

//定義隊(duì)列

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

我們先來(lái)實(shí)現(xiàn)入隊(duì)操作：

enqueue：向隊(duì)列添加元素

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

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

因?yàn)镴S中的數(shù)組具有其他語(yǔ)言沒(méi)有的有點(diǎn)，可以直接利用 shift 方法刪除數(shù)組的第一個(gè)元素，因此，出隊(duì)操作的實(shí)現(xiàn)就變得很簡(jiǎn)單了。

dequeue：刪除隊(duì)首的元素

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

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

我們注意的，上面我做了一個(gè)判斷，隊(duì)列是否還有元素，因?yàn)槿h除空隊(duì)列的元素是沒(méi)有意義的，那么，我們就來(lái)看看 empty 方法是如何實(shí)現(xiàn)的。

empty：判斷隊(duì)列是否為空

//我們通過(guò)判斷 dataStore 的長(zhǎng)度就可知道隊(duì)列是否為空

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

我們先來(lái)看看測(cè)試一下這幾個(gè)方法，

var queue = new Queue();

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

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

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

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

front：查看隊(duì)首元素

//查看隊(duì)首元素，直接返回?cái)?shù)組首個(gè)元素即可

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

back：查看隊(duì)尾元素

//查看隊(duì)首元素，直接返回?cái)?shù)組最后一個(gè)元素即可

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

我們先看看對(duì)不對(duì)：

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

//出隊(duì)
queue.dequeue();

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

沒(méi)問(wèn)題！現(xiàn)在，我想看看，總共有多少水果，toString方法來(lái)實(shí)現(xiàn)，

toString：查看隊(duì)列中所有元素

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

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

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

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

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

//清空當(dāng)前隊(duì)列，也很簡(jiǎn)單，我們直接將 dataStore 數(shù)值清空即可

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

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

//清空隊(duì)列

queue.clear();

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

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

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

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

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

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

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

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

//基數(shù)排序

var queues = []; //定義隊(duì)列數(shù)組
var nums = [];  //定義數(shù)字?jǐn)?shù)組

//選十個(gè)0~99的隨機(jī)數(shù)進(jìn)行排序
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)的（個(gè)位和十位）數(shù)值，將數(shù)字分配到相應(yīng)隊(duì)列

function distribution ( nums , queues , n , digit ) { //digit表示個(gè)位或者十位的值
 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ù)字

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

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

//第一組測(cè)試

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

//第二組測(cè)試

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

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

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

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

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

您可能感興趣的文章: