关于 C++ 队列算法，你该了解这些【第一集：顺序存储队列】_c++中如何将队列第一个使用完放回第一个

观看本系列博文提醒：
你将学会队列的两种最基本的表现形式：顺序存储队列 和 链式存储队列；
一个扩展队列的使用方法：循环队列；
两个企业级队列的应用：线性池中的任务队列 和 优先链式存储队列。

---

队列的原理

队列是一种受限的线性表，(Queue)，它是一种运算受限的线性表,先进先出(FIFO First In First Out).

例如上图中，圆球1先进，也是圆球1先出。

队列是一种受限的线性结构

1. 它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。
2. 生活中队列场景随处可见: 比如在电影院, 商场, 或者厕所排队。。。。。。

由上图我们可以知道，队列中有两个“指针”，front指向队首，rear指向队尾；
至于length，他是整个队列的总长度（因为一个队列他是有固定长度的）。

---

顺序存储队列

采用数组来保存队列的元素，设立一个队首指针 front ，一个队尾指针 rear，分别指向队首和队尾元素。则 rear - front 即为存储的元素个数！

因为队列的长度是有限的，所以我们可以给队列的长度定义一个宏：
#define QUEUE_MAX 5 // 队列的最大存储个数

队列的定义

typedef int dateType;	// 队列存储的类型

typedef struct arrayQueue {
	dateType queue[QUEUE_MAX];	// 存储队列元素的数组
	int front;	// 队头“指针”
	int rear;	// 队尾“指针”
}seqQueue;
1
2
3
4
5
6
7

就是一个结构体，队列的储存是以数组方式存储的。
还定义了整型变量，front用于定位到队首元素，rear用于定位到队尾元素。

---

队列的初始化

// 队列初始化
void inItQueue(seqQueue* seq) {
	if (!seq) {	// 合法性检查
		return;
	}

	seq->front = seq->rear = 0;		// 对头与队尾“指针”都为零
}
1
2
3
4
5
6
7
8

初始化后他是一个空队列，所以两个“指针”都得为零。

---

判断队列是否为空

