Queue [队列]
# 什么是队列?
队列被定义为一个两端开放的线性数据结构,操作以先进先出(FIFO)顺序进行。
我们把队列定义为一个列表,在这个列表中,所有对列表的添加都在一端进行,所有对列表的删除都在另一端进行。首先被推入顺序的元素,首先对其进行操作。
# 队列的 FIFO 原则
- 队列就像等待购票的队伍,排在第一位的人就是第一个被服务的人。(即先到先得)。
- 队列中准备服务的条目的位置,即第一个将从队列中移除的条目,被称为队列的前部(front)(有时是队列的头部(head)),同样,队列中最后一个条目的位置,即最近增加的一个条目,被称为队列的后部(rear)(或尾部(tail))。
# 队列的特点
- 队列可以处理多个数据。
- 队列可以访问两端。
- 队列是快速和灵活的。
# 队列的表示方法
像堆栈一样,队列也可以用数组来表示。在这种表示法中,队列是用数组实现的。在这种情况下使用的变量有:
- Queue:存储队列元素的数组名称。
- Front:在代表队列的数组中存储第一个元素的索引。
- Rear:在代表队列的数组中存储最后一个元素的索引。
数组实现的优点:
- 易于实现。
- 可以轻松有效地管理大量的数据。
- 由于它遵循先入先出的规则,所以可以轻松地进行插入和删除等操作。
数组实现的缺点:
- 静态数据结构,固定大小。
- 如果队列有大量的 enqueue 和 dequeue 操作,在某些时候(在前后索引线性递增的情况下)我们可能无法在队列中插入元素,即使队列是空的(这个问题可以通过使用循环队列来避免)。
链表表示法:一个队列也可以用链接列表、指针和结构来表示。
# 队列的类型
有不同类型的队列。
- 简单队列。简单队列也被称为线性队列,是队列的最基本版本。在这里,插入一个元素,即 Enqueue 操作发生在后端,删除一个元素,即 Dequeue 操作发生在前端。
- 输入受限队列(Input Restricted Queue):这是一个简单的队列。在这种类型的队列中,输入只能从一端进行,但删除可以从任何一端进行。
- 输出受限队列(Output Restricted Queue):这也是一个简单的队列。在这种类型的队列中,输入可以从两端进行,但删除只能从一端进行。
- 环形队列(Circular Queue):这是一种特殊类型的队列,最后一个位置被连接到第一个位置。这里的操作也是按先进先出的顺序进行的。在环形队列中,队列中的元素就像一个圆形的环。除了最后一个元素与第一个元素相连外,环形队列的工作与线性队列相似。它的优点是可以更好地利用内存。这是因为如果有一个空的空间,即如果在队列的某个位置没有元素,那么可以很容易地在该位置添加一个元素。
- 双端队列 (Double-Ended Queue,Dequeue):在双端队列中,插入和删除操作,都可以从两端进行。因为这个属性,它可能不服从先进先出的原则。
- 优先级队列(Priority Queue):优先级队列是一个特殊的队列,其中元素的访问是基于分配给它们的优先级。它的特点是,它根据一些优先级安排队列中的元素。优先级可以是具有最高值的元素具有优先权,所以它创建了一个数值递减的队列。优先级也可以是具有最低值的元素获得最高的优先级,所以它反过来创建了一个数值递增的队列。
# 队列的基本操作
front ():该操作返回前端的元素,而不删除它。
rear ():该操作返回后端的元素,但不删除它。
isEmpty ():该操作返回一个布尔值,表明队列是否为空。
isFull ():该操作返回一个布尔值,表明队列是否已满。
size ():该操作返回队列的大小,即它包含的元素总数。
Enqueue ():将一个元素添加(或存储)到队列的末端。应采取以下步骤将数据 enqueue(插入)到一个队列中:
- 检查队列是否已满。
- 如果队列已满,返回溢出(overflow)错误并退出。
- 如果队列未满,递增后方指针以指向下一个空位。
- 将数据元素添加到队列中的位置,即 rear 所指向的位置。
- 返回成功。
Dequeue ():移除(或访问)队列中的第一个元素。执行 Dequeue 操作需要采取以下步骤:
- 检查队列是否为空。
- 如果队列是空的,返回下溢(underflow)错误并退出。
- 如果队列不是空的,访问 front 指向的数据。
- 递增 front 指针,使其指向下一个可用的数据元素。
- 返回成功。
# 队列的应用
队列的应用很普遍。在计算机系统中,可能有等待打印机、访问磁盘存储的任务队列,甚至在一个分时系统中,也可能有使用 CPU 的任务队列。在一个程序中,可能有多个请求被保留在队列中,或者一个任务可能创建其他任务,这些任务必须通过保留在队列中来依次完成。当事情不必立即处理,但必须按照先入先出的顺序进行处理时,就会用到队列,如广度优先搜索。队列的这一特性使它在以下情况下也很有用:
- 它有一个单一的资源和多个消费者。
- 它在慢速和快速设备之间进行同步。
- 在网络中,队列用于诸如路由器 / 交换机和邮件队列等设备中。
- 变种:dequeue、优先队列和双端优先队列等。
以及更多的应用场景:
- 队列被广泛用作单一共享资源的等待列表,如打印机、磁盘、CPU。
- 队列用于数据的异步传输(数据在两个进程之间不以相同的速度传输),例如管道、文件 IO、套接字。
- 在大多数应用程序中,队列被用作缓冲器,如 MP3 媒体播放器、CD 播放器等。
- 队列用于维护媒体播放器中的播放列表,以便从播放列表中添加和删除歌曲。
- 队列在操作系统中用于处理中断。
# 复杂度分析(数组实现)
时间复杂度:
操作 | 复杂度 |
---|---|
Enqueue (插入) | O(1) |
Dequeue (删除) | O(1) |
Front (获取 front) | O(1) |
Rear (获取 Rear) | O(1) |
辅助空间:O (N),其中 N 是用于存储元素的数组的大小。
Data Structure | Time Complexity | Space Compleity | |||||||
---|---|---|---|---|---|---|---|---|---|
Average | Worst | Worst | |||||||
Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | ||
Queue | θ(n) | θ(n) | θ(1) | θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
# 实现
# JavaScript
class Queue {
/**
* Creates a queue.
* @param {array} [elements]
*/
constructor(elements) {
this._elements = Array.isArray(elements) ? elements : [];
this._offset = 0;
}
/**
* Adds an element at the back of the queue.
* @public
* @param {any} element
*/
enqueue(element) {
this._elements.push(element);
return this;
}
/**
* Dequeues the front element in the queue.
* @public
* @returns {any}
*/
dequeue() {
if (this.size() === 0) return null;
const first = this.front();
this._offset += 1;
if (this._offset * 2 < this._elements.length) return first;
// only remove dequeued elements when reaching half size
// to decrease latency of shifting elements.
this._elements = this._elements.slice(this._offset);
this._offset = 0;
return first;
}
/**
* Returns the front element of the queue.
* @public
* @returns {any}
*/
front() {
return this.size() > 0 ? this._elements[this._offset] : null;
}
/**
* Returns the back element of the queue.
* @public
* @returns {any}
*/
back() {
return this.size() > 0 ? this._elements[this._elements.length - 1] : null;
}
/**
* Returns the number of elements in the queue.
* @public
* @returns {number}
*/
size() {
return this._elements.length - this._offset;
}
/**
* Checks if the queue is empty.
* @public
* @returns {boolean}
*/
isEmpty() {
return this.size() === 0;
}
/**
* Returns the remaining elements in the queue as an array.
* @public
* @returns {array}
*/
toArray() {
return this._elements.slice(this._offset);
}
/**
* Clears the queue.
* @public
*/
clear() {
this._elements = [];
this._offset = 0;
}
/**
* Creates a shallow copy of the queue.
* @public
* @return {Queue}
*/
clone() {
return new Queue(this._elements.slice(this._offset));
}
/**
* Creates a queue from an existing array.
* @public
* @static
* @param {array} elements
* @return {Queue}
*/
static fromArray(elements) {
return new Queue(elements);
}
}
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
103
104
105
106
107
108
109
110
111
112
113
114
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
103
104
105
106
107
108
109
110
111
112
113
114
使用 push 和 shift:
/* Queue
* A Queue is a data structure that allows you to add an element to the end of
* a list and remove the item at the front. A queue follows a "First In First Out"
* system, where the first item to enter the queue is the first to be removed. This
* implementation uses an array to store the queue.
*/
// Functions: enqueue, dequeue, peek, view, length, empty
class Queue {
// constructor
constructor () {
// This is the array representation of the queue
this.queue = []
}
// methods
// Add a value to the end of the queue
enqueue (item) {
this.queue.push(item)
}
// Removes the value at the front of the queue
dequeue () {
if (this.empty()) {
throw new Error('Queue is Empty')
}
return this.queue.shift() // remove the item at position 0 from the array and return it
}
// Return the length of the queue
length () {
return this.queue.length
}
// Return the item at the front of the queue
peek () {
if (this.empty()) {
throw new Error('Queue is Empty')
}
return this.queue[0]
}
// List all the items in the queue
view (output = value => console.log(value)) {
output(this.queue)
}
// Return Is queue empty ?
empty () {
return this.queue.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
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
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
利用两个栈实现队列:
// implementation of Queue using 2 stacks
// contribution made by hamza chabchoub for a university project
class Queue {
constructor () {
this.inputStack = []
this.outputStack = []
}
// Push item into the inputstack
enqueue (item) {
this.inputStack.push(item)
}
dequeue () {
// push all items to outputstack
this.outputStack = []
while (this.inputStack.length > 0) {
this.outputStack.push(this.inputStack.pop())
}
// return the top element of the outputstack if any
if (this.outputStack.length > 0) {
const top = this.outputStack.pop()
// repush all the items to the inputstack
this.inputStack = []
while (this.outputStack.length > 0) {
this.inputStack.push(this.outputStack.pop())
}
return top
}
}
// display elements of the inputstack
listIn (output = value => console.log(value)) {
let i = 0
while (i < this.inputStack.length) {
output(this.inputStack[i])
i++
}
}
// display element of the outputstack
listOut (output = value => console.log(value)) {
let i = 0
while (i < this.outputStack.length) {
output(this.outputStack[i])
i++
}
}
}
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
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
参考:
编辑 (opens new window)
上次更新: 2022/10/11, 17:42:20