数据结构—-队列

1、队列的定义

队列是一种特殊的线性表，其特殊之处在于，它只允许你在队列的头部删除元素，在队列的末尾添加新的元素。

2、队列的方法

• enqueue 从队列尾部添加一个元素（新来一个排队的人，文明礼貌，站在了队伍末尾）
• dequeue 从队列头部删除一个元素（排队伍最前面的人刚办理完登机手续，离开了队伍）
• head 返回头部的元素，注意，不是删除（只是看一下，谁排在最前面）
• size 返回队列大小（数一数有多少人在排队）
• clear 清空队列（航班取消，大家都散了吧）
• isEmpty 判断队列是否为空 （看看是不是有人在排队）
• tail 返回队列尾节点

3、实现队列

这里先用数组的方式实现。如下：

function Queue () {
    var items = [];
    this.enqueue = function(item){
        items.push(item)
    }
    this.dequeue = function(){
        items.shift()
    }
    this.head = function(){
        return items[0]
    }
    this.size = function(){
        return items.length
    }
    this.clear = function(){
        items = []
    }
    this.isEmpty = function(){
        return items.length === 0
    }
    this.tail = function(){
        return items[items.length-1]
    }
}
 

4、队列的小练习

Q1:   约瑟夫环问题。有一个数组a[100]存放0--99;要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数。

上代码：

function del_circle(arr){
    var _queue = new Queue();
    var index = 0;
    // 把数组中的元素入栈
    for(var i=0;i<arr.length;i++){
        _queue.enqueue(arr[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 = [];
for(var i=0;i<100;i++){
    arr.push(i);
}
console.log(del_circle(arr));
 

思路：

准备好一个队列（头部可删除元素，尾部添加元素），将100个数入栈。每隔两个删除一个，并将这两个数放到队列的末尾。每隔3取余，找到这个要删除的数，用 index 做标记，前两个数入队列。依次循环这样。。。。

Q2:  斐波那契数列

前两项是 1  1，以后每项是前两项之和，即 f(n) = f(n-1) + f(n-2)。

1、递归方式实现：

function fibonacci(n){
    if(n<=2) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}
 

2、队列实现

function fibonacci(n){  var queue = new Queue();  var index = 0; // 计数用来实现每3个删除一个  // 先放入斐波那契序列的前两个数值  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();}
 

思路：

将每次前两项相加之和从队尾入队列，先放入两个数到队列中，将队列头部删除的元素记为 del_item, 这是队列中剩余 head_item , 两者相加 得 next_item 再将其从队尾入队列。