原文
作者：
朱赵彧铭
, 时间：2023-09-17 12:30:26 , 所有人可见, 阅读 3
朱赵彧铭
, 时间：2023-09-17 12:30:26 , 所有人可见, 阅读 3
文章目录
一、循环队列的实现（数组模拟）
1、队列的特点
2、数组模拟队列
3、编写队列结构
4、入队操作
5、出队操作
6、判空和判满
7、构造和析构
8、完整代码
一、循环队列的实现（数组模拟）
1、队列的特点
队列是一种先进先出的线性表
上面的队列中，1最先进入队列，7最后进入，因此1最先出队而7最后出队
2、数组模拟队列
例如：上图是一个数组，我们怎样才能让数组的行为和队列一致呢？
例如上面数组中的1和2，如何让他们写入呢？
直接利用数组和索引
array[0] = 1; array[1] = 2;
1
这样看起来可以，但是有一个问题，我们需要时刻记得我们入队了几次，否则就无法根据索引入队了。
那么其实我们可以把这个索引用一个变量表示，每次入队只需递增它就可以了。
array[tail] = 1; ++tail;
array[tail] = 2; ++tail;
1
2
出队的话，可以利用和入队类似的办法，但数组无法删除元素，但我们可以用一个数组索引的变量表示队头的位置，每次出队只需把这个索引向递增即可。
例如让上面的1和2出队
++head; ++head;
1
解决了入队出队问题，我们就来试一下。
队空 队满 出队到队空
看起来还不错，但仔细观察出队到队空时，队列里面没有数了，也就是队空了，可以继续加数据，但是，表示队列头尾的变量已经到了数组的最右边的下一个索引，已经没办法再往右了，同时数组还是空的。
怎么办呢，如果队尾指针变量在到数组最后一个之后自动移动到数组第一个位置就可以解决了，如何才能做到呢？
可以利用模运算！
// 将递加操作用用模运算替代
tail = (tail+1) % 6; // 6是数组的大小
// 对于对头也是一样
head = (head+1) % 6;
1
2
3
4
当tail没有到达数组末尾的时候，tail+1都小于6，因此，模6所得值还是本身，如果tail到达数组末尾，tail+1 = 6模值将会变成0，完美地将tail移动到了数组开头！
再来试一下
队空 入队到队满 队满
发现，当tail到数组末尾之后自动移动到开头了！
但问题就来了，要怎么判断队列满了呢？很显可以通过head = tail，可是，队空的时候它们也是相等的，这怎么办？可以改变队空或者队满的条件来解决冲突。这里可以将数组的一个格子空出来，当数组还有一个格子的时候，就当作队列已经满了。
第一种情况 第二种情况
第一种情况，很明显，可以用head == tail + 1 判断队满；但第二种情况好像不行，回想之前的模运算，很快可以得到head == (tail+1) % 6，而且这个式子也适用于第一种情况！
3、编写队列结构
很明显，这个队列包含一个数组，还需要队头、队尾两个索引变量和队列大小这四个数据，同时包含入队、出队、判空、判满这四个成员函数。
// 队列结构
class Queue {
private:
int* data;
std::size_t head;
std::size_t tail;
std::size_t size;
public:
inline Queue(std::size_t sz);
inline ~Queue();
void push();
int pop(); // 为了方便测试，出队时返回出队的数据
inline bool isEmpty();
inline bool isFull();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
4、入队操作
入队时，先将队尾所指位置放入需要入队的值，再将队尾后移。
代码逻辑：
判断是否队满
没满则执行入队操作
满了就输出错误信息
void Queue::push(int val) {
if (!isFull()) {
data[tail] = val;
tail = (tail+1) % (size+1);
} else {
std::cerr << val << " push failed, Queue is full!" << std::endl;
}
}
1
2
3
4
5
6
7
8
5、出队操作
先保存对头位置的值，再将对头指针后移，最后返回保存的值。
代码逻辑：
判断是否队空
不空则执行出队操作
空则输出错误信息
int Queue::pop() {
if (!isEmpty()) {
auto temp = data[head];
head = (head+1) % (size+1);
return temp;
} else {
std::cout << "Pop failed, Queue is empty!" << std::endl;
return INT_MAX; // 用以表示队空
}
}
1
2
3
4
5
6
7
8
9
10
6、判空和判满
inline bool Queue::isEmpty() {
return head == tail;
}
inline bool Queue::isFull() {
return head == (tail+1) % (size+1);
}
1
2
3
4
5
6
7
7、构造和析构
// 由于使用时才传入队列大小，因此需要动态数组，sz+1是为了空一格
inline Queue::Queue(std::size_t sz)
: data(new int[sz+1]), head(0), tail(0), size(sz) { }
inline ~Queue::Queue() { delete data[]; }
1
2
3
4
5
8、完整代码
// Queue.h 队列类头文件
#include <cstddef>
// 队列结构
class Queue {
private:
int* data;
std::size_t head;
std::size_t tail;
std::size_t size;
public:
inline Queue(std::size_t sz);
inline ~Queue();
void push(int val);
int pop(); // 为了方便测试，出队时返回出队的数据
inline bool isEmpty();
inline bool isFull();
};
/*inline成员函数都定义到类的头文件中*/
// 由于使用时才传入队列大小，因此需要动态数组，sz+1是为了空一格
inline Queue::Queue(std::size_t sz)
: data(new int[sz + 1]), head(0), tail(0), size(sz) { }
inline Queue::~Queue() { delete[] data; }
inline bool Queue::isEmpty() {
return head == tail;
}
inline bool Queue::isFull() {
return head == (tail + 1) % (size + 1);
}
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
// Queue.cpp 队列类函数的实现
#include <iostream>
#include "Queue.h"
#include <climits>
void Queue::push(int val) {
if (!isFull()) {
data[tail] = val;
tail = (tail + 1) % (size + 1);
}
else {
std::cerr << val << " push failed, Queue is full!" << std::endl;
}
}
int Queue::pop() {
if (!isEmpty()) {
auto temp = data[head];
head = (head + 1) % (size + 1);
return temp;
}
else {
std::cout << "Pop failed, Queue is empty!" << std::endl;
return INT_MAX; // 用以表示队空
}
}
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
// QueueTest.cpp 队列测试
#include <iostream>
#include "Queue.h"
int main(void) {
Queue que(5);
// 测试正常入队
que.push(1);
// 测试正常出队
que.pop();
// 一直入队，查看到数组末端会怎样
que.push(2);
que.push(3);
que.push(4);
que.push(5);
que.push(6);
que.push(7);// 测试队满时入队
// 测试出队到队空
for (auto i = 0; i < 5; ++i)
std::cout << que.pop() << " ";
std::cout << std::endl;
// 测试队空出队
que.pop();
/*期望输出
7 push failed, Queue is full!
2 3 4 5 6
Pop failed, Queue is empty!
*/
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
文章知识点与官方知识档案匹配，可进一步学习相关知识
