算法与数据结构【四】——C语言实现循环队列

队列是另一种经典数据结构，也是有两种，一是静态队列，即数组实现的循环队列，二是用链表实现的动态队列，今天我写的是循环队列，下面我就详细分析一下循环队列我认为不太好理解的几个点

第零，循环队列的构成，用一个结构体表示的话是这样的：

typedef struct queue{    int *pBase;//内部实现队列的数组，用于储存元素    int front;//指向队列第一个元素      int rear;//指向队列最后一个元素的下一个元素      int maxsize;//循环队列的最大存储空间  }QUEUE,*PQUEUE; 这里借鉴了一下这篇文章数据结构：循环队列（C语言实现）的实现方法。
第一，验满 / 验空，这个是循环队列的第一个难点，因为乍一想，循环队列是满或是空好像都是需要满足这个条件即可——front == rear，这样我们就难以分辨队列到底是满还是空，其实再仔细一想，办法还是有的，而且经典的办法都不止一种，一是立一个flag，当满或空时这个标志位的值有所不同，这样就分出了到底是空队列还是满队列。第二种办法是改变一下这个满的定义，我们让队列的最后一位元素空出来，所以，此时满的条件就改为了（rear+1）%maxsize == front。为空的条件依然是front == rear。
第二，入队 / 出队，因为队列是先进先出的，所以要入队只能从队尾进入，而出队只能从队首出去，所以，理解了这一点就很容易能写出具体的代码。
第三，队列的长度计算，当rear>front的时候，此时队列的长度为rear - front，但是当rear<front时，队列长度分为两段，一段是maxsize-front，另一段是rear+0，把两段相加，就得到了长度为rear-front+maxsize，这样可以得到一个通用的队列计算长度公式：
(rear—front + maxsize) % maxsize  这也可以解释为什么要对maxsize取模，就是为了整合起来队列长度的计算问题。
不多说，下面上代码，代码的命名部分参考了数据结构：循环队列（C语言实现）这篇博文
#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedef struct queue{	int *pBase;      int front;//指向队列第一个元素      int rear;//指向队列最后一个元素的下一个元素      int maxsize;//循环队列的最大存储空间  }QUEUE,*PQUEUE;void CreateQueue(PQUEUE Q,int maxsize);void TraverseQueue(PQUEUE Q);int FullQueue(PQUEUE Q);int EmptyQueue(PQUEUE Q);int Enqueue(PQUEUE Q, int val);int Dequeue(PQUEUE Q, int *val);int main(void){	PQUEUE Q = (PQUEUE)malloc(sizeof(QUEUE));	CreateQueue(Q,6);	Enqueue(Q,25);	Enqueue(Q,22);	Enqueue(Q,22);	Enqueue(Q,22);	Enqueue(Q,23);	TraverseQueue(Q);	return 0;}//创建一个空的循环队列 void CreateQueue(PQUEUE Q,int maxsize){	Q->pBase = (int*)malloc(sizeof(maxsize));	if(Q->pBase == NULL)	{		PRintf("ERROR!");		exit(-1);	}	else	{		Q->maxsize = maxsize;		Q->front = 0;		Q->rear = 0;	}}//遍历打印队列 void TraverseQueue(PQUEUE Q){	int i;	printf("队列中的全部元素为：/n");	for(i=Q->front;i%Q->maxsize<Q->rear;i=(i+1)%Q->maxsize)	{		printf("%d/n",Q->pBase[i]);	}}//判断队列是否已满 int FullQueue(PQUEUE Q){	if(Q->front==(Q->rear+1)%Q->maxsize)//判断循环链表是否满，留一个预留空间不用          return 1;    else        return 0;}//判断队列是否为空 int EmptyQueue(PQUEUE Q){	if(Q->front==Q->rear)//判断是否为空          return 1;    else        return 0;}//元素入队 int Enqueue(PQUEUE Q, int val){	if(FullQueue(Q) == 1)        return 0;    else    {        Q->pBase[Q->rear]=val;        Q->rear=(Q->rear+1)%Q->maxsize;        return 1;    }}//出队 int Dequeue(PQUEUE Q, int *val){	if(FullQueue(Q) == 1)        return 0;    else    {    	*val=Q->pBase[Q->front];     	Q->front=(Q->front+1)%Q->maxsize;    	return *val;    }}