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

一、循环队列

参考书：《数据结构（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<len; i++) {
		if(Q.front != Q.rear-1)
			printf("%c,",Q.base[Q.front]);	//从队头开始打印
		else
			printf("%c",Q.base[Q.front]);
		Q.front = (Q.front + 1) % MAXQSIZE;	//Q.front指针向队尾移
	}
}

int  main(void) {
	SqQueue Q;
	InitQueue(Q);
	QElemType ch;
	char e;
	printf("请输入入队元素(可分段输入(输入最后一段Enter后按Ctrl+Z))：\n");
	while((ch=getchar()) != EOF) {
		if(ch == '\n')
			continue;
		else
			EnQueue(Q,ch);
	}
	DeQueue(Q,e);
	printf("整个队列队头元素为：%c\n",e);
	printf("剩余队列元素依次为：");
	QueuePrint(Q);

	return 0;
}