[C++知识库]C语言 数据结构循环队列的基本操作（附输入样例和讲解）

代码参照了严蔚敏、吴伟民编写的数据结构（C语言版）。实现了书中列出的线性表所有操作。
所有代码采用C语言编写。讲解请查看注释。

• 注1：书中很多函数采用了引用传值，如InitQueue(SqQueue &Q)。但C语言并不支持引用传值，因此统一改为地址传值，即InitQueue(SqQueue *Q))。

头文件及宏定义

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAXQSIZE 100
#define OK 1
#define False 0
#define True 1
#define Error 0

typedef定义数据类型和结构体

typedef int QElemType;
typedef int Status;

typedef struct{
	QElemType *base;//初始化的动态分配存储空间 
	int front;//头指针，若队列不空，则指向队列头元素 
	int rear;//尾指针，若队列不空，则指向队列尾元素的下一个位置 
}SqQueue;

InitQueue（创建）

Status InitQueue(SqQueue *Q){
	Q->base=(QElemType *)malloc(MAXQSIZE * sizeof(QElemType));//为整个队列分配内存 
	if(!Q->base)
	exit(OVERFLOW);
	Q->front=Q->rear=0;
	return OK;
}

DestroyQueue（销毁）

Status DestroyQueue(SqQueue *Q){
	Q->front=Q->rear=0;
	if(Q->base){
		free(Q->base);
	}
	Q->base=NULL;
	return OK;
} 

ClearQueue（清空）

Status ClearQueue(SqQueue *Q){
	Q->front=Q->rear=0;
}

QueueEmpty（//判断队列是否为空）

Status QueueEmpty(SqQueue Q){
	if(Q.rear==Q.front)
	return True;
	else
	return False;
}

QueueLength（获得队列的长度）

int QueueLength(SqQueue Q){
	return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

GetHead（获得队头元素）

Status GetHead(SqQueue Q,QElemType *e){
	if(Q.front==Q.rear)
	return Error;
	*e=Q.base[Q.front];
	return OK; 
}

EnQueue（ 队尾插入）

Status EnQueue(SqQueue *Q,QElemType e){//插入e为Q的新的队尾元素 
	if(Q->front==(Q->rear+1)%MAXQSIZE)
	return Error;
	Q->base[Q->rear]=e;
	Q->rear=(Q->rear+1)%MAXQSIZE;
	return OK;
}

DeQueue（队头删除）

Status DeQueue(SqQueue *Q,QElemType *e){//若队列不空，删除Q的队头元素并用e返回 
	if(Q->front==Q->rear)
	return Error;
	*e=Q->base[Q->front];
	Q->front=(Q->front+1)%MAXQSIZE;
	return OK;	
}

QueueTraverse（遍历）

首先需要实现Visit()

Status visit(SqQueue Q){
	while(Q.front%MAXQSIZE!=Q.rear){
		printf("%d\n",Q.base[Q.front]);
		Q.front++;
	}
}

Status QueueTraverse(SqQueue Q,Status visit()){
	visit(Q);
	return OK; 
}

输入样例

很多函数被我注释掉了，需要使用的话自行取消注释。

int main(void){
	SqQueue Q;
	InitQueue(&Q);
	int elem1=1,elem2=2,elem3=3;
	EnQueue(&Q,elem1);
	EnQueue(&Q,elem2);
	EnQueue(&Q,elem3);
	//QueueEmpty(Q);
	//QueueLength(Q);
	//int elem4=0,elem5=0;
	//DeQueue(&Q,&elem4);
	//GetHead(Q,&elem5);
	QueueTraverse(Q,visit);
	DestroyQueue(&Q);
}

输出结果