目录
前言
1.循环队列的定义
2.循环队列的结构
3.循环队列的操作
3.1定义循环队列
3.2初始化
3.3入队
3.4出队
3.5遍历，求表长
3.6清空销毁
4.完整代码
前言
日期：2023.7.25
书籍：2024年数据结构考研复习指导（王道考研系列）
内容：实现顺序队列的基本实现，主要功能如下：
1.循环队列的数据结构
2.入队
3.出队
4.遍历
5.求队长6.清空，销毁
1.循环队列的定义
顺序队列在使用过程中容易出现虚假的满状态， 为了解决这个问题，就产生了一个较巧妙的方法，将顺序队列臆造为一个环状的空间，称之为循环队列。
循环队列中指针和队列元素之间的关系不变，我们只需要利用模运算就可以很容易实现指针的循环移动。但是循环队列中存在一个问题，在循环队列中只凭头指针front等于尾指针rear无法判别队列空间是“空”还是“满”，可有两种处理方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置(指环状的下一位置)上”作为队列呈“满”状态的标志。此处使用方法二来解决这个问题。
2. 循环队列的结构
3.循环队列的操作
3.1定义循环队列
#define MaxSize 50
typedef int ElemType;
typedef struct Queue{
ElemType data[MaxSize]; //指向队列的存储空间
int front; //指向队头
int rear; //指向队尾
}Queue;3.2初始化
//1.初始化
void InitQueue(Queue *Q){
Q->front = Q->rear = 0;
}
3.3入队
//入队操作
bool EnQueue(Queue *Q, ElemType x){
//判断循环队列是否已满
if(((Q->rear+1)%MaxSize) == Q->front)
return false;
//如果还有存储空间，将数据入队
Q->data[Q->rear] = x;
Q->rear = (Q->rear+1)%MaxSize;
return true;
}3.4出队
//3.出栈
//出队
bool DeQueue(Queue *Q,ElemType *x){
//判断队列中的元素是否为空
if(Q->front == Q->rear)
return false;
//如果队列中的元素不为空，进行出队操作
*x=Q->data[Q->front];
Q->front = (Q->front+1)%MaxSize;
return true;
}3.5遍历，求表长
//4.遍历队列
//打印顺序队列中的元素
bool ShowQueue(Queue *Q){
//遍历队头到队尾中的每个元素，并将其打印输出
for(int i=Q->front; i<Q->rear; ){
printf("%d ",Q->data[i]);
i = (i+1)%MaxSize;
}
printf("\n");
return true;
}
//5.求队长
//获取队列元素个数
int Length(Queue *Q){
//将尾指针位置减去头指针的位置就是队列中元素的个数
//计算尾指针位置与头指针位置的差距
int len= Q->rear - Q->front;
//如果为正数，那么len就是队列的长度；如果为负数，那么MAXSIZE+len才是队列的长度
len = (len>0) ? len : MaxSize+len;
return len;
}
3.6清空销毁
//6.清空，销毁队列
//清空队列
bool ClearQueue(Queue *Q){
//将队头指针和队尾指针都重置为0
Q->front = Q->rear = 0;
return true;
}
//销毁队列
void DestroyQueue(Queue *Q){
//释放队列的存储空间
free(Q);
//将队列空间的位置指针置空
Q = NULL;
}4.完整代码
//循环队列
#include <stdio.h>
#include <stdlib.h>
#define bool char
#define true 1
#define false 0
#define MaxSize 50
typedef int ElemType;
typedef struct Queue{
ElemType data[MaxSize]; //指向队列的存储空间
int front; //指向队头
int rear; //指向队尾
}Queue;
//1.初始化
void InitQueue(Queue *Q){
Q->front = Q->rear = 0;
}
//2.入队
//入队操作
bool EnQueue(Queue *Q, ElemType x){
//判断循环队列是否已满
if(((Q->rear+1)%MaxSize) == Q->front)
return false;
//如果还有存储空间，将数据入队
Q->data[Q->rear] = x;
Q->rear = (Q->rear+1)%MaxSize;
return true;
}
//3.出栈
//出队
bool DeQueue(Queue *Q,ElemType *x){
//判断队列中的元素是否为空
if(Q->front == Q->rear)
return false;
//如果队列中的元素不为空，进行出队操作
*x=Q->data[Q->front];
Q->front = (Q->front+1)%MaxSize;
return true;
}
//4.遍历队列
//打印顺序队列中的元素
bool ShowQueue(Queue *Q){
//遍历队头到队尾中的每个元素，并将其打印输出
for(int i=Q->front; i<Q->rear; ){
printf("%d ",Q->data[i]);
i = (i+1)%MaxSize;
}
printf("\n");
return true;
}
//5.求队长
//获取队列元素个数
int Length(Queue *Q){
//将尾指针位置减去头指针的位置就是队列中元素的个数
//计算尾指针位置与头指针位置的差距
int len= Q->rear - Q->front;
//如果为正数，那么len就是队列的长度；如果为负数，那么MAXSIZE+len才是队列的长度
len = (len>0) ? len : MaxSize+len;
return len;
}
//6.清空，销毁队列
//清空队列
bool ClearQueue(Queue *Q){
//将队头指针和队尾指针都重置为0
Q->front = Q->rear = 0;
return true;
}
//销毁队列
void DestroyQueue(Queue *Q){
//释放队列的存储空间
free(Q);
//将队列空间的位置指针置空
Q = NULL;
}
int main(){
Queue Q;
InitQueue(&Q);
for(int i=1; i<=15; ++i){
EnQueue(&Q, i);
}
ShowQueue(&Q);
int x;
DeQueue(&Q,&x);
printf("%d\n",x);
EnQueue(&Q,100);
ShowQueue(&Q);
printf("%d\n",Length(&Q));
}
文章来源：https://www.toymoban.com/news/detail-606118.html
文章来源地址https://www.toymoban.com/news/detail-606118.html
到了这里，关于王道考研数据结构--4.2循环队列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
