问题：什么是顺序队列的假溢出？
从队首倒到队尾完全占用了分配的空间，是溢出。相反，队尾元素占用了分配的最后一个空间，队首元素还是占有的不是第一个分配的空间，相当于队列对外是满的，但是内部空间利用不充分，还有剩余，此时就称为假溢出。
解决假上溢的方法-引入循环队列
把把队列首元素queue[front=0] 接在queue[MAXQSIZE-1]之后，若rear+1 == MAXQSIZE，则令rear=0；
解决办法：使用模运算（%）
//插入元素：
queue[rear] = x;
rear = ( rear + 1 ) % MAXQSIZE;
//删除元素：
x = queue[front];
front = ( front + 1) % MAXQSIZE;
相当于下表为0的元素的前驱变成了原队尾（MAXQSIZE-1）的后继。
遇到新问题
判断队列空或满时，都是 front == rear
解决方案：
- 设置标志，以区别队空、队满
- 另设一个变量，计算元素个数
- 少利用一个空间（以下编码使用这种方式）
少用一个空间如何区别队满？
队满判断条件：front ==（rear+1）% MAXQSIZE；
实现代码
/*
* @Author: jinbo.ma
* @Mail: 18710648068@163.com
* @Date: 2021-05-04 09:39:21
* @LastEditTime: 2021-05-05 16:02:41
*/
#include <stdio.h>
#include <stdlib.h>
#define MAXQSIZE 6
int queue_length (int front, int rear) {
return (rear - front + MAXQSIZE) % MAXQSIZE;
}
int entry_queue (int *q, int *front, int *rear, int data) {
printf ("data=%d\n", data);
//判断队满
if ( (*rear+1)%MAXQSIZE == *front ) {
return 0;
}
q[*rear] = data;
*rear = (*rear + 1) % MAXQSIZE;
return 1;
}
int exit_queue (int * q, int *front, int *rear, int *data) {
//判断队空
if (*front == *rear) {
return 0;
}
*data = q[*front];
*front = (*front + 1) % MAXQSIZE;
return 1;
}
/**
* 顺序表-循环队列之实现
*/
int main() {
int queue[MAXQSIZE] = {0}, front = 0, rear = 0;
int data;
//空队出队操作
if ( exit_queue(queue, &front, &rear, &data) ) {
printf("空队列出队成功这是不可能的事情！data=%d\n\n", data);
} else {
printf("空队列出队失败才是正常的, front=%d, rear=%d\n\n", front, rear);
}
printf("\n----------------------------------------------------------------\n");
//求空队列的长度
printf("queue length=%d\n", queue_length(front, rear) );
printf("\n----------------------------------------------------------------\n");
//试验真溢出
for (int i = 0; i <= MAXQSIZE; i++) {
printf("i=%d\n", i);
if ( entry_queue(queue, &front, &rear, 10+i) ) {
printf("data=%d 入队成功: front=%d, rear=%d\n", 10+i, front, rear);
} else {
printf("data=%d 入队失败: front=%d, rear=%d\n", 10+i, front, rear);
}
}
//求队列长度，牺牲一个空间满足了判断队满的情况，故而此时队列长度为MAXQSIZE-1
printf("queue length=%d\n", queue_length(front, rear) );
printf("\n----------------------------------------------------------------\n");
//出队四个元素
for (int i = 0; i < MAXQSIZE-2; i++) {
printf("i=%d\n", i);
if ( exit_queue(queue, &front, &rear, &data) ) {
printf("data=%d 出队成功: front=%d, rear=%d\n", data, front, rear);
} else {
printf("data=%d 出队失败: front=%d, rear=%d\n", data, front, rear);
}
}
printf("\n----------------------------------------------------------------\n");
//假如不是循环队列，此时是不能入队的，继续入队测试循环队列
for (int i = 0; i <= MAXQSIZE; i++) {
printf("i=%d\n", i);
if ( entry_queue(queue, &front, &rear, 15+i) ) {
printf("data=%d 入队成功: front=%d, rear=%d\n", 15+i, front, rear);
} else {
printf("data=%d 入队失败: front=%d, rear=%d\n", 15+i, front, rear);
}
}
//此时队列长度又是MAXQSIZE-1
printf("queue length=%d\n", queue_length(front, rear) );
return 0;
}
执行结果：
空队列出队失败才是正常的, front=0, rear=0
----------------------------------------------------------------
queue length=0
----------------------------------------------------------------
i=0
data=10
data=10 入队成功: front=0, rear=1
i=1
data=11
data=11 入队成功: front=0, rear=2
i=2
data=12
data=12 入队成功: front=0, rear=3
i=3
data=13
data=13 入队成功: front=0, rear=4
i=4
data=14
data=14 入队成功: front=0, rear=5
i=5
data=15
data=15 入队失败: front=0, rear=5
i=6
data=16
data=16 入队失败: front=0, rear=5
queue length=5
----------------------------------------------------------------
i=0
data=10 出队成功: front=1, rear=5
i=1
data=11 出队成功: front=2, rear=5
i=2
data=12 出队成功: front=3, rear=5
i=3
data=13 出队成功: front=4, rear=5
----------------------------------------------------------------
i=0
data=15
data=15 入队成功: front=4, rear=0
i=1
data=16
data=16 入队成功: front=4, rear=1
i=2
data=17
data=17 入队成功: front=4, rear=2
i=3
data=18
data=18 入队成功: front=4, rear=3
i=4
data=19
data=19 入队失败: front=4, rear=3
i=5
data=20
data=20 入队失败: front=4, rear=3
i=6
data=21
data=21 入队失败: front=4, rear=3
queue length=5