// 判断队列是否为空
bool estimateQueueEmpty(seqQueue* seq) {
	if (!seq) {	// 合法性检查
		cout << "队列不存在！";
		return false;
	}

	if (seq->front == seq->rear) {	// 当头尾“指针”相等时，为空队列
		return true;
	}

	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

由上图我们可以知道，当队列为空时，“指针”front和rear都是指向0的，所以我们可以以此作为判断。

---

判断队列是否已满

// 判断队列是否已满
bool estimateQueueFull(seqQueue* seq) {
	if (!seq) {
		cout << "队列不存在！";
		return false;
	}

	if (seq->rear == QUEUE_MAX) {	// 当队尾“指针”等于队列最大存储个数时，为满
		return true;
	}

	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

先提前跟大家说一下，因为顺序存储队列是以数组方式存储的，最大下标是4，他的尾“指针”rear作为下标的话都是指向最后一个元素的下一个位置的，所以我们插入元素时，可以直接使用rear作为插入位置的下标。也就是说，当队列满时，他是与我们定义的数组长度是相等的，即我们定义的宏定义#define QUEUE_MAX 5，我们可以用rear与宏定义作比较，当他们相等时，说明队列已经满了。

---

入队，将元素插入队列中

// 入队，将元素插入队列中
bool enterQueue(seqQueue* seq, dateType date) {	// 参数二是入队的元素
	if (!seq) {
		cout << "队列不存在！";
		return false;
	}

	if (estimateQueueFull(seq)) {
		cout << "队列已满！插入 " << date << " 失败！" << endl;
		return false;
	}

	seq->queue[seq->rear] = date;	// 在队尾插入元素date
	seq->rear += 1;		// 队尾“指针”后移一位

	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

就如同我们上面所说的，当需要插入一个元素时，只需要将“指针”rear作为下标插入即可，然后再将rear加一，指向下一个空白的区域（如上图）。front“指针”永远都是指向头部第一个元素的。

---

出队，将元素从头部删除掉

他有两种出队方式：

1. 将队列中队首的元素出队，后面的元素向前移动。优点：保证了队列的内存都能得到最大的利用，不浪费；缺点：假如队列中有成千上万个数据的话，删除一个元素造成后续那么多个元素的移动，会造成很大的开销，影响性能。
2. 将队列中的队首元素出队，出队后对头“指针”front后移一位。优点：没有涉及到元素的移动，效率很快；缺点：由于他是移动头指针，所以每次出队，都会空置出一个内存区域，浪费内存。

情况一：将队列中队首的元素出队，后面的元素向前移动

// 出队一，将队列中队首的元素出队，后面的元素向前移动
bool deleteQueueFront_1(seqQueue* seq, dateType* date) {	// 参数二：保存出列的元素返回
	if (!seq) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateQueueEmpty(seq)) {
		cout << "队列为空！" << endl;
		return false;
	}

	if (!date) {
		cout << "date指针为空！" << endl;
		return true;
	}

	// 保存出列的元素返回
	*date = seq->queue[seq->front];

	// 从队头元素的下一个元素开始遍历，将后续的所有元素都往前移动一个位置
	for (int i = seq->front + 1; i < seq->rear; i++) {
		seq->queue[i - 1] = seq->queue[i];
	}
	seq->rear -= 1;

	return true;
}
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

从队头元素的下一个元素开始遍历，将后续的所有元素都往前移动一个位置。

上图就是出队前后的效果图。

可能有些朋友会有疑问，a1使出对了没错，但是为什么会有两个a3啊？
有这样的疑问是正常的。因为我们使用的删除方式是将后面的元素都往前移动一个位置，所以最后一个元素还是会保留在原来的位置的。但是，我们的尾“指针”rear最后自减了一，现在等于二，所以，就算是保留在哪里也不会出什么问题，因为我们根本访问不了他。
我们遍历队列最多只能访问前两个元素。

如果还是不懂的朋友可以把他理解成下图，就知道了。

准确来讲，还是第一幅图贴近现实！

情况二：将队列中的队首元素出队，出队后对头“指针”front后移一位

// 出队二，将队列中的队首元素出队，出对后对头“指针”front后移一位
bool deleteQueueFront_2(seqQueue* seq, dateType* date) {	// 参数二：保存出列的元素返回
	if (!seq) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateQueueEmpty(seq)) {
		cout << "队列为空！" << endl;
		return false;
	}

	if (!date) {
		cout << "date指针为空！" << endl;
		return false;
	}

	if (seq->front >= QUEUE_MAX) {
		cout << "队列已到尽头！" << endl;
		return false;
	}

	// 保存出列的元素返回
	*date = seq->queue[seq->front];

	seq->front += 1;	// 队首“指针”后移一位

	return true;
}
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

第二种方式要比第一种方式要多一次判断合法性检查。如果front“指针”已经大于或者等于队列的最大元素存储，那后面的操作就没有意义了。

如果合法性都正确，那么只需要将队首“指针”front自增一就行了。

如上图就是出队前和出队后的效果图。

也跟第一种删除方式差不多，现在是头元素保留在原来的位置，只是front“指针”只增一了，我们也就无法访问到原来的元素了。

不懂的朋友也可以把他理解成下图：

准确来讲，还是第一幅图贴近现实！

---

获取队列的首元素

// 获取队列的首元素
bool gainQueueFrontValue(seqQueue* seq, dateType* date) {
	if (!seq) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateQueueEmpty(seq)) {
		cout << "队列为空！" << endl;
		return false;
	}

	if (!date) {
		cout << "date指针为空！" << endl;
		return false;
	}

	// 保存出列的元素返回
	*date = seq->queue[seq->front];

	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

也就是和出队的代码差不多，合法性检查之后，就像元素赋值给date返回。

---

修改队列中任意位置的值

// 修改队列中任意位置的值
bool alterQueueValue(seqQueue* seq, int i, dateType date) {	// 参数二：修改位置；参数三：修改后的值
	if (!seq) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateQueueEmpty(seq)) {
		cout << "队列为空！" << endl;
		return false;
	}

	if (!date) {
		cout << "date指针为空！" << endl;
		return false;
	}

	if (i < seq->front || i >= seq->rear) {
		cout << "修改位置不合法！" << endl;
		return false;
	}

	for (int j = seq->front; j < seq->rear; j++) {
		if (i-1 == j) {
			seq->queue[j] = date;
			break;
		}
	}

	return true;
}
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

