数据结构与算法(2) - 队列

哈喽各位小伙伴，接着上一篇介绍了栈这个数据结构，这一篇我们来说一下队列，上一篇没看的同学可以先去看一下 [数据结构与算法(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));

小结

数据结构在系统设计中的应用非常广泛，只是我们水平达不到那个级别，知道的太少，但如果能理解并掌握这些数据结构，那么就有机会在工作中使用它们并解决一些具体的问题，当我们手里除了锤子还有电锯时，那么我们的眼里就不只是钉子，解决问题的思路也会更加开阔。