【数据结构与算法】队列(JavaScript版详解)

By 大Van家 on 2021-08-12
阅读时间 25 分钟
文章共 5.8k
阅读量

要点:基本队列、优先队列、双端队列、循环队列、对应练习

先知:队列(Queue)是一种运算受限的线性表,特点:先进先出。(FIFO:First In First Out)

一、认识队列

1.1 定义

队列(Queue)是一种运算受限的线性表,特点:先进先出。(FIFO:First In First Out)

受限之处:

  • 只允许在表的前端(front)进行删除操作。
  • 只允许在表的后端(rear)进行插入操作。

生活中类似队列结构的场景:

  • 排队,比如在电影院,商场,甚至是厕所排队。
  • 优先排队的人,优先处理。 (买票、结账、WC)。

image

1.2 队列图解

image

1.3 队列在程序中的应用

打印队列:计算机打印多个文件的时候,需要排队打印。

线程队列:当开启多线程时,当新开启的线程所需的资源不足时就先放入线程队列,等待 CPU 处理。

我们在做性能优化的时候,很多时候会提到的一点就是“HTTP 1.1 的队头阻塞问题”,具体来说就是 HTTP2 解决了 HTTP1.1 中的队头阻塞问题,但是为什么 HTTP1.1 有队头阻塞问题,HTTP2 究竟怎么解决的这个问题,很多人都不清楚。

其实队头阻塞是一个专有名词,不仅仅在 HTTP 有,交换器等其他地方也都涉及到了这个问题。实际上引起这个问题的根本原因是使用了队列这种数据结构。

协议规定, 对于同一个 tcp 连接,所有的 http1.0 请求放入队列中,只有前一个请求的响应收到了,才能发送下一个请求,这个时候就发生了阻塞,并且这个阻塞主要发生在客户端。

这就好像我们在等红绿灯,即使旁边绿灯亮了,你的这个车道是红灯,你还是不能走,还是要等着。

HTTP/1.0 和 HTTP/1.1

HTTP/1.0 中每一次请求都需要建立一个 TCP 连接,请求结束后立即断开连接。

HTTP/1.1 中,每一个连接都默认是长连接 (persistent connection)。对于同一个 tcp 连接,允许一次发送多个 http1.1 请求,也就是说,不必等前一个响应收到,就可以发送下一个请求。这样就解决了 http1.0 的客户端的队头阻塞,而这也就是HTTP/1.1管道 (Pipeline)的概念了。

但是,http1.1 规定,服务器端的响应的发送要根据请求被接收的顺序排队,也就是说,先接收到的请求的响应也要先发送。这样造成的问题是,如果最先收到的请求的处理时间长的话,响应生成也慢,就会阻塞已经生成了的响应的发送,这也会造成队头阻塞。可见,http1.1 的队首阻塞是发生在服务器端。

HTTP/2 和 HTTP/1.1

为了解决HTTP/1.1中的服务端队首阻塞,HTTP/2采用了二进制分帧多路复用 等方法。

帧是HTTP/2数据通信的最小单位。在 HTTP/1.1 中数据包是文本格式,而 HTTP/2 的数据包是二进制格式的,也就是二进制帧。

采用帧的传输方式可以将请求和响应的数据分割得更小,且二进制协议可以被高效解析。HTTP/2中,同域名下所有通信都在单个连接上完成,该连接可以承载任意数量的双向数据流。每个数据流都以消息的形式发送,而消息又由一个或多个帧组成。多个帧之间可以乱序发送,根据帧首部的流标识可以重新组装。

多路复用用以替代原来的序列和拥塞机制。在HTTP/1.1中,并发多个请求需要多个 TCP 链接,且单个域名有 6-8 个 TCP 链接请求限制(这个限制是浏览器限制的,不同的浏览器也不一定一样)。在HTTP/2中,同一域名下的所有通信在单个链接完成,仅占用一个 TCP 链接,且在这一个链接上可以并行请求和响应,互不干扰。

此网站 可以直观感受 HTTP/1.1HTTP/2 的性能对比。

二、队列的实现

