哈嘍各位小伙伴杠纵，接著上一篇介紹了棧這個數(shù)據(jù)結(jié)構(gòu)比藻，這一篇我們來說一下隊列倘屹，上一篇沒看的同學(xué)可以先去看一下 數(shù)據(jù)結(jié)構(gòu)與算法(1) - 棧
隊列的定義
隊列是一種特殊的線性表纽匙，其特殊之處在于烛缔，它只允許你在隊列的頭部刪除元素，在隊列的末尾添加新的元素烟央。
下面這張圖展示了隊列如何添加新的元素
左側(cè)是隊列的頭部，右側(cè)是隊列的尾部，新的元素如果想進(jìn)入隊列梯影，只能從尾部進(jìn)入，如果想要出隊列甲棍，只能從隊列的頭部出去,下面的圖展示了元素如何出隊列
日常生活中感猛，排隊就是典型的隊列結(jié)構(gòu)陪白，下面這幅圖里膳灶，大家在排隊辦理登機(jī)手續(xù)。
1. 隊列的實現(xiàn)
有了棧這個數(shù)據(jù)結(jié)構(gòu)做鋪墊序厉，隊列就很容易學(xué)了
數(shù)據(jù)存儲
同棧一樣弛房，本課程里隊列的實現(xiàn)也使用數(shù)組來存儲數(shù)據(jù)霉晕，定義一個簡單的Queue類
function Queue(){
var items = []; // 存儲數(shù)據(jù)
};
2. 隊列的方法
隊列的方法如下:
- enqueue 從隊列尾部添加一個元素（新來一個排隊的人拄轻，文明禮貌伟葫，站在了隊伍末尾）
- dequeue 從隊列頭部刪除一個元素（排隊伍最前面的人剛辦理完登機(jī)手續(xù)，離開了隊伍）
- head 返回頭部的元素常拓，注意弄抬，不是刪除（只是看一下掂恕，誰排在最前面）
- size 返回隊列大邪猛觥（數(shù)一數(shù)有多少人在排隊）
- clear 清空隊列（航班取消乎串，大家都散了吧）
- isEmpty 判斷隊列是否為空 （看看是不是有人在排隊）
- tail 返回隊列尾節(jié)點
2.1 enqueue方法
// 向隊列尾部添加一個元素
this.enqueue = function(item){
items.push(item);
};
2.2 dequeue方法
// 移除隊列頭部的元素
this.dequeue = function(){
return items.shift();
};
2.3 head方法
// 返回隊列頭部的元素
this.head = function(){
return items[0];
}
2.4 size方法
// 返回隊列大小
this.size = function(){
return items.length;
}
2.5 clear方法
// clear
this.clear = function(){
items = [];
}
2.6 isEmpty方法
// isEmpty 判斷是否為空隊列
this.isEmpty = function(){
return items.length == 0;
}
2.7 tail方法
// 返回隊列尾部的元素
this.tail = function(){
return items[items.length-1];
};
完整代碼如下
function Queue(){
var items = []; // 存儲數(shù)據(jù)
// 向隊列尾部添加一個元素
this.enqueue = function(item){
items.push(item);
};
// 移除隊列頭部的元素
this.dequeue = function(){
return items.shift();
};
// 返回隊列頭部的元素
this.head = function(){
return items[0];
}
// 返回隊列大小
this.size = function(){
return items.length;
}
// clear
this.clear = function(){
items = [];
}
// isEmpty 判斷是否為空隊列
this.isEmpty = function(){
return items.length == 0;
}
};
3.隊列的應(yīng)用
3.1 約瑟夫環(huán)
3.1.1 題目要求
有一個數(shù)組a[100]存放0--99;要求每隔兩個數(shù)刪掉一個數(shù)店枣，到末尾時循環(huán)至開頭繼續(xù)進(jìn)行，求最后一個被刪掉的數(shù)叹誉。
3.1.2 思路分析
前10個數(shù)是 0 1 2 3 4 5 6 7 8 9 10鸯两，所謂每隔兩個數(shù)刪掉一個數(shù)，其實就是把 2 5 8 刪除掉桂对，如果只是從0 到 99 每個兩個數(shù)刪掉一個數(shù)甩卓，其實挺簡單的鸠匀，可是題目要求到末尾時還有循環(huán)至開頭繼續(xù)進(jìn)行蕉斜。
如果是用數(shù)組，問題就又顯得麻煩了缀棍，關(guān)鍵是到了末尾如何回到開頭重新來一遍宅此，還得考慮把刪除掉的元素從數(shù)組中刪除父腕。
如果用隊列就簡單了，先將這100個數(shù)放入隊列，使用while循環(huán)，while循環(huán)終止的條件是隊列里只有一個元素竞阐。使用index變量從0開始計數(shù)，算法步驟如下:
1. 從隊列頭部刪除一個元素峭火，index+1
2. 如果index%3 == 0,就說明這個元素是需要刪除的元素稍浆，如果不等于0，就不是需要被刪除的元素，則把它添加到隊列的尾部
不停的有元素被刪除益楼，最終隊列里只有一個元素粒督，此時while循環(huán)終止，隊列的所剩的元素就是最后一個被刪除的元素。
3.1.3 示例代碼
function del_ring(arr_list){
// 把數(shù)組里的元素都放入到隊列中
var queue = new Queue();
for(var i=0;i< arr_list.length;i++){
queue.enqueue(arr_list[i]);
}
var index = 0;
while(queue.size() != 1){
// 彈出一個元素,判斷是否需要刪除
var item = queue.dequeue();
index += 1;
// 每隔兩個就要刪除掉一個,那么不是被刪除的元素就放回到隊列尾部
if(index %3 != 0){
queue.enqueue(item);
}
}
return queue.head();
};
// 準(zhǔn)備好數(shù)據(jù)
var arr_list = [];
for(var i=0;i< 100;i++){
arr_list.push(i);
}
console.log(del_ring(arr_list));
3.2 斐波那契數(shù)列
斐波那契數(shù)列是一個非常經(jīng)典的問題，有著各種各樣的解法劳翰，比較常見的是遞歸算法颖变，其實也可以使用隊列來實現(xiàn)
3.2.1 題目要求
計算斐波那契數(shù)列的第n項
3.2.2 思路分析
斐波那契數(shù)列的前兩項是 1 1 马胧，此后的每一項都是該項前面兩項之和垫卤，即f(n) = f(n-1) + f(n-2)。
如果使用數(shù)組來實現(xiàn)，究竟有多麻煩了我就不贅述了，直接考慮使用隊列來實現(xiàn)。
先將兩個1 添加到隊列中，之后使用while循環(huán)厌均，用index計數(shù)擒悬，循環(huán)終止的條件是index < n -2
- 使用dequeue方法從隊列頭部刪除一個元素僧凤，該元素為del_item
- 使用head方法獲得隊列頭部的元素澎语，該元素為 head_item
- del_item + head_item = next_item,將next_item放入隊列盯孙，注意骑晶，只能從尾部添加元素
- index+1
當(dāng)循環(huán)結(jié)束時漫谷，隊列里面有兩個元素惕稻，先用dequeue 刪除頭部元素俺祠，剩下的那個元素就是我們想要的答案
3.2.3 示例代碼
function fibonacci(n){
queue = new Queue();
var index = 0;
// 先放入斐波那契序列的前兩個數(shù)值
queue.enqueue(1);
queue.enqueue(1);
while(index < n-2){
// 出隊列一個元素
var del_item = queue.dequeue();
// 取隊列頭部元素
var head_item = queue.head();
var next_item = del_item + head_item;
// 將計算結(jié)果放入隊列
queue.enqueue(next_item);
index += 1;
}
queue.dequeue();
return queue.head();
};
console.log(fibonacci(8));
小結(jié)
數(shù)據(jù)結(jié)構(gòu)在系統(tǒng)設(shè)計中的應(yīng)用非常廣泛，只是我們水平達(dá)不到那個級別淌铐，知道的太少，但如果能理解并掌握這些數(shù)據(jù)結(jié)構(gòu)，那么就有機(jī)會在工作中使用它們并解決一些具體的問題释涛，當(dāng)我們手里除了錘子還有電鋸時唇撬，那么我們的眼里就不只是釘子烧给，解決問題的思路也會更加開闊酝惧。
