JavaScript数据结构与算法 -- 队列篇

名词

先进先出 - FIFO - first in first out
队头: front
队尾: rear
入队: enQueue
出队: deQueue
下溢: 当队列为空时，做出队运算产生的溢出现象。
上溢
- 真上溢: 当队列满时，做进栈运算产生空间溢出的现象。
- 假上溢: 由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。

一、什么是队列

队列是一种特殊的线性表，和栈非常类似，但是使用了与后进先出不同的原则。

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO）线性表。
队列类似与现实中的排队现场

JavaScript数据结构与算法队列篇-2023-11-30-14-52-41

队列类型分为：

!!顺序队列
循环队列

顺序队列

建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针 front，它指向队头元素；另一个是队尾指针 rear，它指向下一个入队元素的存储位置，如图所示

JavaScript数据结构与算法队列篇-2023-11-30-14-52-46

循环队列

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

JavaScript数据结构与算法队列篇-2023-11-30-14-52-51

二、特点

本次主要讲的是 顺序队列 其特点为:

遵从队列先进先出(FIFO)的基本原则
按顺序依次递增front

三、操作

主要操作:

入队
出队

除了这两个操作之外，基本操作还有

判断是否为空
成员个数
清空
查看队首
查看队尾

四、javascript 实现一个队列

这次我们使用key - value来实现队列，想比array好处是可以更加高效的获取操作成员数据

1
2
3


count: number = 0;
lowestCount: number = 0;
items: any = {};

count 表示队列数队尾的下标
lowestCount 表示队首下标
items 用来存储队列的成员信息

实现队列基本操作入队, 出队

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


// 入队
public enQueue(dt: any): void {
  this.items[this.count++] = dt;
}

// 出队
public deQueue(): any {
  if (this.isEmpty()) return undefined;
  let _result = this.items[this.lowestCount];
  delete this.items[this.lowestCount++];
  return _result;
}

入队，即插入到队尾，入队之后将count下标+1
出队，为防止下溢出现，判断非空后，返回队尾成员，并删除该成员，之后将队首下标+1

获取队首与队尾

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


// 返回队首
public front(): any {
  if (this.isEmpty()) return undefined;
  return this.items[this.lowestCount];
}

// 返回队尾
public back(): any {
  return this.items[this.count];
}

与出队入队不同，返回队首与队尾只是用来查看成员，不删除或改变成员

成员个数获取，为空判断，清空成员

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


// 队列是否为空
public isEmpty(): Boolean {
  return this.size() <= 0;
}

// 清空队列
public clear(): void {
  this.items = {};
  this.count = 0;
  this.lowestCount = 0;
}

// 队列长度
public size(): Number {
  return this.count - this.lowestCount;
}

顺序队列的实现特点 front, rear 会一直累加，队列长度即是队首与队尾的差值。
判断是否为空就可以简单的使用 size = 0 判断

至此麻雀虽小五脏俱全，到这里我们就已经实现了一个基本的队列

五、使用

1
2
3


Queue.enQueue(_item); // 入队
Queue.deQueue(_item); // 出队
Queue.size(); // 成员数

现在队列有了，来看看这个简单的东西能干什么吧，大家能想到什么应用场景吗？

六、实例

请求队列
信息弹窗列表
弹夹

名词