• 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 数组及其方法

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

  • 相关阅读:
    《21天精通TypeScript-4》-类型推断与语义检查
    收录批量查询 网页收录批量查询数据并导出
    计算机毕业设计springboot+vue基本微信小程序的透析耗材管理系统
    2.12 IC类元器件的封装应该怎么创建？
    OPT-001
    大数据-玩转数据-Centos7 升级JDK11
    台湾通行证识别易语言代码
    第十三届蓝桥杯省赛 C++ C 组 E 题、Python B组 D题、PythonC组 D 题—— 数位排序（AC）
    Transformer与强化学习结合提升物联网智能决策
    Redis中缓存穿透、击穿、雪崩以及解决方案
  • 原文地址：https://blog.csdn.net/weixin_46015333/article/details/127995994