顺序循环队列的基本概念

1、队列

        定义：队列是一种线性数据结构，它遵循先进先出的原则。就像排队买东西一样，先到的人先接受服务。在队列中，元素从队尾进入队列，从队头离开队列。

2、缺点

        上面描述的队列有如下缺点：

        （1）空间利用率低

        当队列执行出队操作后，前面的空间就空出来了，空间难以再被利用。以数组实现普通队列为例，假设有一个大小为5的数组arr，依次入队元素1、2、3。出队元素1后，数组的零号下标位置就会空出，如果再进行入队操作，只能在3号下标位置入队，不能利用前面空出的位置。

        （2）容易出现假溢出的情况

        以数组实现普通队列为例，队列在进行入队操作时，当队尾指针到达数组末尾，即使数组前面还有空闲空间，也会认为队列已满，出现假溢出的情况。

3、循环队列

        循环队列通过循环存储的方式解决了上述缺点，只要队列整体未满，就可以继续进行入队操作。还是以数组实现循环队列为例，当有元素入队时，队尾指针加一，当存储到数组末尾位置时候，队尾指针的下一个位置是数组的零号下标。当有元素出队时，队头指针加一，当队头指针移动到数组末尾位置时，队头指针的下一个位置同样也是数组的零号下标。这样进行存取数据时，可以避免浪费前面空出位置的情况。

4、如何解决顺序循环队列的判空和判满问题

        在利用数组实现循环队列的过程中，可以发现队列为空和队列为满时，队列的队头指针和队尾指针都会相等，那么就很难判断相等时究竟队列为空还是队列为满。

        为了解决这一问题，这里提出两种解决方法：

        （1）额外增加一个变量来记录队列中元素的个数，当元素个数等于队列的最大容量时，队列为满，元素个数为零时，队列为空。

        （2）牺牲一个存储单元来区分队满和队空。判满条件是（rear+1）%MAX == front，其中MAX是队列的最大容量。判空条件是rear == front，即头尾指针相等。

顺序循环队列的代码实现

准备工作

在用代码来实现顺序循环队列时，作如下约定：

约定一：数组的大小为LEN时，最多只存LEN-1个元素（为了方便判空和判满）

约定二：数组的LEN-1号下标的下一个位置为0号下标位置（实现循环存储）

在定义头尾指针时，有如下规定：

规定一：头指针front指向队头元素的前一个位置，尾指针rear指向队尾元素所在位置。

规定二：头指针front指向队头元素的位置，尾指针rear指向队尾元素的下一个位置。

        这两个约定在代码实现中都要遵守，两个规定在代码实现中，选择其中一个遵守，下面的代码实现中，选择规定二。

定义结构体 

typedef char Type; //方便后续修改维护
#define LEN 10 //最多存储LEN-1个元素typedef struct{Type data[LEN]; //队列的存储空间int front; //队头指针：队头的下标int rear;  //队尾指针：队尾的下标+1
}queue;        //顺序循环队列

功能函数部分 

创建：

        为队列结构体动态申请空间并检查是否申请成功，初始情况下，队头在零号位置，队尾在负一号位置，则头尾指针都为零。最后返回结构体指针。

queue *create_queue()
{queue *q = (queue *)malloc(sizeof(queue));if(NULL == q){perror("malloc queue error");return NULL;}q->front = 0;q->rear = 0;return q;
}

判空： 

        当两个指针相等时，队列为空。这里并不是两个指针相等且都为零，因为当进行出队操作后，头指针会向后移动，所以队列为空时，二者可能在中间位置相等。队列为空函数返回0，队列非空函数返回1，出错情况下返回-1。

int empty_queue(queue *q)
{if(NULL == q){puts("queue is NULL");return -1;}if(q->front == q->rear){puts("queue is empty");return 0;}elsereturn 1;
}

判满： 

        当队列为满的时，满足（rear+1）%LEN = front，加取余的原因是，当队尾在len-2号下标且队列为满时，队头在0号下标，rear = 队尾+1 = len – 1，此时rear + 1 = len，取余才能与front相等。

int full_queue(queue *q)
{if(NULL == q){puts("queue is NULL");return -1;}if((q->rear+1)%LEN == q->front){puts("queue is full");return 0;}elsereturn 1;
}

入队：

        当队列未满才能进行入队操作，尾指针当前指向队尾的下一个位置，在尾指针位置插入，然后将尾指针后移，因为后移操作可能会移动到LEN-1号下标位置，所以要进行取余操作。

void enter_queue(queue *q,Type data)
{if(full_queue(q) == 1){q->data[q->rear] = data;q->rear = (q->rear+1)%LEN;}
}

出队：

        当队列非空时才能进行出队操作，头指针当前指向的就是队头数据，保存该数据的值，然后更新头指针指向下一个位置，同样的，后移操作可能会移动到LEN-1号下标，所以也要进行取余操作。最后返回保存的值。

Type delete_queue(queue *q)
{if(empty_queue(q) == 1){Type temp = q->data[q->front];q->front = (q->front+1)%LEN;return temp;}
}

初始化：

        头尾指针同时赋值为零，回到最初的创建状态。

void init_queue(queue *q)
{if(NULL == q){puts("queue is NULL");return;}q->rear = q->front = 0;
}

回收： 

        将结构体free掉，要注意的是，将主函数中的指针指向NULL，防止野指针的出现，所以此处应该传入二级指针。

void free_queue(queue **q)
{if(NULL == q){puts("queue is NULL");return;}free(*q);*q = NULL;
}