隊(duì)列(Queue)
我們之前說到了棧，它是一種比較高效的數(shù)據(jù)結(jié)構(gòu)允华，遵循 先入后出(LIFO圈浇，last-in-first-out) 的原則。而今天我們要討論的隊(duì)列靴寂，它也是一種特殊的列表磷蜀，它與棧不同的是， 隊(duì)列只能在隊(duì)尾插入元素百炬，在隊(duì)首刪除元素褐隆，就像我們平時(shí)排隊(duì)買票一樣~
隊(duì)列用于存儲按順序排列的數(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 兩個方法。
除此之外屡穗，隊(duì)列還有一些其他的操作贴捡，比如讀取隊(duì)首的元素，該操作僅返回對頭元素并不將它從隊(duì)列中刪除村砂，類似棧的 peek 方法栈暇；back 方法讀取隊(duì)尾的元素；toString 方法可以打印當(dāng)前隊(duì)列中所有的元素箍镜；clear 方法清空當(dāng)前隊(duì)列等。
我們定義好數(shù)據(jù)類型煎源，可以通過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ì)列是否為空
}
我們先來實(shí)現(xiàn)入隊(duì)操作：
enqueue：向隊(duì)列添加元素
//向隊(duì)列末尾添加一個元素，直接調(diào)用 push 方法即可
function enqueue ( element ) {
this.dataStore.push( element );
}
因?yàn)镴S中的數(shù)組具有其他語言沒有的有點(diǎn)手销，可以直接利用 shift 方法刪除數(shù)組的第一個元素歇僧，因此，出隊(duì)操作的實(shí)現(xiàn)就變得很簡單了锋拖。
dequeue：刪除隊(duì)首的元素
//刪除隊(duì)列首的元素诈悍，可以利用 JS 數(shù)組中的 shift 方法
function dequeue () {
if( this.empty() ) return 'This queue is empty';
else this.dataStore.shift();
}
我們注意的，上面我做了一個判斷兽埃，隊(duì)列是否還有元素侥钳，因?yàn)槿h除空隊(duì)列的元素是沒有意義的，那么柄错，我們就來看看 empty 方法是如何實(shí)現(xiàn)的舷夺。
empty：判斷隊(duì)列是否為空
//我們通過判斷 dataStore 的長度就可知道隊(duì)列是否為空
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：查看隊(duì)首元素
//查看隊(duì)首元素敢伸，直接返回?cái)?shù)組首個元素即可
function front(){
if( this.empty() ) return 'This queue is empty';
else return this.dataStore[0]；
}
back：查看隊(duì)尾元素
//查看隊(duì)首元素恒削，直接返回?cái)?shù)組最后一個元素即可
//讀取隊(duì)列尾的元素
function back () {
if( this.empty() ) return 'This queue is empty';
else return this.dataStore[ this.dataStore.length - 1 ];
}
我們先看看對不對：
//查看隊(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
沒問題池颈！現(xiàn)在，我想看看钓丰，總共有多少水果饶辙，toString方法來實(shí)現(xiàn)，
toString：查看隊(duì)列中所有元素
//查看對了所有元素斑粱，我這里采用數(shù)組的 join 方法實(shí)現(xiàn)
function toString(){
return this.dataStore.join('\n');
}
現(xiàn)在弃揽，你可以看看你還有什么水果沒吃的了,
console.log( queue.toString() ) // Apple
// Banana
// Pear
我們就剩下一個 clear 方法了，如果你已經(jīng)把所有水果都吃完了，那么你應(yīng)該使用 clear 方法矿微，
//清空當(dāng)前隊(duì)列痕慢，也很簡單，我們直接將 dataStore 數(shù)值清空即可
function clear(){
delete this.dataStore;
this.dataStor = [];
}
至此涌矢，我們已經(jīng)用JS實(shí)現(xiàn)了一個隊(duì)列掖举，怎么樣，是不是覺得JS的數(shù)組超級好用娜庇，省去了不少麻煩塔次，有木有！名秀！
//清空隊(duì)列
queue.clear();
console.log( queue.empty() ); // true
下面励负，我們利用隊(duì)列來實(shí)現(xiàn)基數(shù)排序。
基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort）匕得，它是透過鍵值的部份資訊继榆，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用汁掠，基數(shù)排序法是屬于穩(wěn)定性的排序略吨，其時(shí)間復(fù)雜度為O (nlog(r)m)，其中r為所采取的基數(shù)考阱，而m為堆數(shù)翠忠，在某些時(shí)候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法乞榨。
先看一下基數(shù)排序的的實(shí)現(xiàn)步驟（以兩位數(shù)為例）负间，需要掃描兩次，第一次按個位數(shù)字進(jìn)行排序姜凄，第二次按十位數(shù)字排序政溃，每個數(shù)字根據(jù)對應(yīng)的數(shù)值分配到到不同的盒子里，最后將盒子的數(shù)字依次取出态秧，組成新的列表即為排序好的數(shù)字董虱。
- 假設(shè)我們有一串?dāng)?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é)合隊(duì)列去實(shí)現(xiàn)它帮匾，一起來看看吧奖慌。
//基數(shù)排序
var queues = []; //定義隊(duì)列數(shù)組
var nums = []; //定義數(shù)字?jǐn)?shù)組
//選十個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)的（個位和十位）數(shù)值昼窗，將數(shù)字分配到相應(yīng)隊(duì)列
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] );
}
}
}
//從隊(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();
}
}
}
我這里貼出兩組測試的結(jié)果累颂，大家自己動手實(shí)踐一下对人。
//第一組測試
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
至此谣殊，我們隊(duì)列也就告一段落了，大家還可以往深入拓展牺弄，比如優(yōu)先隊(duì)列姻几，循環(huán)隊(duì)列等，希望大家能發(fā)散思維势告，多動手實(shí)踐蛇捌，一起加油！
