队列

队列的定义

队列是一种特殊的线性表，只允许在队列的头部进行删除元素，队列的尾部添加元素（先进先出）

queue1.png

左侧是队列的头部，右侧是队列的尾部，元素想进入队列，只能从尾部进入；想出队列，也只能从头部出去。

queue2.png

就像刷卡进地铁，只能从队尾一个个去排队，从最前面刷完卡就走了

队列的实现

跟栈一样，用数组来实现队列

队列的方法：

• enqueue: 从队列尾部添加一个元素
• dequeue: 从队列头部删除一个元素
• head: 返回队列头部的元素，不是删除
• tail: 返回队列尾部的元素
• size: 返回队列的大小
• clear: 清空队列
• isEmpty: 判断队列是否为空

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

队列的练习

练习一：约瑟夫环

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

思路分析：

所谓每隔两个数删掉一个数，假设有三个元素就删掉第三个，假设有六个元素就删掉第三个和第六个。。。由此可见就是删掉所在位置是3的倍数的元素

如果只删除一轮，用数组实现还可以，现在要求到末尾时循环至开头继续删除，用数组就很麻烦了，下标不好控制

那如何用队列来实现呢？

• 先循环数组把元素存进队列中
• 定义一个计数变量，用来计算是不是3的倍数
• 用while循环数组，直到队列大小是1为止
• 每次删除队首元素，计数变量+1，如果该元素所在位置不是3的倍数，再从队尾添加进去。这样一轮删除过后，队列里面就是剩下的没被删除的元素可以进行下一轮删除。

function delRing (arr) {
  const queue = new Queue();
  // 先把数组存入队列
  for (let i = 0; i < arr.length; i++) {
    queue.enqueue(arr[i]);
  }
  let index = 0; // 计数
  while(queue.size() !== 1) { // 只要队列长度不为1就继续循环
    const item = queue.dequeue(); // 从队列头部删除元素
    index++;
    if (index % 3 !== 0) { // 如果元素不能被3整除，就再次存入队列
      queue.enqueue(item);
    }
  }
  return queue.head();
}
const arr = [];
for (let i = 0; i < 100; i++) {
  arr[i] = i;
}
console.log(delRing(arr));

练习二：斐波那契数列

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

思路分析：

斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)

• 首先，前两项是已知的，先把它们放进队列
• 从第三项开始，值就是前两项的和。先从队列首部删除一个元素这是第一个值，再使用head()方法获得队列头部的元素这是第二个值，把这两个值相加就是第三项的值，把这个值从队列尾部加进队列(为什么第二次是用head()方法而不是dequeue(), 因为我们每次都是取两个值进行运算，如果使用dequeue()方法删除，下次计算的时候就只有一个值没法进行运算了)
• 因为我们每次都是删除一个值，再加进一个值，所以队列里面始终有两个元素。第二个元素就是第n项的值

function fibonacci (n) {
  const queue = new Queue();
  // 先把前两个元素放进队列
  queue.enqueue(1);
  queue.enqueue(1);
  for (let i = 2; i < n; i++) { // 因为前两个元素已知且已经放进队列，所以i从2开始
    const item1 = queue.dequeue(); // 第一个元素删除
    const item2 = queue.head(); // 第二个元素只是知道值就可以，不用删除，因为这个元素还要作为下一次计算的第一个值
    const sum = item1 + item2;
    queue.enqueue(sum); // 计算结果放进队列
  }
  return queue.tail(); // 尾部元素即是第n个元素的值
}
console.log(fibonacci(10));

练习三：用队列实现栈

用两个队列实现一个栈

思路分析：

主要记住队列是先进先出，栈是后进先出。

定义两个队列，queue1和queue2