队列的实现和栈一样,有两种方案:

  • 基于数组实现。
  • 基于链表实现。

2.1 队列常见的操作

enqueue(element) 向队列尾部添加一个(或多个)新的项。

dequeue() 移除队列的第一(即排在队列最前面的)项,并返回被移除的元素。

front() 返回队列中的第一个元素——最先被添加,也将是最先被移除的元素。队列不做任何变动(不移除元素,只返回元素信息与 Map 类的 peek 方法非常类似)。

isEmpty() 如果队列中不包含任何元素,返回 true,否则返回 false。

size() 返回队列包含的元素个数,与数组的 length 属性类似。

toString() 将队列中的内容,转成字符串形式。

2.2 代码实现

顺序队列

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
class Queue {
constructor() {
this.items = [];
}

// enqueue(item) 入队,将元素加入到队列中
enqueue(item) {
this.items.push(item);
}

// dequeue() 出队,从队列中删除队头元素,返回删除的那个元素
dequeue() {
return this.items.shift();
}

// front() 查看队列的队头元素
front() {
return this.items[0];
}

// isEmpty() 查看队列是否为空
isEmpty() {
return this.items.length === 0;
}

// size() 查看队列中元素的个数
size() {
return this.items.length;
}

// toString() 将队列中的元素以字符串形式返回
toString() {
let result = "";
for (let item of this.items) {
result += item + " ";
}
return result;
}
}

链式队列

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
function LinkedQueue() {
let Node = function (ele) {
this.ele = ele;
this.next = null;
}

let length = 0,
front, //队首指针
rear; //队尾指针
this.push = function (ele) {
let node = new Node(ele),
temp;

if (length == 0) {
front = node;
} else {
temp = rear;
temp.next = node;
}
rear = node;
length++;
return true;
}

this.pop = function () {
let temp = front;
front = front.next
length--;
temp.next = null
return temp;
}

this.size = function () {
return length;
}
this.getFront = function () {
return front;
// 有没有什么思路只获取队列的头结点,而不是获取整个队列
}
this.getRear = function () {
return rear;
}
this.toString = function () {
let string = '',
temp = front;
while (temp) {
string += temp.ele + ' ';
temp = temp.next;
}
return string;
}
this.clear = function () {
front = null;
rear = null;
length = 0;
return true;
}
}

let myQueue = new LinkedQueue();

myQueue.push(1)
myQueue.push(2)
myQueue.push(3)
myQueue.push(4)
console.log(myQueue.toString()) // 1 2 3 4
console.log(myQueue.pop()) // Node { ele: 1, next: null }
console.log(myQueue.toString()) // 2 3 4

2.3 测试代码

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
const queue = new Queue();

// enqueue() 测试
queue.enqueue("a");
queue.enqueue("b");
queue.enqueue("c");
queue.enqueue("d");
console.log(queue.items); //--> ["a", "b", "c", "d"]

// dequeue() 测试
queue.dequeue();
queue.dequeue();
console.log(queue.items); //--> ["c", "d"]

// front() 测试
console.log(queue.front()); //--> c

// isEmpty() 测试
console.log(queue.isEmpty()); //--> false

// size() 测试
console.log(queue.size()); //--> 2

// toString() 测试
console.log(queue.toString()); //--> c d

三、优先队列

3.1 定义

生活中类似优先队列的场景:

  • 优先排队的人,优先处理。 (买票、结账、WC)。
  • 排队中,有紧急情况(特殊情况)的人可优先处理。

所谓优先队列,顾名思义,就是说插入到队列中的元素可以根据优先级设置先后顺序。优先级越高位置越靠前,优先级越低位置越靠后。假设优先级用数字来表示,如果数字越小表示的优先级越高,形成的队列就称之为最小优先队列,反之则称之为最大优先队列。

3.2 代码实现

优先级队列主要考虑的问题:

  • 每个元素不再只是一个数据,还包含优先级。
  • 在添加元素过程中,根据优先级放入到正确位置。
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// 优先队列内部的元素类
class QueueElement {
constructor(element, priority) {
this.element = element;
this.priority = priority;
}
}

