循环队列的实现方法及细节

1. 队列定义：
一种可以实现 “先进先出” 的存储结构（类似于排队）
只允许在一端插入元素，在另一端删除元素，不可以混在一起
2. 队列分类：
链式队列：由链表实现的队列，本质是链表
静态队列：由数组实现的队列，本质是数组
3. 循环队列讲解
静态队列为什么必须时循环队列：静态队列必须是循环队列，这是由数组的特性决定的。队列只允许尾部添加元素头部删除元素，如果用数组实现，添加元素时元素向后排列，删除元素时前面的位置就会空出来，时间长了之后会造成大量的空间浪费，所以要使用循环队列，以防止空间浪费
非循环队列，会浪费很多空间
循环队列，不会浪费空间
循环队列需要几个参数来确定：两个，即队列头、尾（实质上就是数组的两个下标）
循环队列各个参数的含义：
循环队列需要两个参数来确定，且这两个参数在不同的情况下由不同的含义
队列初始化时：front和rear值都为零
队列非空时：front代表队列第一个元素，rear代表队列的最后一个有效元素的下一个元素
队列空时：front和rear相等单不一定为零
循环队列入队伪算法讲解：将值存入下标为rear的位置后,rear = (rear+1) %数组长度，而不是 rear+1
循环队列出队伪算法讲解：front = (front + 1) % 数组长度，与入队相同
如何判断循环队列是否为空：若 rear == front 则队列为空
如何判断循环队列是否为满：若 （rear + 1）% 数组长度 == front 则队列已满（因为 rear 指示的是队列最后一个有效元素的下一个元素，所以这样判断队列已满会浪费一个数组位置，但是这已经比非循环队列省了很多空间了。如果要不浪费哪一个元素就需要多加一个参数，这样就会麻烦很多，没有必要）
4. 循环队列实现及细节
#include
#include
#include
typedef struct Queue{
int *pBase; //指向数组的指针
int front; //队列头，数值尾队列第一个有效元素的下标
int rear; //队列尾，数值尾队列最后一个有效元素的下一个元素的下标
}QUEUE,*PQUEUE;
PQUEUE InitQueue(void);
/**操作结果：构造一个空队列Q */
void DestoryQueue(PQUEUE pQ);
/**初始条件：队列已经存在
* 操作结果：队列被销毁
*/
void ClearQueue(PQUEUE pQ);
/**初始条件：队列已经存在
* 操作结果：将队列清空
*/
bool QueueEmpty(PQUEUE pQ);
/**初始条件：队列已经存在
* 操作结果：若队列为空，返回TURE，否则返回FALSE
*/
bool QueueFull(PQUEUE pQ);
/**初始条件：队列已存在
* 操作结果：若队列已满，返回TURE，否则返回FALSE
*/
int QueueHead(PQUEUE pQ,int val);
/**初始条件：队列存在且非空
* 操作结果：返回队列头元素
*/
bool EnQueue(PQUEUE pQ,int val);
/**初始条件：队列已存在
* 操作结果：在队尾插入元素
*/
bool DeQueue(PQUEUE pQ,int *pVal);
/**初始条件：队列存在且非空
* 操作结果：删除队头元素，并返回其值
*/
void QueueTraverse(PQUEUE pQ);
/**初始条件：队列存在且非空
* 操作结果：输出队列元素
*/
int N; //N 用于在各个函数之间传递队列的实际长度
int main()
{
int t;
printf("请输入队列长度："); //这里用 N + 1 是因为输入的队列长度是实际元素的个数，因为循环队列会浪费一个元素，所以令队列的实际长度为 N + 1 方便使用
scanf("%d",&t);
N=t+1;
PQUEUE pQ=InitQueue();
int i,n;
for(i=0;i scanf("%d",&n);
EnQueue(pQ,n);
}
QueueTraverse(pQ);
int val;
DeQueue(pQ,&val);
QueueTraverse(pQ);
printf("出队元素为：%d",val);
}
PQUEUE InitQueue(void) //构造一个空队列
{
PQUEUE pQ=(PQUEUE)malloc(sizeof(QUEUE)); //这里必须用 malloc 函数，否则生成的就是一个局部变量。在这里错了好几次，应当注意！！
pQ->pBase=(int *)malloc(sizeof(int)*N);
pQ->rear=0; //因为这是一个空队列，其中没有任何有效元素，所以 rear 和 front 的值都为零
pQ->front=0;
return pQ;
}
void DestoryQueue(PQUEUE pQ) //销毁队列
{
free(pQ);
}
void ClearQueue(PQUEUE pQ) //清空队列
{
pQ->front=pQ->rear; //清空队列时并不需要将队列里所有元素都重置为零，只需要令 front 与 rear 的值相同即可，以后入队时输入的值就会把原来的值覆盖
}
bool QueueEmpty(PQUEUE pQ) //判断队列是否为空
{
if(pQ->front==pQ->rear){
return true;
}else{
return false;
}
}
bool QueueFull(PQUEUE pQ) //判断队列是否已满
{
int m,n;
m=pQ->rear;
n=pQ->front;
if((m+1)%N==(n)) {
return true;
}else{
return false;
}
}
int QueueHead(PQUEUE pQ,int val) //返回队列头元素
{
val=pQ->pBase[pQ->front];
return val;
}
bool EnQueue(PQUEUE pQ,int val) //在队尾插入元素
{
if(QueueFull(pQ)){
return false;
}else{
pQ->pBase[pQ->rear]=val;
pQ->rear=(pQ->rear+1)%N;
return true;
}
}
bool DeQueue(PQUEUE pQ,int *pVal) //删除队头元素并返回其值
{
if(QueueEmpty(pQ)){
return false;
} else{
*pVal=pQ->pBase[pQ->front]; //这里因为需要函数类型为 bool ，所以无法正常返回 int 类型的值，所以用指针直接修改 val 的值即可
pQ->front=(pQ->front+1)%N;
return true;
}
}
void QueueTraverse(PQUEUE pQ) //遍历输出队列元素
{
int i=pQ->front;
while(i!=pQ->rear){
printf("%d ",pQ->pBase[i]);
i=(i+1)%N;
}
printf("n");
}