循环队列（C语言）

循环队列里需要注意的是每次头指针和尾指针的位置，因为是循环队列，所以每次入队，头指针和尾指针都会+1，但是每次出队，只有尾指针-1，当头指针与尾指针相遇的时候，表示这个队列已经是空的了，我们可以利用这个来判空。

头文件函数声明

#define MAX_SIZE 100
typedef int ELEM_TYPE;
typedef struct Queue {
	ELEM_TYPE* base;//接受malloc 申请的空间
	int front;//表头指针
	int rear;//表尾指针
	//int count;
}Queue,*PQueue;
void Init(PQueue pq);
bool Push(PQueue pq,ELEM_TYPE val);
bool Pop(PQueue pq);
bool Top(PQueue pq,ELEM_TYPE* rtval);
bool IsEmpty(PQueue pq);
bool IsFull(PQueue pq);
int Get_length(PQueue pq);
void Clear(PQueue pq);
void Destory(PQueue pq);
void show(PQueue pq);

头文件函数声明的实现 

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"cqueue.h"
void Init(PQueue pq) {
	assert(pq!=NULL);
	pq->base = (ELEM_TYPE*)malloc(MAX_SIZE * sizeof(ELEM_TYPE));
	assert(pq->base != NULL);
	pq->front = 0;
	pq->rear = 0;
}
bool Push(PQueue pq, ELEM_TYPE val) {
	assert(pq != NULL);
	if (IsFull(pq)) {
		return false;
	}
	pq->base[pq->rear] = val;
	pq->rear = (pq->rear + 1) % MAX_SIZE;
	return true;
}
bool Pop(PQueue pq) {
	assert(pq != NULL);
	if (IsEmpty(pq)) {
		return false;
	}
	pq->front=(pq->front+1)%MAX_SIZE;
	return true;
}
bool Top(PQueue pq, ELEM_TYPE* rtval) {
	assert(pq != NULL);
	if (IsEmpty(pq)) {
		return false;
	}
	*rtval = pq->base[pq->front];
	return true;
}
bool IsEmpty(PQueue pq) {
	assert(pq != NULL);
	return pq->front == pq->rear;
}
bool IsFull(PQueue pq) {
	assert(pq != NULL);
	return (pq->rear + 1) % MAX_SIZE == pq->front;
}
int Get_length(PQueue pq) {
	assert(pq != NULL);
	int count= (pq->rear - pq->front + MAX_SIZE) % MAX_SIZE;//前面是防止出现负数，后面是防止正数加多
	return count;
}
void Clear(PQueue pq) {
	assert(pq != NULL);
	pq->front = pq->rear = 0;
}
void Destory(PQueue pq) {
	assert(pq != NULL);
	free(pq->base);
	pq->front = pq->rear = 0;
}
void show(PQueue pq) {
	assert(pq != NULL);
	for (int i = pq->front;i!= pq->rear;i=(i+1)%MAX_SIZE) {
		printf("%5d",pq->base[i]);
	}
	printf("\n");
}

这里我们要注意的点是，每次头指针，尾指针+1为了防止出现越界，我们对其与循环队列的容量取余，防止越界。

测试函数

#include<stdio.h>
#include"cqueue.h"
int main() {
	struct Queue head;
	Init(&head);
	for (int i = 0; i < 20;i++) {
		Push(&head,i+1);
	}
	show(&head);
	printf("front   %d\n",head.front);
	printf("rear   %d\n", head.rear);
	Pop(&head);
	Pop(&head);
	Pop(&head);
	show(&head);
	printf("front   %d\n", head.front);
	printf("rear   %d\n", head.rear);
	ELEM_TYPE temp;
	bool tag=Top(&head,&temp);
	if (tag) {
		printf("temp=   %d\n",temp);
	}
	printf("length=   %d\n", Get_length(&head));
	for (int i = 0; i < 81; i++) {
		Push(&head, i + 1);
	}
	show(&head);
	printf("front   %d\n", head.front);
	printf("rear   %d\n", head.rear);
	printf("length=   %d\n",Get_length(&head));
	Clear(&head);
	Destory(&head);
	show(&head);
	return 0;
}

测试用例