// 优先队列类(继承 Queue 类)
export class PriorityQueue extends Queue {
constructor() {
super();
}

// enqueue(element, priority) 入队,将元素按优先级加入到队列中
// 重写 enqueue()
enqueue(element, priority) {
// 根据传入的元素,创建 QueueElement 对象
const queueElement = new QueueElement(element, priority);

// 判断队列是否为空
if (this.isEmpty()) {
// 如果为空,不用判断优先级,直接添加
this.items.push(queueElement);
} else {
// 定义一个变量记录是否成功添加了新元素
let added = false;

for (let i = 0; i < this.items.length; i++) {
// 让新插入的元素进行优先级比较,priority 值越小,优先级越大
if (queueElement.priority < this.items[i].priority) {
// 在指定的位置插入元素
this.items.splice(i, 0, queueElement);
added = true;
break;
}
}

// 如果遍历完所有元素,优先级都大于新插入的元素,就将新插入的元素插入到最后
if (!added) {
this.items.push(queueElement);
}
}
}

// dequeue() 出队,从队列中删除前端元素,返回删除的元素
// 继承 Queue 类的 dequeue()
dequeue() {
return super.dequeue();
}

// front() 查看队列的前端元素
// 继承 Queue 类的 front()
front() {
return super.front();
}

// isEmpty() 查看队列是否为空
// 继承 Queue 类的 isEmpty()
isEmpty() {
return super.isEmpty();
}

// size() 查看队列中元素的个数
// 继承 Queue 类的 size()
size() {
return super.size();
}

// toString() 将队列中元素以字符串形式返回
// 重写 toString()
toString() {
let result = "";
for (let item of this.items) {
result += item.element + "-" + item.priority + " ";
}
return result;
}
}

可以看到,唯一有区别的只有enqueue方法。我们规定所有添加到优先队列的元素都必须满足{element, priority}这种JSON格式,以保证队列中的每一个元素都有一个priority属性来表示优先级。如果要添加的元素的优先级和队列中已有元素的优先级相同,仍然遵循队列的先进先出原则。如果队列中所有元素的优先级比要添加的元素的优先级都高,则将元素添加到队列的末尾。

3.3 测试代码

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
const priorityQueue = new PriorityQueue();

// 入队 enqueue() 测试
priorityQueue.enqueue("A", 10);
priorityQueue.enqueue("B", 15);
priorityQueue.enqueue("C", 11);
priorityQueue.enqueue("D", 20);
priorityQueue.enqueue("E", 18);
console.log(priorityQueue.items);
//--> output:
// QueueElement {element: "A", priority: 10}
// QueueElement {element: "C", priority: 11}
// QueueElement {element: "B", priority: 15}
// QueueElement {element: "E", priority: 18}
// QueueElement {element: "D", priority: 20}

// 出队 dequeue() 测试
priorityQueue.dequeue();
priorityQueue.dequeue();
console.log(priorityQueue.items);
//--> output:
// QueueElement {element: "B", priority: 15}
// QueueElement {element: "E", priority: 18}
// QueueElement {element: "D", priority: 20}

// isEmpty() 测试
console.log(priorityQueue.isEmpty()); //--> false

// size() 测试
console.log(priorityQueue.size()); //--> 3

// toString() 测试
console.log(priorityQueue.toString()); //--> B-15 E-18 D-20

四、双端队列

4.1 定义

允许从前端(front)和后端(rear)添加元素, 遵循的原则先进先出或后进先出.

双端队列可以理解为就是栈(后进先出)和队列(先进先出)的一种结合体. 既然是结合那么相应的操作也支持队列,栈的操作。

4.2 代码实现

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
  constructor() {
this.items = {}
this.count = 0
this.lowestCount = 0
}

addFront(ele) {
if (this.isEmpty()) {
this.items[this.count] = ele
} else if (this.lowestCount > 0) {
this.lowestCount -= 1
this.items[this.lowestCount] = ele
} else {
for (let i = this.count; i > 0; i--) {
this.items[i] = this.items[i - 1]
}
this.items[0] = ele
}
this.count++
return ele
}