• push方法：由于是两个队列，添加元素的时候要明确具体向哪个队列中添加。如果两个队列都为空，默认向queue1中添加；否则向不空的队列添加
• pop方法：对于栈来说，是删除栈顶元素，对于队列，就是队尾元素。由于队列只能从队首删除元素，所以要一直循环操作，删除队首元素并放进空队列中直到队列剩下一个元素为止，这个元素就是要删除的栈顶元素。删除并返回这个元素
• top方法：返回栈顶元素，也就是队列的队尾元素。找到不为空的队列，返回队尾元素即可

可以发现每进行一次pop操作，空队列和不为空的队列就要做一次元素的转移。原本queue1不为空，pop操作完后就变成空的了。所以我们再定义两个变量，一个指向非空队列，一个指向空队列。

const Queue = require('./myQueue.js');
function QueueStack () {
  const queue1 = new Queue();
  const queue2 = new Queue();
  let dataQueue = null;  // 放数据的队列
  let emptyQueue = null; // 空队列，备份使用

  function initQueue () { // 确认放数据的队列和空队列的指向
    if (queue1.isEmpty() && queue2.isEmpty()) { // 如果都为空，默认放数据的队列指向queue1
      dataQueue = queue1;
      emptyQueue = queue2;
    } else if (queue1.isEmpty()) {
      dataQueue = queue2;
      emptyQueue = queue1;
    } else if (queue2.isEmpty()) {
      dataQueue = queue1;
      emptyQueue = queue2;
    }
  }

  this.push = function (item) {
    initQueue();
    dataQueue.enqueue(item);
  }
  
  this.pop = function () {
    initQueue();
    while(dataQueue.size() !== 1) {
      const item = dataQueue.dequeue();
      emptyQueue.enqueue(item);
    }
    return dataQueue.dequeue();
  }

  this.top = function () {
    initQueue();
    return dataQueue.tail();
  }
}
const qStack = new QueueStack();
qStack.push(1);
qStack.push(2);
qStack.push(4);
console.log(qStack.top());   // 栈顶是 4
console.log(qStack.pop());   // 移除 4
console.log(qStack.top());   // 栈顶变成 2
console.log(qStack.pop());   // 移除 2
console.log(qStack.pop());

练习四：打印杨辉三角

使用队列打印出杨辉三角的前n行，n >= 1

思路分析：

杨辉三角示意图：

yanghui.jpeg

杨辉三角中的每一行，都依赖于上一行。假设在队列里存储第n-1行的数据，输出第n行时，只需要将队列里的数据依次出队列，进行计算得到下一行的数值并将计算所得放入到队列中。

计算方式： f[i][j] = f[i-1][j-1]+f[i-1][j], i代表行数，j代表一行的第几个数，如果j=0或者j===i, 则f[i][j] = 1;

• 定义一个字符串变量来存储结果，默认是1，存储第一行的结果
• 把1存入队列，以便后续计算
• 我们是将第n-1行的数据依次取出进行计算，然后再将结果存入队列。所以这时候队列中是存的两行的数据，需要区分到哪个位置为止停止计算也就是标记一下第n-1行的数据什么时候结束。这里我们在一行的数据结尾再存入一个0作为区分

function printYanghui (n) {
  if (n < 1) {
    console.error('n必须大于等于1');
    return;
  }
  let line = '1';
  const queue = new Queue();
  queue.enqueue(1);
  queue.enqueue(0);

  for (let i = 1; i < n; i++) { // 第一行数据1已经默认存储了，所以i从1开始
    line += '\n'; // 换行，每轮循环代表一行数据
    line += '1 '; // f[i][0] = 1
    queue.enqueue(1)
    while(queue.head() !== 0) { // 队列头部元素是0代表这行元素结束了
      // 取出n-1行两个元素进行计算，并将结果存入队列
      const item1 = queue.dequeue(); // 第一个元素删除
      const item2 = queue.head();    // 第二个元素取出不删除，因为它还要参与第n行下个元素的计算
      const res = item1 + item2;
      line += `${res} `;
      queue.enqueue(res);
    }
    queue.dequeue(); // 把第n-1行的0删除
    queue.enqueue(0); // 第n行末尾添加0
  }
  return line;
}
console.log(printYanghui(10));