这个也是很简单的，从队首开始遍历，直到找到对应位置位置。将元素修改后break退出，然后结束函数。

注意：代码中，我们判断时对 i 进行了减一，我们不是从0开始数的，而是从1开始数。

---

获取队列中的元素个数

// 获取队列中的元素个数
int size(seqQueue* seq) {
	if (!seq) {
		cout << "队列不存在！" << endl;
		return false;
	}

	return seq->rear - seq->front;
}
1
2
3
4
5
6
7
8
9

我们可以将队尾“指针”rear减去队首“指针”front，就可以得到队列的元素个数了。

---

清空队列

// 清空队列
void clearQueue(seqQueue* seq) {
	if (!seq) {
		return ;
	}

	seq->front = seq->rear = 0;		// 对头与队尾“指针”都为零
}
1
2
3
4
5
6
7
8

清空队列和初始化队列都是一样的，将队首和队尾“指针”赋值0即可。

---

输出队列中的元素

// 输出队列中的元素
void queuePrint(seqQueue* seq) {
	if (!seq) {
		cout << "队列不存在！";
		return;
	}

	if (estimateQueueEmpty(seq)) {
		cout << "队列为空！" << endl;
		return;
	}

	for (int i = seq->front; i < seq->rear; i++) {
		cout << seq->queue[i] << " ";
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

测试代码：

#include <iostream>
#include <Windows.h>

using namespace std;

#define QUEUE_MAX 5		// 队列的最大存储个数

typedef int dateType;	// 队列存储的类型

typedef struct arrayQueue {
	dateType queue[QUEUE_MAX];	// 存储队列元素的数组
	int front;	// 对头“指针”
	int rear;	// 队尾“指针”
}seqQueue;


// 队列初始化
void inItQueue(seqQueue* seq) {
	if (!seq) {
		return;
	}

	seq->front = seq->rear = 0;		// 对头与队尾“指针”都为零
}

// 判断队列是否为空
bool estimateQueueEmpty(seqQueue* seq) {
	if (!seq) {
		cout << "队列不存在！";
		return false;
	}

	if (seq->front == seq->rear) {	// 当头尾“指针”相等时，为空队列
		return true;
	}

	return false;
}

// 判断队列是否已满
bool estimateQueueFull(seqQueue* seq) {
	if (!seq) {
		cout << "队列不存在！";
		return false;
	}

	if (seq->rear == QUEUE_MAX) {	// 当队尾“指针”等于队列最大存储个数时，为满
		return true;
	}

	return false;
}

// 入队，将元素插入队列中
bool enterQueue(seqQueue* seq, dateType date) {	// 参数二是入队的元素
	if (!seq) {
		cout << "队列不存在！";
		return false;
	}

	if (estimateQueueFull(seq)) {
		cout << "队列已满！插入 " << date << " 失败！" << endl;
		return false;
	}

	seq->queue[seq->rear] = date;	// 在队尾插入元素date
	seq->rear += 1;		// 队尾“指针”后移一位

	return true;
}

// 出队一，将队列中队首的元素出队，后面的元素向前移动
bool deleteQueueFront_1(seqQueue* seq, dateType* date) {	// 参数二：保存出列的元素返回
	if (!seq) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateQueueEmpty(seq)) {
		cout << "队列为空！" << endl;
		return false;
	}

	if (!date) {
		cout << "date指针为空！" << endl;
		return true;
	}

	// 保存出列的元素返回
	*date = seq->queue[seq->front];

	// 从头元素的下一个元素开始遍历，将后续的所有元素都往前移动一个位置
	for (int i = seq->front + 1; i < seq->rear; i++) {
		seq->queue[i - 1] = seq->queue[i];
	}
	seq->rear -= 1;

	return true;
}

// 出队二，将队列中的队首元素出队，出对后对头“指针”front后移一位
bool deleteQueueFront_2(seqQueue* seq, dateType* date) {	// 参数二：保存出列的元素返回
	if (!seq) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateQueueEmpty(seq)) {
		cout << "队列为空！" << endl;
		return false;
	}

	if (!date) {
		cout << "date指针为空！" << endl;
		return false;
	}

	if (seq->front >= QUEUE_MAX) {
		cout << "队列已到尽头！" << endl;
		return false;
	}

	// 保存出列的元素返回
	*date = seq->queue[seq->front];

	seq->front += 1;	// 队首“指针”后移一位

	return true;
}