removeFront() {
if (this.isEmpty()) {
return
}
const delEle = this.items[this.lowestCount]
delete this.items[this.lowestCount]
this.lowestCount++
return delEle
}

addBack(ele) {
this.items[this.count] = ele
this.count++
}

removeBack() {
if (this.isEmpty()) {
return
}

const delEle = this.items[this.count - 1]
delete this.items[this.count - 1]
this.count--
return delEle
}

peekFront() {
if (this.isEmpty()) {
return
}
return this.items[this.lowestCount]
}

peekBack() {
if (this.isEmpty()) {
return
}
return this.items[this.count - 1]
}

size() {
return this.count - this.lowestCount
}

isEmpty() {
return this.size() === 0
}

clear() {
this.items = {}
this.count = 0
this.lowestCount = 0
}

toString() {
if (this.isEmpty()) {
return ''
}
let objString = `${this.items[this.lowestCount]}`
for (let i = this.lowestCount + 1; i < this.count; i++){
objString = `${objString}, ${this.items[i]}`
}
return objString
}

}

五、循环队列

5.1 定义

设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。 你的实现应该支持如下操作:

  • MyCircularQueue(k): 构造器,设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空,返回 -1 。
  • Rear: 获取队尾元素。如果队列为空,返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

想要实现上面的功能,其实主要就是判断循环队列是否为空isEmpty,是否已满isFull,这里我们使用两个指针来表示队首(head)和队尾的指针(tail)。假设初始化的时候两个指针的值都是-1。那么显然是否为空的判断条件就是两个指针都是-1的时候。

5.2 代码实现

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/**
* Initialize your data structure here. Set the size of the queue to be k.
* @param {number} k
*/
var MyCircularQueue = function(k) {
this.size = k
this.head = -1
this.tail = -1
this.data = []
};

/**
* Insert an element into the circular queue. Return true if the operation is successful.
* @param {number} value
* @return {boolean}
*/
MyCircularQueue.prototype.enQueue = function(value) {
if (this.isFull()) {
return false
}
if (this.isEmpty()) {
this.head = 0
}
this.tail = (this.tail + 1)%this.size
this.data[this.tail] = value
return true
};

/**
* Delete an element from the circular queue. Return true if the operation is successful.
* @return {boolean}
*/
MyCircularQueue.prototype.deQueue = function() {
if (!this.isEmpty()) {
if (this.tail === this.head) {
this.tail = -1
this.head = -1
} else {
this.head = (this.head + 1)%this.size
}
return true
}
return false
};

/**
* Get the front item from the queue.
* @return {number}
*/
MyCircularQueue.prototype.Front = function() {
return this.head === -1? -1 : this.data[this.head]
};

/**
* Get the last item from the queue.
* @return {number}
*/
MyCircularQueue.prototype.Rear = function() {
return this.tail === -1 ? -1 : this.data[this.tail]
};

/**
* Checks whether the circular queue is empty or not.
* @return {boolean}
*/
MyCircularQueue.prototype.isEmpty = function() {
return this.tail === -1 && this.head === -1
};

/**
* Checks whether the circular queue is full or not.
* 当队列满的时候,则为指针的下一个地址应该等于头指针的位置:
* @return {boolean}
*/
MyCircularQueue.prototype.isFull = function() {
return (this.tail + 1)%this.size === this.head
};

MyCircularQueue.createNew = function(k) {
return new MyCircularQueue(k)
};

/**
* Your MyCircularQueue object will be instantiated and called as such:
* var obj = Object.create(MyCircularQueue).createNew(k)
* var param_1 = obj.enQueue(value)
* var param_2 = obj.deQueue()
* var param_3 = obj.Front()
* var param_4 = obj.Rear()
* var param_5 = obj.isEmpty()
* var param_6 = obj.isFull()
*/

六、队列的应用

6.1 击鼓传花-循环队列

使用队列实现小游戏:击鼓传花。

分析:现实例子就是击鼓传花(Hot Potato),在游戏中,孩子们围着圆圈,把花尽快地传递给旁边的人。某一时刻传花停止,这个时候花在谁手里,谁就退出圆圈结束游戏。重复这个过程,直到只剩一个孩子(胜利)。

