- 循环队列
- 判断入队时队尾指针应该如何变化
- 判断出队时队头指针应该如何变化
- 判断队列是否已满或已空
- 不同情况的实现方式
- 方式一
- 方式二
- 方式三
- 判空
- 计算队列元素个数
- 整体实现
- 方式一
- 方式二
- 方式三
为解决假溢出问题，采用循环队列，循环队列即一种逻辑上的环状结构，但在物理空间上仍然为顺序存储，即数组
循环队列示例图
其中 f 为头指针，指向队列的第一个元素，r 为尾指针，指向队尾元素的下一个位置。
由于循环队列的处理有三种方法，此处先不给出具体结构体的定义；详细实现和采用的方式有关；
判断入队时队尾指针应该如何变化一般情况，队尾指针简单后移 (rear + 1) 即可，队头指针不变
而当出现多次出队列以后，队尾指针到达数组最后一位时 (如下图)
简单的 rear + 1 将不会满足实际情况，此时，rear = (rear + 1) % MAX 将满足实际情况。并且此公式也适用于一般情况。因此可以得出结论，入队列时，在队列未满时，元素入队，队尾元素 rear = (rear + 1) % MAX ；
入队列前需要判断队列是否为满；
判断出队时队头指针应该如何变化当队列非空时，队头元素出队列，队头指针移动；
出队列的指针变化和入队列一样 front = (front + 1) % MAX
出队需判断队列是否为空；
接下来讨论怎样判断队列的满或者空；
判断队列是否已满或已空当队列已满时，有如下情况：
左图为一直入队列的情况，右图为出队列一次的情况
从图中可以看出，队满时，front = rear；是否能使用这个条件判断队列已满呢？再看队列为空时；
可见，在这种情况下不能使用 f = r 来判断队列为空，也不能判断队列已满；对此，有一些处理方式；
不同情况的实现方式 方式一少使用一个存储单元，这样就可以避免队列满时 f = r，并且此时 f = r 可以判断队列为空；
此时，队满：(rear + 1) % MAX = front 队空：rear = front
结构体
typedef int Type;
#define MAX 20
typedef struct {
Type data[MAX];
int front, rear;
} SqQueue;
初始化
void InitQueue(SqQueue &Q) {
Q.front = 0;
Q.rear = 0;
}
入队列：(Q.rear + 1) % MAX == Q.front 为满
bool EnQueue(SqQueue &Q, Type x) {
if((Q.rear + 1) % MAX == Q.front) {
return false;
}
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MAX;
return true;
}
出队列：Q.front == Q.rear 时为空
bool DeQueue(SqQueue &Q, Type &x) {
if(Q.front == Q.rear) {
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MAX;
return true;
}
方式二
在结构体中设置一个表示队列大小的变量 size， 入队时加一，出队时减一，指针随之变化；
结构体
typedef struct {
Type data[MAX];
int front, rear;
int size;
} SqQueue;
初始化
void InitQueue(SqQueue &Q) {
Q.front = 0;
Q.rear = 0;
Q.size = 0;
}
入队列代码： size = MAX 时队列已满，不能入队列；
bool EnQueue(SqQueue &Q, Type x) {
if(Q.size == MAX) {
return false;
}
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MAX;
Q.size++;
return true;
}
出队列：size = 0 为空，不能出队列；
bool DeQueue(SqQueue &Q, Type &x) {
if(Q.size == 0) {
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MAX;
return true;
}
方式三
在结构体中设置标志 tag， tag = 0 &&Q.front == Q.rear 表示队列为空， tag = 1 && Q.front == Q.rear 表示队列已满。初始时 tag 为 0，此后，若遇入队列后 Q.front == Q.rear 则表示队列必满，置 tag = 1;若遇到出队列后 Q.front == Q.rear 则表示队列必空；由此可写出其入队列和出队列代码；
结构体
typedef struct {
Type data[MAX];
int front, rear;
int tag;
} SqQueue;
入队列：
Q.tag == 1 && Q.front == Q.rear 表示队列已满，若队列未满，则入队列，入队列后若 Q.front == Q.rear 则队列必满，此时置 tag 为 1；
bool EnQueue(SqQueue &Q, Type x) {
if(Q.tag == 1 && Q.front == Q.rear) {
return false;
}
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MAX;
if(Q.front == Q.rear) { //若入栈后相等，此时队列必满
Q.tag = 1;
}
return true;
}
出队列：
Q.tag == 0 && Q.front == Q.rear 表示队列已空，若队列未满，则入队列，出队列后若 Q.front == Q.rear 则队列必空，此时置 tag 为 0；
bool DeQueue(SqQueue &Q, Type &x) {
if(Q.tag == 0 && Q.front == Q.rear) { //队列为空时
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MAX;
if(Q.front == Q.rear) { //若出队列后相等，此时队列必空
Q.tag = 0;
}
return true;
}
判空
-
空一个位置
只有空的时候会出现 Q.front == Q.rear
bool QueueEmpty(SqQueue Q) { if(Q.front == Q.rear) { return true; } return false; } -
设置 size
bool QueueEmpty(SqQueue Q) { if(Q.size == 0) { return true; } return false; } -
设置 tag
bool QueueEmpty(SqQueue Q) { if(Q.front == Q.rear && Q.tag == 0) { return true; } return false; }
-
方式一
int length(SqQueue Q) { return (Q.rear + MAX - Q.front) % MAX; } -
方式二
int length(SqQueue Q) { return Q.size; } -
方式三
由于队列满时 Q.front == Q.rear，故需单独对队列满时进行处理
int length(SqQueue Q) { if(Q.tag == 1 && Q.front == Q.rear) { return MAX; } return (Q.rear + MAX - Q.front) % MAX; }
由于有三种不同的循环队列处理方式，因此也使用三种不同方式
方式一数组空一个位置
测试方案
测试方案：依次入队列至如下情况，此时将不能入队列， rear = 7，front = 0；
出队列四次，入队列两次，此时队头为 4，队尾指针为 1；
出队列置队列为空，进行判空
#includeusing namespace std; typedef char Type; #define MAX 8 typedef struct { Type data[MAX]; int front, rear; } SqQueue; void InitQueue(SqQueue &Q) { Q.front = 0; Q.rear = 0; } bool EnQueue(SqQueue &Q, Type x) { if((Q.rear + 1) % MAX == Q.front) { return false; } Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % MAX; return true; } bool DeQueue(SqQueue &Q, Type &x) { if(Q.front == Q.rear) { return false; } x = Q.data[Q.front]; Q.front = (Q.front + 1) % MAX; return true; } bool QueueEmpty(SqQueue Q) { if(Q.front == Q.rear) { return true; } return false; } int length(SqQueue Q) { return (Q.rear + MAX - Q.front) % MAX; } int main() { SqQueue queue; InitQueue(queue); char chs[7] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'}; for(int i = 0; i < 7; i++) { EnQueue(queue, chs[i]); } if(!EnQueue(queue, 'x')) { cout << "队列已满，入队失败" << endl; } cout << queue.front << " " << queue.rear << endl; //出队四次 Type x; DeQueue(queue, x); cout << x << endl; DeQueue(queue, x); cout << x << endl; DeQueue(queue, x); cout << x << endl; DeQueue(queue, x); cout << x << endl; cout << "队列元素个数为 " << length(queue) << endl; //入队两次 EnQueue(queue, 'h'); EnQueue(queue, 'i'); cout << "队列元素个数为 " << length(queue) << endl; cout << queue.front << " " << queue.rear << endl; while(!QueueEmpty(queue)) { DeQueue(queue, x); cout << x << " "; } return 0; }
通过结果分析，和手动模拟一致；
方式二结构体中设置 size
由于此类情况可以使用全部空间，对此进行检验
测试方案
测试方案：依次入队列至如下情况，此时， rear = 7，front = 0；
出队列四次，入队列五次，此时队列已满；将不能继续入队，指针均为 4
出队列置队列为空，进行判空
#include方式三using namespace std; typedef char Type; #define MAX 8 typedef struct { Type data[MAX]; int front, rear; int size; } SqQueue; void InitQueue(SqQueue &Q) { Q.front = 0; Q.rear = 0; Q.size = 0; } bool EnQueue(SqQueue &Q, Type x) { if(Q.size == MAX) { return false; } Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % MAX; Q.size++; return true; } bool DeQueue(SqQueue &Q, Type &x) { if(Q.size == 0) { return false; } x = Q.data[Q.front]; Q.front = (Q.front + 1) % MAX; Q.size--; return true; } bool QueueEmpty(SqQueue Q) { if(Q.size == 0) { return true; } return false; } int length(SqQueue Q) { return Q.size; } int main() { SqQueue queue; InitQueue(queue); char chs[7] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'}; for(int i = 0; i < 7; i++) { EnQueue(queue, chs[i]); } cout << queue.front << " " << queue.rear << endl; //出队四次 Type x; DeQueue(queue, x); cout << x << endl; DeQueue(queue, x); cout << x << endl; DeQueue(queue, x); cout << x << endl; DeQueue(queue, x); cout << x << endl; cout << "队列元素个数为 " << length(queue) << endl; //入队五次 EnQueue(queue, 'h'); EnQueue(queue, 'i'); EnQueue(queue, 'j'); EnQueue(queue, 'k'); EnQueue(queue, 'l'); cout << "队列元素个数为 " << length(queue) << endl; cout << queue.front << " " << queue.rear << endl; if(!EnQueue(queue, 'x')) { cout << "队列已满，入队失败" << endl; } while(!QueueEmpty(queue)) { DeQueue(queue, x); cout << x << " "; } return 0; }
此处和方式二使用同样的测试方案；
#includeusing namespace std; typedef char Type; #define MAX 8 typedef struct { Type data[MAX]; int front, rear; int tag; } SqQueue; void InitQueue(SqQueue &Q) { Q.front = 0; Q.rear = 0; Q.tag = 0; } bool EnQueue(SqQueue &Q, Type x) { if(Q.tag == 1 && Q.front == Q.rear) { return false; } Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % MAX; if(Q.front == Q.rear) { //若入栈后相等，此时队列必满 Q.tag = 1; } return true; } bool DeQueue(SqQueue &Q, Type &x) { if(Q.tag == 0 && Q.front == Q.rear) { //队列为空时 return false; } x = Q.data[Q.front]; Q.front = (Q.front + 1) % MAX; if(Q.front == Q.rear) { //若出栈后相等，此时队列必空 Q.tag = 0; } return true; } bool QueueEmpty(SqQueue Q) { if(Q.front == Q.rear && Q.tag == 0) { return true; } return false; } int length(SqQueue Q) { if(Q.tag == 1 && Q.front == Q.rear) { return MAX; } return (Q.rear + MAX - Q.front) % MAX; } int main() { SqQueue queue; InitQueue(queue); char chs[7] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'}; for(int i = 0; i < 7; i++) { EnQueue(queue, chs[i]); } cout << queue.front << " " << queue.rear << endl; //出队四次 Type x; DeQueue(queue, x); cout << x << endl; DeQueue(queue, x); cout << x << endl; DeQueue(queue, x); cout << x << endl; DeQueue(queue, x); cout << x << endl; cout << "队列元素个数为 " << length(queue) << endl; //入队五次 EnQueue(queue, 'h'); EnQueue(queue, 'i'); EnQueue(queue, 'j'); EnQueue(queue, 'k'); EnQueue(queue, 'l'); cout << "队列元素个数为 " << length(queue) << endl; cout << queue.front << " " << queue.rear << endl; if(!EnQueue(queue, 'x')) { cout << "队列已满，入队失败" << endl; } while(!QueueEmpty(queue)) { DeQueue(queue, x); cout << x << " "; } return 0; }
