《数据结构(C语言版)》循环队列的实现
清华大学计算机系列教材 累计发行超400万册
严蔚敏 吴伟民 编著
数据结构(C语言版)
以下是本人对该紫皮书第三章栈和队列中循环队列的代码实现,即课本3.4.3节队列的顺序表示和实现,本人使用少用一个元素空间的方式区分队满与队空,并处理了非法输入字母等问题。
(貌似专栏把我缩进吃了,懒得加了,另外建议用visual studio编译)
代码实现如下
/*
课本P63页倒数第二段,由于C语言中中仅凭等式Q.front==Q.rear无法判断队列空间是“空”还是“满”
可以采取两种处理方法:
1.另设一个标志位以区别队列是“空”还是“满”
2.少用一个元素空间,约定以队列头指针在队列尾指针的下一位置作为队列成“满”状态的标志
下列代码中采取处理方法2
队空标志:front==rear
队满标志:(rear+1)%MAXQSIZE==front
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXQSIZE 6
typedef int Status;
typedef int QElemType;
typedef struct
{
QElemType* base;
int front;
int rear;
}SqQueue;
Status InitQueue(SqQueue& Q);//队列的初始化
int QueueLength(SqQueue Q);//返回Q的元素个数,即队列的长度
Status EnQueue(SqQueue& Q, QElemType e);//入队
Status DeQueue(SqQueue& Q, QElemType& e);//出队
Status GetHead(SqQueue Q, QElemType& e);//用e返回队头元素,若队空返回ERROR
void Menu()
{
printf("***************************\n");
printf("********0:退出系统********\n");
printf("********1:元素入队********\n");
printf("********2:元素出队********\n");
printf("********3:求队列长********\n");
printf("********4:求队头值********\n");
printf("***************************\n");
}
int main()
{
int option;
int value;
SqQueue MyQueue;
InitQueue(MyQueue);
Menu();
printf("请输入你想使用的功能:");
while (scanf("%d", &option) != EOF)
{
while (getchar() != '\n');
switch (option)
{
case 1:
printf("请输入你想入队的元素:");
while (scanf("%d", &value) != 1)
{
while (getchar() != '\n');
printf("非法输入,请重试\n");
}
if (EnQueue(MyQueue, value))
{
printf("入队成功!\n");
}
else
{
printf("队列的最大长度为%d,队列已满!\n", MAXQSIZE - 1);
}
break;
case 2:
if (DeQueue(MyQueue, value))
{
printf("元素%d出队成功!\n", value);
}
else
{
printf("队空,无元素可出队\n");
}
break;
case 3:
printf("队列长度为%d\n", QueueLength(MyQueue));
break;
case 4:
if (GetHead(MyQueue, value))
{
printf("队头元素为%d\n", value);
}
else
{
printf("队空,无队头元素\n");
}
break;
case 0:
printf("感谢使用!\n");
exit(0);
default:
printf("非法输入,请重试\n");
}
Menu();
printf("请输入你想使用的功能:");
}
return 0;
}
Status InitQueue(SqQueue& Q)//队列的初始化
//构造一个空队列
{
Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
if (!Q.base)
{
exit(OVERFLOW);
}
Q.front = Q.rear = 0;
return OK;
}
int QueueLength(SqQueue Q)//返回Q的元素个数,即队列的长度
{
return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}
Status EnQueue(SqQueue& Q, QElemType e)//入队
//插入元素e为Q的新的队尾元素
{
if ((Q.rear + 1) % MAXQSIZE == Q.front)
{
return ERROR;//队列满
}
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;//队尾指针+1
return OK;
}
Status DeQueue(SqQueue& Q, QElemType& e)//出队
//若队列不空,则删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR
{
if (Q.front == Q.rear)//如果队空
{
return ERROR;
}
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}
Status GetHead(SqQueue Q, QElemType& e)//用e返回队头元素,若队空返回ERROR
{
if (Q.front != Q.rear)
{
e = Q.base[Q.front];//返回对头指针元素,对头指针不变
return OK;
}
return ERROR;
}