哈喽各位小伙伴，接着上一篇介绍了栈这个数据结构，这一篇我们来说一下队列，上一篇没看的同学可以先去看一下 数据结构与算法(1) - 栈
队列的定义
队列是一种特殊的线性表，其特殊之处在于，它只允许你在队列的头部删除元素，在队列的末尾添加新的元素。
下面这张图展示了队列如何添加新的元素
左侧是队列的头部，右侧是队列的尾部，新的元素如果想进入队列，只能从尾部进入，如果想要出队列，只能从队列的头部出去,下面的图展示了元素如何出队列
日常生活中，排队就是典型的队列结构，下面这幅图里，大家在排队办理登机手续。
1. 队列的实现
有了栈这个数据结构做铺垫，队列就很容易学了
数据存储
同栈一样，本课程里队列的实现也使用数组来存储数据，定义一个简单的Queue类
function Queue(){
var items = []; // 存储数据
};
2. 队列的方法
队列的方法如下:
- enqueue 从队列尾部添加一个元素（新来一个排队的人，文明礼貌，站在了队伍末尾）
- dequeue 从队列头部删除一个元素（排队伍最前面的人刚办理完登机手续，离开了队伍）
- head 返回头部的元素，注意，不是删除（只是看一下，谁排在最前面）
- size 返回队列大小（数一数有多少人在排队）
- clear 清空队列（航班取消，大家都散了吧）
- isEmpty 判断队列是否为空 （看看是不是有人在排队）
- tail 返回队列尾节点
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 = []; // 存储数据
// 向队列尾部添加一个元素
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.队列的应用
3.1 约瑟夫环
3.1.1 题目要求
有一个数组a[100]存放0--99;要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数。
3.1.2 思路分析
前10个数是 0 1 2 3 4 5 6 7 8 9 10，所谓每隔两个数删掉一个数，其实就是把 2 5 8 删除掉，如果只是从0 到 99 每个两个数删掉一个数，其实挺简单的，可是题目要求到末尾时还有循环至开头继续进行。
如果是用数组，问题就又显得麻烦了，关键是到了末尾如何回到开头重新来一遍，还得考虑把删除掉的元素从数组中删除。
如果用队列就简单了，先将这100个数放入队列，使用while循环，while循环终止的条件是队列里只有一个元素。使用index变量从0开始计数，算法步骤如下:
1. 从队列头部删除一个元素，index+1
2. 如果index%3 == 0,就说明这个元素是需要删除的元素，如果不等于0，就不是需要被删除的元素，则把它添加到队列的尾部
不停的有元素被删除，最终队列里只有一个元素，此时while循环终止，队列的所剩的元素就是最后一个被删除的元素。
3.1.3 示例代码
function del_ring(arr_list){
// 把数组里的元素都放入到队列中
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();
};
// 准备好数据
var arr_list = [];
for(var i=0;i< 100;i++){
arr_list.push(i);
}
console.log(del_ring(arr_list));
3.2 斐波那契数列
斐波那契数列是一个非常经典的问题，有着各种各样的解法，比较常见的是递归算法，其实也可以使用队列来实现
3.2.1 题目要求
计算斐波那契数列的第n项
3.2.2 思路分析
斐波那契数列的前两项是 1 1 ，此后的每一项都是该项前面两项之和，即f(n) = f(n-1) + f(n-2)。
如果使用数组来实现，究竟有多麻烦了我就不赘述了，直接考虑使用队列来实现。
先将两个1 添加到队列中，之后使用while循环，用index计数，循环终止的条件是index < n -2
- 使用dequeue方法从队列头部删除一个元素，该元素为del_item
- 使用head方法获得队列头部的元素，该元素为 head_item
- del_item + head_item = next_item,将next_item放入队列，注意，只能从尾部添加元素
- index+1
当循环结束时，队列里面有两个元素，先用dequeue 删除头部元素，剩下的那个元素就是我们想要的答案
3.2.3 示例代码
function fibonacci(n){
queue = new Queue();
var index = 0;
// 先放入斐波那契序列的前两个数值
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;
// 将计算结果放入队列
queue.enqueue(next_item);
index += 1;
}
queue.dequeue();
return queue.head();
};
console.log(fibonacci(8));
小结
数据结构在系统设计中的应用非常广泛，只是我们水平达不到那个级别，知道的太少，但如果能理解并掌握这些数据结构，那么就有机会在工作中使用它们并解决一些具体的问题，当我们手里除了锤子还有电锯时，那么我们的眼里就不只是钉子，解决问题的思路也会更加开阔。