传入一组数据集合和设定的数字 number,循环遍历数组内元素,遍历到的元素为指定数字 number 时将该元素删除,直至数组剩下一个元素。

代码实现

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
// 利用队列结构的特点实现击鼓传花游戏求解方法的封装
function passGame(nameList, number) {
// 1、new 一个 Queue 对象
const queue = new Queue();

// 2、将 nameList 里面的每一个元素入队
for (const name of nameList) {
queue.enqueue(name);
}

// 3、开始数数
// 队列中只剩下 1 个元素时就停止数数
while (queue.size() > 1) {
// 不是 number 时,重新加入到队尾
// 是 number 时,将其删除

for (let i = 0; i < number - 1; i++) {
// number 数字之前的人重新放入到队尾(即把队头删除的元素,重新加入到队列中)
queue.enqueue(queue.dequeue());
}

// number 对应这个人,直接从队列中删除
// 由于队列没有像数组一样的下标值不能直接取到某一元素,
// 所以采用,把 number 前面的 number - 1 个元素先删除后添加到队列末尾,
// 这样第 number 个元素就排到了队列的最前面,可以直接使用 dequeue 方法进行删除
queue.dequeue();
}

// 4、获取最后剩下的那个人
const endName = queue.front();

// 5、返回这个人在原数组中对应的索引
return nameList.indexOf(endName);
}

测试代码

1
2
3
4
// passGame() 测试
const names = ["lily", "lucy", "tom", "tony", "jack"];
const targetIndex = passGame(names, 4);
console.log("击鼓传花", names[targetIndex]); //--> lily

6.2 基数排序

使用队列实现基数排序

队列不仅用于执行现实生活中关于队列相关的操作,还可以用于对数据进行排序。计算机刚刚出现的时候,程序是通过穿孔输入主机的,每一张卡包含一条程序语句。这些穿孔卡装在一个盒子里面,经过一个机械装置进行排序。我们可以用一组队列来模拟这个过程。这种排序技术叫做基数排序

对于0~99的数字,基数排序将数据集扫描两次。第一次按照个位上的数字进行排序,第二次按照十位上的数字进行排序。每个数组根据对应位上的数字被分配在不同的盒子里。

举例如下:假如有数字 91,46,85,15,92,35,31,22

经过基数排序第一次扫描之后按照个位数的大小排序,数字被分配大如下的盒子中:

第0个盒子:
第1个盒子:91,31
第2个盒子:92,22
第3个盒子:
第4个盒子:
第5个盒子:85,15,35
第6个盒子:46
第7个盒子:
第8个盒子:
第9个盒子:

根据盒子的顺序,对数字经行第一次排序的结果如下:

91,31,92,22,85,15,35,46

然后根据十位上的数值再将上次排序结果分配到不同的盒子里

第0个盒子:
第1个盒子:15
第2个盒子:22
第3个盒子:31,35
第4个盒子:46
第5个盒子:
第6个盒子:
第7个盒子:
第8个盒子:85
第9个盒子:92,92

最后将盒子里的数字取出,组成一个新的列表,该列表即为排好顺序的数字:

15,22,31,35,46,85,91,92

使用队列代表盒子,可以实现这个算法,我们需要9个队列,每个对应一个数字。将所有队列保存在一个数组中,使用取余和出发操作决定各位和十位。算法的剩余部分将数字加入对应的队列,根据个位数值重新排序,然后再根据十位数值经行排序,结果即为排好顺序的数字。

代码实现

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/*--------------Queue类的定义和测试代码----------------*/
function Queue(){
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
}

//入队,就是在数组的末尾添加一个元素
function enqueue(element){
this.dataStore.push(element);
}
//出队,就是删除数组的第一个元素
function dequeue(){
return this.dataStore.shift();
}
//取出数组的第一个元素
function front(){
return this.dataStore[0];
}
//取出数组的最后一个元素
function back(){
return this.dataStore[this.dataStore.length-1];
}

