循环队列的建立及基本操作-数据结构-C语言

实验项目名称：队列的建立及操作

一、 实验目的
1．掌握队列存储结构的表示和实现方法。
2．掌握队列的入队和出队等基本操作的算法实现。
二、 实验题
建立顺序循环队列，并在顺序循环队列上实现入队、出队基本操作。
三、 实验过程及结果
基本思路

1. 建立顺序循环队列：
   定义一个结构体，成员有三个：数组、头指针（用来表示数组的下标，用于删除元素，即出队）、尾指针（用来表示数组的下标，用于插入元素，即入队）。
2. 入队：
   需要判断队列是否满了，若不满，则可入队。
3. 出队：
4. 需要判断队列是否为空
5. 思路：
   循环队列的引入：解决队列是假溢出的问题
   建立一个顺序队列，当rear+1=MAXQSIZE时，front有两种情况：
   （1） front=0
   此时是队列真溢出，即队列已满；
   （2） front不等于0
   此时队列是假溢出；
   解决方法：
   引入循环队列，当rear+1=MAXQSIZE时，rear指向数组下标为零的位置，再次利用没有元素的空间，front同理；
   由rear+1变为rear=0的方法：
   取模运算：（rear+1）%MAXQSIZE；
6. 判断循环队列空和满的条件问题：
   解决方案：
   （1） 另设一个标志元素，以区分队空，队满；
   （2） 另设一个变量，记录元素个数；
   （3）少用一个元素空间；
   解决方案（3）的实现：
   
   全部程序代码：

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define MAXQSIZE 100
#define OVERFLOW 0
typedef int QElemType;
typedef int Status;
typedef struct
{
	QElemType *base;//动态分配数组空间 
	int front;//头指针，若队列不为空，指向队列头元素 
	int rear;//尾指针，若队列不为空，指向尾元素的下一个位置 
}SqQueue;
SqQueue Q;

//循环队列的初始化 
Status InitQueue(SqQueue &Q)
{
	Q.base=new QElemType[MAXQSIZE];//分配数组空间  
	/*Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType))*/ 
	if(!Q.base)exit(OVERFLOW);//存储分配失败 
	Q.front=Q.rear=0;
	return OK; 
}

//求队列的长度
int QueueLength(SqQueue Q)
{
	if(!Q.base)return ERROR;
	else
	return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
//入队
Status EnQueue(SqQueue &Q,int n)
{
	QElemType e;
	while(n)
	{
		if((Q.rear+1)%MAXQSIZE==Q.front)return ERROR;//队满
		scanf("%d",&e);
	    Q.base[Q.rear]=e;//新元素加入队尾 
	    Q.rear=(Q.rear+1)%MAXQSIZE;//队尾指针加一 
	    n--;
	}
	return OK;
}
//出队
Status DeQueue(SqQueue &Q,int n)
{
	QElemType e;
	if(n<0||n>QueueLength(Q))return ERROR;//出队元素个数不合理 
	while(n)
	{
		if(Q.rear==Q.front)return ERROR;//队空
	    e=Q.base[Q.front];//将此时头元素的值赋给e
	    printf("The DeQueue element is %d\n",e);
	    Q.front=(Q.front+1)%MAXQSIZE;
	    //头指针的值加一
		/*当头指针（Q.front+1)==MAXQSIZE时，如果直接取模运算，则可指向下标为零的位置
		构成一个循环队列*/  
	    n--;
	}
	
	return OK; 
}
//取队头元素
QElemType GetHead(SqQueue Q)
{
	if(Q.rear!=Q.front)//队列不为空 
	return Q.base[Q.front];//直接返回队头指针所指向的元素的值，队头指针不变 
}
//主函数测试
int main()
{
	QElemType e;
	int x,y; 
	if(InitQueue(Q))
	printf("InitQueue success\n");
	printf("请输入入队的元素个数：\n");
	scanf("%d",&x);
	if(EnQueue(Q,x))
	printf("EnQueue success\n");
	printf("The head Element is %d\n",GetHead(Q));
    printf("The length of Queue element is %d\n",QueueLength(Q));
	printf("请输入出队的元素个数：\n");
	scanf("%d",&y);
	if(DeQueue(Q,y));
	printf("DeQueue success\n");
	return 0;	
 }

实验结果：