线性表-队列

队列是一种特殊的线性表，其特殊是值允许在队列的头部删除元素，在队列的尾部添加新的元素。

• 队列的实现
• 队列的应用

队列的实现

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;
  };
  // 清空队列
  this.clear = function () {
    items = [];
  };
  // 判断是否为空队列
  this.isEmpty = function () {
    return items.length == 0;
  };
}

基于连边实现队列

function Queue() {
  var linklist = new LinkList();
  // ⼊队列
  this.enqueue = function (item) {
    linklist.append(item);
  };
  // 出队列
  this.dequeue = function () {
    return linklist.remove_head();
  };
  // 返回队⾸
  this.head = function () {
    return linklist.head();
  };
  // 返回队尾
  this.tail = function () {
    return linklist.tail();
  };
  // size
  this.size = function () {
    return linklist.length();
  };
  //clear
  this.clear = function () {
    linklist.clear();
  };
  // isEmpty
  this.isEmpty = function () {
    return linklist.isEmpty();
  };
}

队列的应用

1. 约瑟夫环

   有一个数组a[100]存放0-99；要求每隔两个数删掉一个数，到末尾至开头继续进行，求最后一个被删除的数字。
   

   实例代码

   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));
   

2. 斐波那契数列

   使用队列计算斐波那契数列的第n项。
   

   详情

   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));