/*郭睿玥第四次算法实验作业*/
/*实验原理
循环队列是队列的顺序映像的实现，采用顺序存储结构存储队列，会产生假溢出现象，循环队列
是解决假溢出的很好途径。若队列为空时队头指示器与队尾指示器同时指向某一存储单元，即此时两
个指示器的数值相同，若队列非空，队头指示器指向队头元素下标，队尾指示器指向队尾元素的下一
个位置的下标；
循环队列进行入队操作时，只需直接把值赋给当前队尾指示器所指向的下标，然后队尾指示器向
后移动一个位置即可；出队操作时若需返回队头结点值，先返回当前队头指示器所指向的下标的值，
让队头指示器向后移动一个位置，否则直接移动位置即可；
*/
/*实验环境
CodeBlocks*/
/*实验目的
掌握循环队列的基本操作，循环队列初始化、入队、出队、判断队空、判断队满以及求队列长度操作；
掌握队列在顺序存储结构上的操作实现。
*/
/*实验内容
循环队列的初始化、入队、出队、判断是否为空、求队列长度及队列输出操作的实现；
通过设计统一界面来调用基本操作的实现。
*/
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 5
typedef int Status;// 定义函数返回值类型
typedef int ElemType;// 定义每条数据的结构体类型
typedef struct//结构体
{
int front;//队头指针
int rear;//队尾指针
ElemType* base;//base[]为数据
}sqqueue;
Status initsqqueue(sqqueue*q)//队列的初始化
{
q->base=(ElemType*)malloc(sizeof(ElemType*)*MAXSIZE);//申请空间建立数组
if(!q->base) return 0;//空间申请是否成功
q->front=q->rear=0;//空队列标志
printf("初始化成功\n");
return 1;//初始化成功返回1
}
Status queueempty(sqqueue *q)//判断是否为空
{
if(q->front==q->rear) //判空条件
return 1;
return 0;
}
Status getlength(sqqueue*q)//统计队列长度
{
return (q->rear-q->front+MAXSIZE)%MAXSIZE;//模运算出队列长度并返回
}
Status queueefull(sqqueue*q)//判断是否为满
{
if((q->rear+1)%MAXSIZE==q->front)//如果队满则头指针一定指向尾指针之后的一个结点
return 1;
else return 0;
}
Status enqueue(sqqueue*q,ElemType e)//入队操作
{
if(queueefull(q)) //队满则无法入队
return 0;
q->base[q->rear]=e;//新元素入队
q->rear=(q->rear+1)%MAXSIZE;//尾指针移动
return 1;
}
Status dequeue(sqqueue*q) //出队操作
{
ElemType e;
e=q->base[q->front];
q->front=(q->front+1)%MAXSIZE;//尾指针移动
return e;//返回出队的元素
}
void traverse(sqqueue*l)//输出队列
{
sqqueue *p;/*建立一个新队列与要输出的队列一致*/
p=l;
for(;p->front!=p->rear;)//直到新队列成为空队列，每次输出都是新队列的头元素后使新队列出队
{
printf("该元素是%d，它位于队列中的第%d个单元\n",p->base[p->front],p->front+1);//输出新队列头元素
dequeue(p);//对新队列出队
}
return 0;
}
int main()
{
int choice;
sqqueue QQ;
do {/*显示操作界面*/
printf("1. 初始化 \n");
printf("2. 入队； \n");
printf("3. 出队； \n");
printf("4. 求队列长度； \n");
printf("5. 队列判空； \n");
printf("6. 队列判满； \n");
printf("7. 输出队列； \n");
printf("0. 退出。 \n");
printf("\n");
printf("请选择你要操作的选项:");
scanf("%d", &choice);//输入需要进行的选项
printf("\n");
switch (choice) {
case 1:{
initsqqueue(&QQ);//队列的初始化
break;
}
case 2:{//入队操作
ElemType i;
printf("*请输入你要入队的数据 *\n");
scanf("%d",&i);
if(enqueue(&QQ,i))
printf("入队成功\n");
else printf("入队失败\n");
break;
}
case 3:{//出队操作
if(queueempty(&QQ)) {
printf("空队,无法出队\n");//空队列无法出队
break;
}
if(dequeue(&QQ))printf("出队成功\n");//出队操作
break;
}
case 4:{
printf("该队列的长度是%d\n",getlength(&QQ));//求队列长度并输出
break;
}
case 5:{
if (queueempty(&QQ)) printf("空栈\n");//判空
else printf("不是空栈\n");
break;
}
case 6:{
if (queueefull(&QQ)) printf("满栈\n");//判满
else printf("不是满栈\n");
break;
}
case 7:{
traverse(&QQ);//输出队列
break;
}
case 0:{
printf("\n退出系统成功！请按任意键结束！\n");//退出程序
exit(0);
}
break;
}
} while (choice);//只要选择不为需要进行的功能不为0则该程序可以一直进行下去
return 0;
}
/*
实验结果
操作界面如下
1. 初始化
2. 入队；
3. 出队；
4. 求队列长度；
5. 队列判空；
6. 队列判满；
7. 输出队列；
0. 退出。
郭睿玥 算法与数据结构第四次作业
1. 初始化
2. 入队；
3. 出队；
4. 求队列长度；
5. 队列判空；
6. 队列判满；
7. 输出队列；
0. 退出。
请选择你要操作的选项:1
初始化成功
1. 初始化
2. 入队；
3. 出队；
4. 求队列长度；
5. 队列判空；
6. 队列判满；
7. 输出队列；
0. 退出。
请选择你要操作的选项:2
*请输入你要入队的数据 *
6
入队成功
1. 初始化
2. 入队；
3. 出队；
4. 求队列长度；
5. 队列判空；
6. 队列判满；
7. 输出队列；
0. 退出。
请选择你要操作的选项:2
*请输入你要入队的数据 *
8
入队成功
1. 初始化
2. 入队；
3. 出队；
4. 求队列长度；
5. 队列判空；
6. 队列判满；
7. 输出队列；
0. 退出。
请选择你要操作的选项:2
*请输入你要入队的数据 *
4
入队成功
1. 初始化
2. 入队；
3. 出队；
4. 求队列长度；
5. 队列判空；
6. 队列判满；
7. 输出队列；
0. 退出。
请选择你要操作的选项:2
*请输入你要入队的数据 *
9
入队成功
1. 初始化
2. 入队；
3. 出队；
4. 求队列长度；
5. 队列判空；
6. 队列判满；
7. 输出队列；
0. 退出。
请选择你要操作的选项:2
*请输入你要入队的数据 *
2
入队失败
1. 初始化
2. 入队；
3. 出队；
4. 求队列长度；
5. 队列判空；
6. 队列判满；
7. 输出队列；
0. 退出。
请选择你要操作的选项:3
出队成功
1. 初始化
2. 入队；
3. 出队；
4. 求队列长度；
5. 队列判空；
6. 队列判满；
7. 输出队列；
0. 退出。
请选择你要操作的选项:4
该队列的长度是3
1. 初始化
2. 入队；
3. 出队；
4. 求队列长度；
5. 队列判空；
6. 队列判满；
7. 输出队列；
0. 退出。
请选择你要操作的选项:5
不是空栈
1. 初始化
2. 入队；
3. 出队；
4. 求队列长度；
5. 队列判空；
6. 队列判满；
7. 输出队列；
0. 退出。
请选择你要操作的选项:6
不是满栈
1. 初始化
2. 入队；
3. 出队；
4. 求队列长度；
5. 队列判空；
6. 队列判满；
7. 输出队列；
0. 退出。
请选择你要操作的选项:7
该元素是8，它位于队列中的第2个单元
该元素是4，它位于队列中的第3个单元
该元素是9，它位于队列中的第4个单元
1. 初始化
2. 入队；
3. 出队；
4. 求队列长度；
5. 队列判空；
6. 队列判满；
7. 输出队列；
0. 退出。
请选择你要操作的选项:0
退出系统成功！
*/