# 队列

# 定义

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

下图展示队列如何添加新的元素

左侧是队列的头部，右侧是队列的尾部，新的元素如果想进入队列，只能从尾部进入，如果想要出队列，只能从队列的头部出去，下面的图展示了元素如何出队列

日常生活中，排队就是典型的队列结构。

# 队列的实现

队列的方法有

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

用数组实现队列

class Queue {
  construtor() {
    this.items = [];
  }

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    return this.items.shift();
  }

  head() {
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items.length = 0;
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# 队列的应用

# 斐波那契数列

斐波那契数列的前两项是 1,1，此后每一项都是该项前两项之和，即 f(n) = f(n-1) + f(n-2)。

斐波那契数列是一个非常经典的问题，有着各种各样的解法，比较常见的是递归算法，其实也可以用队列来实现。

递归实现

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

1
2
3
4
5
6
7

队列实现

思路

现将两个 1 添加到队列中，之后使用 while 循环，用 index 计数，循环终止条件是 index < n-2

使用 dequeue 方法从队列头部删除一个元素，该元素为 delItem
使用 head 方法获得列头元素，该元素为 headItem
delItem + headItem 等于 nextItem，将 nextItem 放入队列，注意，只能从尾部添加元素
index+1
当循环结束时，队列有两个元素，先用 dequeue 删除头部元素，剩下的那个元素就是要的答案

function fibonacci(n) {
  var queue = new Queue();
  var index = 0;
  // 先放入斐波那契数列最前面两个数值
  queue.enqueue(1);
  queue.enqueue(1);

  while (index < n - 2) {
    // 出列一个元素
    var delItem = queue.dequeue();
    // 取得头部元素
    var headItem = queue.head();

    var nextItem = delItem + headItem;

    // 计算结果入列
    queue.enqueue(nextItem);
    index += 1;
  }
  queue.dequeue();
  return queue.head();
}

console.log(fibonacci(8)); // 21

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 异步队列

多个 ajax 依次请求，每个请求都在前面请求执行完之后才请求

先创建一个生成 ajax 请求的函数，在每一个请求结束之后，执行一个 next 函数，next 的作用就是定位执行请求的 ajax 函数

function createAjaxFn(query) {
  return function() {
    $.get({
      url: `https://api.apiopen.top/likePoetry?name=${query}`,
      success: function(res) {
        console.log(res);
        next();
      }
    });
  };
}

1
2
3
4
5
6
7
8
9
10
11

创建一个队列，ajax 请求入列

var queue = new Queue();

queue.enqueue(createAjaxFn("锦瑟无端五十弦"));
queue.enqueue(createAjaxFn("至今思项羽"));
queue.enqueue(createAjaxFn("十步杀一人"));
queue.enqueue(createAjaxFn("李清照"));
queue.enqueue(createAjaxFn("王维"));
queue.enqueue(createAjaxFn("李白"));
queue.enqueue(createAjaxFn("杜甫"));
queue.enqueue(createAjaxFn("白居易"));
queue.enqueue(createAjaxFn("刘禹锡"));

1
2
3
4
5
6
7
8
9
10
11

定义 next 函数

function next() {
  // 如果队列为空，则队列里请求都执行完了
  if (queue.isEmpty()) {
    console.log("执行完成了");
    return;
  }
  // 出列一个请求
  var target = queue.dequeue();
  // 执行出列的元素
  target();
}

1
2
3
4
5
6
7
8
9
10
11

执行 next()函数，开始队列 ajax 请求

next();

可以添加一个阈值，让请求最多同时请求 n 个，以达到效率最优。

function run(n) {
  for (var i = 0; i < n; i++) {
    next();
  }
}
// 传入阈值
run(3);

1
2
3
4
5
6
7

# 树形数据转换

var data = [
  {
    id: 1,
    title: "a",
    pid: 0
  },
  {
    id: 2,
    title: "a1",
    pid: 1
  },
  {
    id: 3,
    title: "a11",
    pid: 2
  },
  {
    id: 4,
    title: "a12",
    pid: 2
  },
  {
    id: 5,
    title: "a2",
    pid: 1
  },
  {
    id: 6,
    title: "a21",
    pid: 5
  }
];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

转为树形结构

function listConvertTree(list) {
  var root = null;
  if (!list.length) {
    return root;
  }
  var group = {};
  for (var i = 0; i < list.length; i++) {
    var item = list[i];
    if (item.pid) {
      // 将非根节点存储在hashMap中，pid和节点一一对应
      if (!group[item.pid]) {
        group[item.pid] = [];
      }
      group[item.pid].push(item);
    } else {
      // 获取根节点
      root = {
        id: item.id,
        pid: item.pid,
        title: item.title,
        children: []
      };
    }
  }
  var queue = [];
  queue.push(root);
  while (queue.length) {
    var node = queue.shift();
    node.children =
      group[node.id] && group[node.id].length ? group[node.id] : null;
    if (node.children) {
      [].push.apply(queue, node.children);
    }
  }
  return root;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

树形遍历

树形转为列表

function treeConvertList(node) {
  var list = [];
  if (node === null) {
    return;
  }
  var queue = [];
  queue.push(node);
  var target;
  while (queue.length) {
    target = queue.shift();
    list.push({
      id: target.id,
      title: target.title,
      pid: target.pid
    });
    [].push.apply(queue, target.children);
  }
  return list;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 打印杨辉三角

杨辉三角每一行，都依赖于上一行，假设在队列里存储第 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。

但是将计算所得反入到队列中时，队列中保存的是两行数据，一部分是第 n-1 行，另一部分是刚刚计算出来的第 n 行数据，需要有办法将这两行数据分隔开。

分开的方式有两种，一种是 for 循环进行控制，在输出第 5 行时，其实只有 5 个数据可以输出，那么就可以使用 for 循环控制调用 enqueue 的次数，循环 5 次后，队列里存储的就是计算好的第 6 行数据。

第二种方法是每一行的数据后面多存储个 0，使用 0 作为分界点，如果 enqueue 返回的就是 0，就说明这一行已经全部输出，此时，将这个 0 追加到队列的末尾。

function printYanghui1(n) {
  var queue = new Queue();
  queue.enqueue(1);
  // 第一层for循环控制打印几层

  for (var i = 1; i <= n; i++) {
    var line = "";
    var pre = 0;
    // 第二层for循环控制打印第i层
    for (var j = 0; j < i; j++) {
      var item = queue.dequeue();
      line += item + " ";
      // 计算下一行的内容
      var value = item + pre;
      pre = item;
      queue.enqueue(value);
    }
    // 每一层最后一个数字是1，上面的for循环没有计算最后一个数
    queue.enqueue(1);
    console.log(line);
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

function printYanghui2(n) {
  var queue = new Queue();
  queue.enqueue(1);
  queue.enqueue(0);
  for (var i = 1; i <= n; i++) {
    var line = "";
    var pre = 0;
    while (true) {
      var item = queue.dequeue();
      // 用一个0把每一行的数据分割开,遇到0不输出,
      if (item == 0) {
        queue.enqueue(1);
        queue.enqueue(0);
        break;
      } else {
        // 计算下一行的内容
        line += item + "  ";
        var value = item + pre;
        pre = item;
        queue.enqueue(value);
      }
    }
    console.log(line);
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

← 栈链表 →