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

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

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

typedef struct queue{
    int *pBase;//内部实现队列的数组，用于储存元素
    int front;//指向队列第一个元素  
    int rear;//指向队列最后一个元素的下一个元素  
    int maxsize;//循环队列的最大存储空间  
}QUEUE,*PQUEUE;

第一，验满 / 验空，这个是循环队列的第一个难点，因为乍一想，循环队列是满或是空好像都是需要满足这个条件即可——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;
    }
}