循环队列的入队出队-----数据结构与算法笔记

参考书：《数据结构（C语言）》–严蔚敏等编著，清华大学出版社。

和顺序栈相似，在循环队列中除了用一组地址连续的存储单元依次存储元素之外，还需要两个指针front和rear分别指向队头与队尾。并且在初始化中，建立空队列时，使Q.front = Q.rear = 0判空。
如下图指针位置存放：

我们发现，在图中：Q.front头指针始终指向头元素，且Q.front指针上移；反而Q.rear尾指针始终指向下一个队尾入队的位置，并非指向一个元素；但是当这个顺序表满了或者Q.rear不能再向上移动了的时候，插入元素时就会产生越界的严重问题，所以只需要设计一个环状的顺序表，问题就会得到解决，如下：

这样，当Q.rear指针就可以使用Q.front指针使用过的空间，并且，Q.front = Q.rear = 0 可能是判空条件，也可能是判满条件，所以在实际当中，将数组最后一个位置空出，少用最后一个位置，使得队头指针在队尾指针的下一个位置，使得：当 （Q.rear+1）% MAXQSIZE == Q.front时，作为队列判满条件，而将Q.front == Q.rear 作为判空条件。

判满：(Q.rear+1) % MAXQSIZE == Q.front;
判空：Q.front == Q.rear;

判空判满如图所示：

相关代码：

#include "stdio.h"
#include "stdlib.h"
#define OK 		1
#define ERROR 	0
#define TRUE 	1
#define FALSE 	0
#define OVERFLOW -2
#define MAXQSIZE 100

typedef int Status;
typedef char QElemType;
typedef struct {
	QElemType *base;	//初始化动态分配存储空间
	int front;	//队头指针
	int rear;	//队尾指针
} SqQueue;

Status InitQueue(SqQueue &Q);
//构造一个空循环队列Q
Status InitQueue(SqQueue &Q) {
	Q.base = (QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
	if(!Q.base) exit(OVERFLOW);
	Q.front = Q.rear = 0;	//队头尾都指向0号元素
	return OK;
}

Status EnQueue(SqQueue &Q,QElemType e);
//插入元素e作为Q的新的队尾元素，入队
Status EnQueue(SqQueue &Q,QElemType e) {
	if((Q.rear+1)%MAXQSIZE == Q.front) return ERROR;
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear+1)%MAXQSIZE;
	return OK;
}

Status DeQueue(SqQueue &Q,QElemType &e);
//删除Q的队头元素，用e返回其值,出队
Status DeQueue(SqQueue &Q,QElemType &e) {
	if(Q.front == Q.rear) return ERROR;
	e = Q.base[Q.front];
	Q.front = (Q.front+1)%MAXQSIZE;
	return OK;
}

Status QueueLength(SqQueue Q);
//求长度
Status QueueLength(SqQueue Q) {
	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
	//返回当前长度
}

Status QueuePrint(SqQueue &Q);
//打印
Status QueuePrint(SqQueue &Q) {
	int len = QueueLength(Q);
	for(int i=0; i