JS 数据结构：队列_js 队列

队列

定义： 队列(Queue) 是一种只在表的一端进行插入，而在另一端进行删除的数据结构。

• 队头(front) 允许删除的一端，永远指向第一个元素前一个位置。
• 队尾(rear) 允许插入的一端，永远是指向队列最后一个元素
• 先进先出(First In First Out)的线性表，简称FIFO表
• 空队列 当队列中没有元素

上溢和下溢

当队列满时再入队会产生空间溢出，简称“上溢”;当队列空时再出队也会产生溢出，简称“下溢”。上溢是一种出错状态，应该避免；下溢则是正常现象。
假上溢：

• 因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。
  
  队尾指针为5，队头指针为1，此时尾指针已经指向了顺序队列最后一个元素，但可以看到0，1两个
  并没有被使用，此时就为假上溢。

顺序队列

定义： 队列的顺序存储结构简称顺序队列。

完整代码

基于 JS 数组实现，由于 JS 数组能够自动扩容，所以没有上溢问题。并且原生实现了队列方法。

class ArrayQueue {
  constructor() {
    this.queue = [];
  }
  // 入队
  enqueue(value) {
    return this.queue.push(value);
  }
  // 出队
  dequeue() {
    return this.queue.shift();
  }
  // 取队头元素
  peek() {
    return this.queue[0];
  }
  // 判断队列是否为空
  isEmpty() {
    return this.queue.length === 0;
  }
  // 取队列有多少个元素
  size() {
    return this.queue.length;
  }
  // 清空队列
  clear() {
    this.queue = [];
  }
}
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

基于 JS 对象实现。不存在上溢和假上溢问题。

class ObjectQueue {
  constructor() {
    this.queue = {};
    this.end = -1;
    this.front = -1;
  }
   // 入队
  enqueue(value) {
    if (this.front === -1) {
      this.front++;
    }
    this.queue[++this.end] = value;
  }
  // 出队
  dequeue() {
    if (!this.isEmpty()) {
      const res = this.queue[this.front];
      delete this.queue[this.front++];
      return res;
    }
    return null;
  }
  // 取队头元素
  peek() {
    if (!this.isEmpty()) {
      return this.queue[this.front];
    }
    return null;
  }
  // 判断队列是否为空
  isEmpty() {
    return this.front > this.end;
  }
  // 取队列有多少个元素
  size() {
    return this.end - this.front + 1;
  }
  // 清空队列
  clear() {
    this.queue = {};
    this.front = -1;
    this.end = -1;
  }
}
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
37
38
39
40
41
42
43
44

循环队列

为了解决假上溢问题，引入循环队列，即把向量空间想象为一个首尾相接的圆环，在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（MAXNUM-1）时，其加1操作的结果是指向向量的下界0。

但是引进的循环队列又出现了新的问题，看图：

判空和判满两种方法

即队空和队满的时都满足q->front==q->rear，我们无法利用这个条件判断队空还是队满！！！该怎么解决这个问题呢？有两种方法：

1. 少用一个数据元素空间，以队尾指示器加 l等于队头指示器判断队满，即队满条件为:
   (q-> rear+l)％MAXNUM==q->front
2. 使用一个计数器记录队列中元素的总数（实际上是队列长度）。

第一种方法实现

