循环队列的实现

循环队列存储结构

循环队列结构体SqQueue,用来管理循环队列分配的数组内存空间，包含：base是分配的存储空间的基地址，base相当于数组名；头指针front，尾指针rear，front和rear相当于数组的下标。

#define MAX_QSIZE 5	//最大队列长度+1
typedef int ElemType;	//队列元素类型
struct SqQueue{
	ElemType* base;		// 初始化的动态分配存储空间
	int front;		// 头指针，若队列不空，指向队列头元素
	int rear;		// 尾指针，若队列不空，指向队列尾元素的下一个位置
};

注意：
1.当队列为空时，front和rear为0；非空时，尾指针始终指向队列为元素的下一个位置，指向的无效元素，头指针指向队列第一个元素。为了区别满队列和空队列，队列的最大长度为分配空间的大小减一。
2.当队列满时，再入队会失败，元素不会插入，对队列没有影响。
3.不管入队还是出队，front和rear都是向上增加。因为是循环队列，所以需要对长度取模，x=(x+1)%MAX_QSIZE。
4.队列初始化或清空时，front=rear=0；队列为空时，front=rear；队列满时，(rear+1)%MAX_QSIZE=front。

基本操作

1.初始化

分配MAX_QSIZE的存储空间，base指向基地址，相当于数组名；初始化时，front和rear都为0；

void InitQueue(SqQueue& Q) {
	Q.base = (ElemType*)malloc(sizeof(ElemType) * MAX_QSIZE);
	if (!Q.base)	exit(-1);
	Q.front = Q.rear = 0;
}

2.销毁

将base指向的内存空间释放，front和rear为0。

void DestroyQueue(SqQueue& Q) {
	if(Q.base)
		free(Q.base);
	Q.base = NULL;
	Q.front = Q.rear = 0;
}

3.清空

循环队列为空时，就是front=rear=0，不用释放内存。

void ClearQueue(SqQueue& Q) {
	Q.rear = Q.front= 0;
}

4.队空
front=rear，不一定都等于0。

bool QueueEmpty(SqQueue Q) {
	if (Q.front == Q.rear)
		return true;
	else
		return false;
}

5.长度

front和rear的大小不确定。

int QueueLength(SqQueue Q) {
	return (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE;
}

6.队头

队非空时返回队头元素。

bool GetHead(SqQueue Q, ElemType& e) {
	if (Q.front == Q.rear)	return false;	//队空
	e = Q.base[Q.front];
	return true;
}

7.入队

bool EnQueue(SqQueue& Q, ElemType e) {
	if (Q.front == (Q.rear + 1) % MAX_QSIZE)
		return false;
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear + 1) % MAX_QSIZE;
	return true;
}

8.出队

bool DeQueue(SqQueue& Q, ElemType& e) {
	if (Q.front == Q.rear)	return false;
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % MAX_QSIZE;
	return true;
}

9.遍历

从队首遍历到队尾。

void QueueTraverse(SqQueue& Q, void(*vi)(ElemType)) {
	int i = Q.front;
	while (i != Q.rear) {
		vi(Q.base[i]);
		i = (i + 1) % MAX_QSIZE;
	}
	printf("\n");
}

测试函数

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

void visit(ElemType e) {
	printf("%d ", e);
}

int main() {
	ElemType e;
	SqQueue Q;
	InitQueue(Q);
	printf("初始化队列后，队列空否？%u(1:空 0:否)\n", QueueEmpty(Q));
	for (int i = 1; i <= 20; i++)
		EnQueue(Q, i);
	printf("现在队列中的元素为\n");
	QueueTraverse(Q, visit);
	printf("队列长度为%d\n", QueueLength(Q));
	DeQueue(Q, e);
	printf("删除的元素值为%d\n", e);
	DeQueue(Q, e);
	printf("删除的元素值为%d\n", e);
	printf("现在队列中的元素为\n");
	QueueTraverse(Q, visit);
	if (GetHead(Q, e))
		printf("现在队头元素为%d\n", e);
	ClearQueue(Q);
	printf("清空队列后, 队列空否？%u(1:空 0:否)\n", QueueEmpty(Q));
	DestroyQueue(Q);
	printf("销毁队列后,q.base=%u ,q.front=%d ,q.rear=%d\n", Q.base,Q.front,Q.rear);
	return 0;
}

测试结果