function toString(){
var retStr = "";
for (var i=0; i<this.dataStore.length; ++i) {
retStr += this.dataStore[i] + " "
}
return retStr;
}
//判断数组是否为空
function empty(){
if(this.dataStore.length == 0){
return true;
}else{
return false;
}
}
//返回数组中元素的个数
function count(){
return this.dataStore.length;
}

/*----------------基数排序-----------------*/

function distribute(nums,queues,n,digit){
for (var i=0; i<n; ++i) {
if(digit == 1){
//各位数字入队
queues[nums[i]%10].enqueue(nums[i]);
}else{
//十位数字入队
queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
}
}
}

//收集队列中的数字放在数字nums中
function collect(queues,nums){
var i=0;
for (var digit=0; digit<10; ++digit) {
while (!queues[digit].empty()){
nums[i++] = queues[digit].dequeue();
}
}
}

function dispArray(arr){
for (var i=0; i<arr.length; ++i) {
document.write(arr[i] + " ");
}
}

//初始化9个队列
var queues = [];
for (var i = 0; i < 10; i++) {
queues[i] = new Queue();
}
//初始化10个二位整数
var nums = [];
for (var i=0; i<10; ++i) {
nums[i] = Math.floor(Math.random()*100);
}

document.write('排序之前');document.write('<br>');
dispArray(nums);
document.write('<br>');
//按照个位数字入相应的队列
distribute(nums, queues, 10, 1);
//收集队列中的数字放在数组nums中
collect(queues, nums);
//按照十位数字如相应的队列
distribute(nums, queues, 10, 10);
//手机队列中的数字放在nums中
collect(queues, nums);
document.write("排序之后");document.write('<br>');
dispArray(nums);

6.3 银行排队

实现思路:第一个客户到达的时刻为0,之后每个客户到达的时刻在前一个客户到达时设定随机值,因此在客户到达时需要产生两个随机数,一个是客户办理业务耗时durtime,一个是下一客户到达时间间隔intertime,假设当前时间为occurtime,则下一客户到达时为occurtime+intertime。

刚到达的客户应该插入到当前含元素最少的队列中。

在JavaScript的运用中,通常使用队列来进行任务的排序。而任务队列的任务是按进入队列的顺序延迟执行(解决状态一致性)的,即当前一个任务完成后,后面的任务才被执行,如果当前没有任务,则入队列的任务立即执行

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function taskQueue() {
taskList = [];
var isRun = false;
this.addTask = function (task) {
taskList.push(task);
};
setInterval(function () {
if (taskList.length > 0 && !isRun) {
isRun = true;
taskList.shift();
isRun = false;
}
}, 100);
}
function show(){
alert(taskList);
}
taskQueue();
addTask(1);
addTask(2);
addTask(3);
setTimeout('show()',99);//1,2,3
setTimeout('show()',101);//2,3
setTimeout('show()',400);//null

6.4 判断回文

上一篇使用栈判断回文)中也有涉及回文的实现, 下面我们通过双端队列来实现同样的功能

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
function palindromeChecker(aString) {
if (!aString || typeof aString !== 'string' || !aString.trim().length) {
return false
}
const deque = new Deque()
const lowerString = aString.toLowerCase().split(' ').join('')

// 加入队列

for (let i = 0; i < lowerString.length; i++) {
deque.addBack(lowerString[i])
}

let isEqual = true
let firstChar = ''
let lastChar = ''

while (deque.size() > 1 && isEqual) {
firstChar = deque.removeFront()
lastChar = deque.removeBack()
if (firstChar != lastChar) {
isEqual = false
}
}

return isEqual

}

图解

1

6.5 生成 1 到 n 的二进制数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function generatePrintBinary(n) {
var q = new Queue()
q.enqueue('1')
while (n-- > 0) {
var s1 = q.peek()
q.dequeue()
console.log(s1)
var s2 = s1
q.enqueue(s1 + '0')
q.enqueue(s2 + '1')
}
}

generatePrintBinary(5) // => 1 10 11 100 101

回顾

数组、栈和队列图解


Tips: Please indicate the source and original author when reprinting or quoting this article.