class LoopArrayQueue{
  constructor() {
    this.MAXNUM = 5;
    this.queue = new Array(this.MAXNUM);
    this.front = 0;
    this.rear = 0;
  }
  // 入队
  enqueue(value) {
    if ((this.rear + 1) % this.MAXNUM === this.front) {
      console.log('队列已满，入队失败');
      return;
    }
    this.rear++;
    this.queue[this.rear % this.MAXNUM] = value;
  }
  // 出队
  dequeue() {
  	if(!this.isEmpty()) {
    	this.front++;
    	const res = this.queue[this.front % this.MAXNUM];
    	this.queue[this.front % this.MAXNUM] = undefined;
    	return res;
    }
    return undefined;
  }
  // 取队头元素
  peek() {
    return this.queue[(this.front + 1) % this.MAXNUM];
  }
  // 判断队列是否为空
  isEmpty() {
    return this.front === this.rear;
  }
  // 取队列有多少个元素
  size() {
    return this.rear - this.front;
  }
  // 清空队列
  clear() {
    this.queue = new Array(this.MAXNUM);
    this.front = 0;
    this.rear = 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

第二种方法实现

class LoopArrayQueue{
  constructor() {
    this.MAXNUM = 5;
    this.queue = new Array(this.MAXNUM);
    this.front = -1;
    this.rear = -1;
    this.count = 0;
  }
  // 入队
  enqueue(value) {
    if (this.count === this.MAXNUM) {
      console.log('队列已满，入队失败');
      return;
    }
    this.count++;
    this.rear++;
    this.queue[this.rear % this.MAXNUM] = value;
  }
  // 出队
  dequeue() {
    if (this.count > 0){
      this.front++;
      this.count--;
      const res = this.queue[this.front % this.MAXNUM];
      this.queue[this.front % this.MAXNUM] = undefined;
      return res;
    }
    return undefined;
  }
  // 取队头元素
  peek() {
    return this.queue[(this.front + 1) % this.MAXNUM];
  }
  // 判断队列是否为空
  isEmpty() {
    return this.count === 0;
  }
  // 取队列有多少个元素
  size() {
    return this.count;
  }
  // 清空队列
  clear() {
    this.count = 0;
    this.front = -1;
    this.rear = -1;
    this.queue = new Array(this.MAXNUM);
  }
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49

链队列

定义： 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。 显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。

注意：虽然 JS 并没有指针的概念，但是对于对象这样的类型，对象的名字本质上就相当于指针。

虽然 JS 中数组实现了在队列的方法，但是它本质上还是数组操作，所以若从数组头部删除一个元素，那么在 JS 引擎内部还是需要移动后边的数组元素，很耗费性能。但是链式存储结构删除和添加元素复杂度为 O1。

节点存储结构：

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
1
2
3
4
5
6

判断队空
注意：有 JS 本身并无指针概念，所以再实现“链队”时必须要定义一个变量 count 记录队列中元素个数，由 count == 0 作为判空条件。

而其他语言（例如 c 语言）链队队空条件是pointer->front->next == NULL && pointer->rear->next == NULL而不是pointer->front == pointer->rear这是因为当队空的时候pointer->front和pointer->rear的值不一样。

原因： 如上图所示，当创建空链队时，队列头指针、尾指针都指向上图中黑色节点（这个黑色节点相当于顺序队列的-1，是一个初始节点），当链队列添加元素后尾指针会改变它指向的节点，此时pointer->rear的值是它指向的尾结点的地址。而当队列删除元素时，改变的是黑色节点的 next 指针（这样做是为了使头指针满足它的特点，具体看上边队列特点），这样pointer->front的值永远是黑色节点的地址。所以pointer->front和pointer->rear的值不一样，不能作为判断队空的条件。

出队列：

当使用其它语言（例如 c 语言）时此功能需要注意的就是当队列只剩一个元素时，即pointer->front->next == pointer->rear，而你要删除此元素，就需要先改变尾指针指向的节点，再删除，释放最后一个元素节点的内存。因为如果你不改变的话，则尾指针是指向最后一个元素节点的，而你删除释放最后一个元素节点的内存后，此时pointer->rear->next是一个野指针（野指针的危害就不用我说了吧！！！）。

完整代码

class LinkQueue {
  constructor() {
    const node = new Node();
    this.count = 0;
    this.head = node;
    this.rear = node;
  }
  // 入队
  enqueue(value) {
    const node = new Node(value);
    this.rear.next = node;
    this.rear = node;
    this.count++;
  }
  // 出队
  dequeue() {
    if (!this.isEmpty()) {
      const res = this.head.next.value;
      this.head.next = this.head.next.next;
      this.count--;
      if (this.isEmpty()) {
        this.rear = this.head;
      }
      return res;
    }
    return null;
  }
  // 取队头元素
  peek() {
    if (!this.isEmpty()) {
      return this.head.value;
    }
    return null;
  }
  // 判断是否为空
  isEmpty() {
    return this.count === 0;
  }
  // 返回队列元素个数
  size() {
    return this.count;
  }
  // 清空队列
  clear() {
    const node = new Node();
    this.count = 0;
    this.head = node;
    this.rear = node;
  }
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50

双端队列

双端队列（deque）是一种允许我们同时从队列前端和后端添加和移除元素的特殊队列。即可以在队头入队、出队，也可在队尾入队、出队。

class ArrayDequeue {
  constructor() {
    this.queue = [];
  }
  // 从队头入队
  adFront(value) {
    this.queue.unshift(value);
  }
  // 从队尾入队
  addBack(value) {
    this.queue.push(value);
  }
  // 从队头出队
  removeFront() {
    return this.queue.shif();
  }
  // 从队尾出队
  removeBack() {
    return this.queue.pop();
  }
  // 返回队头元素
  removeFront() {
    return this.queue[0];
  }
  // 返回队尾元素
  removeBack() {
    return this.queue[this.queue.length - 1];
  }
  // 判断队列是否为空
  isEmpty() {
    return this.queue.length === 0;
  }
  // 取队列有多少个元素
  size() {
    return this.queue.length;
  }
  // 清空队列
  clear() {
    this.queue = [];
  }
}
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
37
38
39
40
41

相信经过栈和队列的学习，你已经感受到了 JS 数组的强大，其本身还具有很多方法，能够让我们更加方便的操控数组元素，可以看看这篇博客哦！总结 JS 数组及其方法

队列讲到这里就结束了。概念很好理解，重要的还是实现时候的细节需要仔细把控。我是孤城浪人，一名正在前端路上摸爬滚打的菜鸟，欢迎你的关注。