队列实现循环队列

队列的基本操作

一、实验目的

1．掌握队列的顺序存储结构。

2．掌握队列先进先出运算原则在解决实际问题中的应用。

3. 掌握自定义数据类型的用法。

二、实验内容

仿照资料中顺序循环队列的例子，设计一个只使用队头指针和计数器的顺序循环队列抽象数据类型。其中操作包括：初始化、入队列、出队列、判断队列是否非空。编写主函数，验证所设计的顺序循环队列的正确性。

以下是队列操作函数的定义：

(1)QueueInitiate(Q)   初始化队列Q

(2)QueueNotEmpty(Q)   队列Q非空否 

(3)QueueAppend(Q,x)   入队列，在队列Q的队尾插入数据元素x。

(4)QueueDelete(Q,d)   出队列，把队列Q的队头元素删除并由参数d带回。

 提示：队尾的位置可由队头指针与计数器进行求解，请思考它们之间的关系，同时还要考虑如何实现循环队列（可借助求模运算）。

头文件

/*仿照资料中顺序循环队列的例子，设计一个只使用队头指针和计数器的顺序循环队列抽象数据类型。
其中操作包括：初始化、入队列、出队列、判断队列是否非空。编写主函数，验证所设计的顺序循环队列的正确性。*/
#include<stdio.h>  
#include<stdlib.h>
#include<malloc.h>
#define DateType char
#define MaxSize 10//循环队列总数 
typedef struct{
	DateType date[MaxSize]; 
	int front;//队头指针 
	int counter;//计数器 
}Queue,*PQueue;


//初始化队列Q 
PQueue QueueInitiate(){
	PQueue Q = (PQueue)malloc(sizeof(Queue));
	Q->counter = 0;
	if(Q){
		Q->counter = 0;
		Q->front = 0;
	}
	return Q;
} 
//队列Q非空否  
int QueueNotEmpty(PQueue Q){
	//空返回1，不空返回0 
	if(Q->counter==0)	return 1;
	else	return 0;
}   
//入队列，在队列Q的队尾插入数据元素x。
void QueueAppend(PQueue Q,DateType x){
	//如果队列不存在，直接返回 
//	if(!Q){
//		return;
//	}
	//x入队列 
	Q->date[(Q->front+Q->counter)%MaxSize] = x;
	Q->counter++;
}
//出队列，把队列Q的队头元素删除并由参数d带回。

void QueueDelete(PQueue Q,DateType *d){
	*d=Q->date[Q->front];
	Q->front=(Q->front+1)%MaxSize;
	Q->counter--; 
}

测试文件

#include<stdio.h>  
#include<stdlib.h>
#include<malloc.h>
#include"3.3.h"
#define DateType char
#define MaxSize 10
void main(){
	int i;
	PQueue myQ = QueueInitiate();
	DateType myC;
	DateType arr[10]={'a','b','c','d','e','f','g','h','i',};
	for(i=0;i<10;i++){
		QueueAppend(myQ,arr[i]);
	}
	printf("如果接下来输出a-i,则正常\n");
	for(i=0;i<10;i++){
		QueueDelete(myQ,&myC);
		printf("%c\t",myC); 
	}
	//下面从队列第10位开始输入，测试循环性 
	for(i=0;i<10;i++){
		QueueAppend(myQ,arr[i]);
	}
	printf("\n如果接下来输出a-i,则正常\n");	
	for(i=0;i<10;i++){
		QueueDelete(myQ,&myC);
		printf("%c\t",myC); 
	}
	//销毁队列
	free(myQ) ;
	myQ=NULL;
	
}