Queue
队列概念
- 定义：队列是一种数据结构，元素只能从一个端（后端）插入，从另一个端（前端）移除。
- 特点：先进先出（FIFO, First-In, First-Out）
- 基本操作：
- Enqueue：在队列的后端插入一个元素。
- Dequeue：从队列的前端移除一个元素。
- Front：获取队列前端元素但不移除它。
- Length：返回队列中元素的数量。
- Clear：清空队列。
队列抽象数据类型（ADT）定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| template <typename E>
class Queue {
private:
void operator =(const Queue&) {}
Queue(const Queue&) {};
public:
Queue() {}
virtual ~Queue() {}
virtual void clear() = 0;
virtual void enqueue(const E&) = 0;
virtual E dequeue() = 0;
virtual const E& frontValue() const = 0;
virtual int length() const = 0;
};
|
数组实现的队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| template <typename E>
class AQueue : public Queue<E> {
private:
int maxSize;
int front;
int rear;
E *listArray;
int currSize;
public:
AQueue(int size = defaultSize) { }
~AQueue() { delete[] listArray; }
};
|
循环队列
- 特点：
- 队列的位置可以在数组内移动。
- 前端最初位于数组的第0个位置，元素依次添加到更高的索引位置。
- 移除元素时，前端索引增加。
- Enqueue 和 Dequeue 操作的时间复杂度均为 $ (1) $。
- 如何判断队列是否为空或满：
- 当
front == rear 时，队列为空或满。
- 解决方案：
- 显式保持队列中元素的计数。
- 数组大小设为 $ n+1 $，只允许存储 $ n $ 个元素：
front = rear + 1 时队列为空。front = rear + 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
40
| template <typename E>
class AQueue : public Queue<E> {
private:
int maxSize;
int front;
int rear;
E *listArray;
public:
AQueue(int size = defaultSize) {
maxSize = size + 1;
rear = 0;
front = 1;
listArray = new E[maxSize];
}
~AQueue() { delete[] listArray; }
void clear() { rear = 0; front = 1; }
void enqueue(const E& it) {
Assert(((rear + 2) % maxSize) != front, "Queue is full");
rear = (rear + 1) % maxSize;
listArray[rear] = it;
}
E dequeue() {
Assert(length() != 0, "Queue is empty");
E it = listArray[front];
front = (front + 1) % maxSize;
return it;
}
const E& frontValue() const {
Assert(length() != 0, "Queue is empty");
return listArray[front];
}
virtual int length() const {
return ((rear + maxSize) - front + 1) % maxSize;
}
};
|
链表实现的队列
- 结构：
- 使用头结点。
front 指针始终指向头结点。rear 指针指向队列最后一个链节点。
- 操作：
- Enqueue：在链表末尾插入新元素，并将
rear 指向新插入的节点。
- Dequeue：移除并返回链表的第一个元素。
时间复杂度
- 所有成员函数：对于两种实现，所有操作的时间复杂度均为
$ (1) $。
空间复杂度
- 数组实现：如果队列未满，会有一些空间浪费。
- 链表实现：每个元素都有链接域的开销。
数组实现的队列 (Array
Implementation)
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
| #include <iostream>
#include <cassert>
template <typename E>
class Queue {
public:
virtual ~Queue() {}
virtual void clear() = 0;
virtual void enqueue(const E&) = 0;
virtual E dequeue() = 0;
virtual const E& frontValue() const = 0;
virtual int length() const = 0;
};
template <typename E>
class AQueue : public Queue<E> {
private:
int maxSize;
int front;
int rear;
E* listArray;
public:
AQueue(int size = 100) {
maxSize = size + 1;
rear = 0;
front = 1;
listArray = new E[maxSize];
}
~AQueue() {
delete[] listArray;
}
void clear() {
rear = 0;
front = 1;
}
void enqueue(const E& it) {
assert((rear + 2) % maxSize != front && "队列已满");
rear = (rear + 1) % maxSize;
listArray[rear] = it;
}
E dequeue() {
assert(length() != 0 && "队列为空");
E it = listArray[front];
front = (front + 1) % maxSize;
return it;
}
const E& frontValue() const {
assert(length() != 0 && "队列为空");
return listArray[front];
}
virtual int length() const {
return (rear + maxSize - front + 1) % maxSize;
}
};
int main() {
AQueue<int> queue;
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
std::cout << "Front Value: " << queue.frontValue() << std::endl;
std::cout << "Dequeued: " << queue.dequeue() << std::endl;
std::cout << "Front Value: " << queue.frontValue() << std::endl;
return 0;
}
|
链表实现的队列
(Linked List Implementation)
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
| #include <iostream>
#include <cassert>
template <typename E>
class Node {
public:
E data;
Node* next;
Node(const E& data) : data(data), next(nullptr) {}
};
template <typename E>
class Queue {
public:
virtual ~Queue() {}
virtual void clear() = 0;
virtual void enqueue(const E&) = 0;
virtual E dequeue() = 0;
virtual const E& frontValue() const = 0;
virtual int length() const = 0;
};
template <typename E>
class LQueue : public Queue<E> {
private:
Node<E>* front;
Node<E>* rear;
int currSize;
public:
LQueue() : front(nullptr), rear(nullptr), currSize(0) {}
~LQueue() {
clear();
}
void clear() {
while (length() > 0) {
dequeue();
}
}
void enqueue(const E& it) {
Node<E>* newNode = new Node<E>(it);
if (rear) {
rear->next = newNode;
} else {
front = newNode;
}
rear = newNode;
currSize++;
}
E dequeue() {
assert(length() != 0 && "队列为空");
Node<E>* temp = front;
E it = front->data;
front = front->next;
delete temp;
currSize--;
if (length() == 0) {
rear = nullptr;
}
return it;
}
const E& frontValue() const {
assert(length() != 0 && "队列为空");
return front->data;
}
virtual int length() const {
return currSize;
}
};
int main() {
LQueue<int> queue;
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
std::cout << "Front Value: " << queue.frontValue() << std::endl;
std::cout << "Dequeued: " << queue.dequeue() << std::endl;
std::cout << "Front Value: " << queue.frontValue() << std::endl;
return 0;
}
|
代码说明
- 数组实现 (
AQueue):
- 使用数组存储队列元素。
- 通过取模运算实现循环队列。
- 提供了入队、出队、获取前端值及清空队列的方法。
- 链表实现 (
LQueue):
- 使用链表节点实现队列。
- 支持动态调整大小，避免了数组的固定大小限制。
- 提供了相同的功能，包括入队、出队、获取前端值及清空队列。
这两个实现各有优缺点，数组实现具有较好的缓存性能，而链表实现则能灵活应对动态变化的队列大小。