// 获取队列的首元素
bool gainQueueFrontValue(seqQueue* seq, dateType* date) {
	if (!seq) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateQueueEmpty(seq)) {
		cout << "队列为空！" << endl;
		return false;
	}

	if (!date) {
		cout << "date指针为空！" << endl;
		return false;
	}

	// 保存出列的元素返回
	*date = seq->queue[seq->front];

	return true;
}

// 修改队列中任意位置的值
bool alterQueueValue(seqQueue* seq, int i, dateType date) {	// 参数二：修改位置；参数三：修改后的值
	if (!seq) {
		cout << "队列不存在！" << endl;
		return false;
	}

	if (estimateQueueEmpty(seq)) {
		cout << "队列为空！" << endl;
		return false;
	}

	if (!date) {
		cout << "date指针为空！" << endl;
		return false;
	}

	if (i < seq->front || i >= seq->rear) {
		cout << "修改位置不合法！" << endl;
		return false;
	}

	for (int j = seq->front; j < seq->rear; j++) {
		if (i-1 == j) {
			seq->queue[j] = date;
			break;
		}
	}

	return true;
}

// 获取队列中的元素个数
int size(seqQueue* seq) {
	if (!seq) {
		cout << "队列不存在！" << endl;
		return false;
	}

	return seq->rear - seq->front;
}


// 输出队列中的元素
void queuePrint(seqQueue* seq) {
	if (!seq) {
		cout << "队列不存在！";
		return;
	}

	if (estimateQueueEmpty(seq)) {
		cout << "队列为空！" << endl;
		return;
	}

	for (int i = seq->front; i < seq->rear; i++) {
		cout << seq->queue[i] << " ";
	}
	cout << endl;
}

// 清空队列
void clearQueue(seqQueue* seq) {
	if (!seq) {
		return ;
	}

	seq->front = seq->rear = 0;		// 对头与队尾“指针”都为零
}

int main(void) {
	seqQueue que;

	// 初始化队列
	inItQueue(&que);

	// 插入元素
	for (int i = 0; i < 6; i++) {
		enterQueue(&que, i * 5);
	}

	// 输出队列中的元素
	queuePrint(&que);

	// 元素出队1
	dateType date = 0;
	deleteQueueFront_1(&que, &date);
	cout << "出队的元素是：" << date << endl;
	cout << "出队元素后：" << endl;
	queuePrint(&que);

	cout << endl;

	// 元素出队2
	deleteQueueFront_2(&que, &date);
	cout << "出队的元素是：" << date << endl;
	cout << "出队元素后：" << endl;
	queuePrint(&que);

	cout << endl;

	/*for (int i = 0; i < 5; i++) {
		if (deleteQueueFront_2(&que, &date)) {
			cout << "出队的元素是：" << date << endl;
		} else {
			cout << "出队失败！" << endl;
		}
		
	}*/

	// 获取队首的元素
	gainQueueFrontValue(&que, &date);
	cout << "队首的元素是：" << date << endl;

	cout << endl;

	// 修改队列中任意位置的值
	if (alterQueueValue(&que, 2, 666)) {
		cout << "修改成功！" << endl;
	} else {
		cout << "修改失败!" << endl;
	}
	cout << "修改后：" << endl;
	queuePrint(&que);

	cout << endl;

	cout << "队列的元素个数是：" << size(&que) << endl;


	// 清空队列
	clearQueue(&que);

	system("pause");
	return 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
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289

---

总结：
顺序存储队列就跟数组一样，其操作都不难，只要注意下标就行！

注意：由于一篇博客内容太多，所以我将会把他分成几篇进行讲解！

祝各位学习愉快！

---

下集提醒：
你将学会队列的另一种最基本的表现形式：链式存储队列；
请持续关注！