初夏小谈：循环队列的基本操作（完整版）

循环队列的入队，出队，队首，队尾等基本操作

其核心思想是让队尾拼接到队首元素上，形成一个环。在实现的时候应当注意标记队尾后一个数据的下标不能大于等于队列容量。由于队列先入先出的原则，我用数组进行存储数据，只需操纵数组下标即可。首先队首，队尾应做一个标记以便操作循环队列的出队列，入队列，其次需要定义循环队列的大小，相应的要记录元素的个数。当然通过队首队尾下标也可以表示，再定义一个数组即可。

在实现循环队列时应注意：

1.充分理解队首，队尾后一个元素下标的意义及其范围，以及在更新时特别注意对++的使用，一不小心会万劫不复。

2.注意入队列/出队列元素时，各个标记的变化是否得当。

OK代码如下：

#include"CirQueue.h"

//创建循环队列
CirQueue* CreateCirQueue(int k)
{
	CirQueue* CQPtr = (CirQueue*)malloc(sizeof(CirQueue));
	CQPtr->capcity = k;//队列容量
	CQPtr->size = 0;//队列元素个数
	CQPtr->ptr = (int*)malloc(sizeof(int)*k);
	CQPtr->front = -1;//代表队首元素下标
	CQPtr->rear = 0;//代表队尾下一个元素的下标
	return CQPtr;
}

//插入元素
void InsertCirQueue(CirQueue* CQPtr, int data)
{
	if (CQPtr->size >= CQPtr->capcity)
	{
		printf("循环队列已满,插入失败！！！\n");
		return;
	}
	if (CQPtr->front == -1)
	{
		CQPtr->front = 0;
	}
	CQPtr->ptr[CQPtr->rear] = data;
	CQPtr->rear = (CQPtr->rear + 1)% CQPtr->capcity;
	CQPtr->size++;
}

//删除元素
void DeleteCirQueue(CirQueue* CQPtr)
{
	if (CQPtr->size == 0)
	{
		return;
	}
	CQPtr->front = ((CQPtr->front + 1)% CQPtr->capcity);
	CQPtr->size--;
}

//返回队首元素
int GetHeadCirQueue(CirQueue* CQPtr)
{
	if (CQPtr->size == 0)
	{
		return -1;
	}
	return CQPtr->ptr[CQPtr->front];
}

//返回队尾元素************************************
int GetWeiCirQueue(CirQueue* CQPtr)
{
	if (CQPtr->size == 0)
	{
		return -1;
	}
	return CQPtr->ptr[(CQPtr->capcity + (CQPtr->rear - 1)) % CQPtr->capcity];
}

//返回当前剩余容量
int GetSurplusCirQueue(CirQueue* CQPtr)
{
	return CQPtr->capcity - CQPtr->size;
}

//打印循环队列
void PrintCirQueue(CirQueue* CQPtr)
{
	if (CQPtr->size == 0)
	{
		printf("空队列\n");
		return;
	}
	int fronts = CQPtr->front;
	if (fronts == CQPtr->rear)
	{
		printf("<-- %d ", CQPtr->ptr[fronts]);
		fronts = (1+fronts) % CQPtr->capcity;
	}
	while (fronts != CQPtr->rear)
	{
		printf("<-- %d ", CQPtr->ptr[fronts]);
		fronts = (1+fronts) % CQPtr->capcity;
	}
	printf("\n");
}

#pragma once

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

//定义循环队列类型
typedef struct
{
	int* ptr;
	int capcity;
	int size;
	int front;
	int rear;
}CirQueue;

//创建循环队列
CirQueue* CreateCirQueue(int k);

//插入元素
void InsertCirQueue(CirQueue* CQPtr, int data);

//删除元素
void DeleteCirQueue(CirQueue* CQPtr);

//返回队首元素
int GetHeadCirQueue(CirQueue* CQPtr);

//返回队尾元素
int GetWeiCirQueue(CirQueue* CQPtr);

//返回当前剩余容量
int GetSurplusCirQueue(CirQueue* CQPtr);

//打印循环队列
void PrintCirQueue(CirQueue* CQPtr);

#include"CirQueue.h"


int main()
{
	CirQueue* CQptr;
	CQptr = CreateCirQueue(6);

	//插入元素
	InsertCirQueue(CQptr, 5);
	//PrintCirQueue(CQptr);
	InsertCirQueue(CQptr, 4);
	InsertCirQueue(CQptr, 3);
	InsertCirQueue(CQptr, 2);
	InsertCirQueue(CQptr, 1);
	PrintCirQueue(CQptr);
	InsertCirQueue(CQptr, 0);
	PrintCirQueue(CQptr);

	//删除队首元素
	DeleteCirQueue(CQptr);
	PrintCirQueue(CQptr);
	//DeleteCirQueue(CQptr);
	//PrintCirQueue(CQptr);

	//插入元素
	InsertCirQueue(CQptr, 5);
	PrintCirQueue(CQptr);

	InsertCirQueue(CQptr, 6);
	PrintCirQueue(CQptr);

	//返回队首元素
	int Head = GetHeadCirQueue(CQptr);
	printf("%d\n", Head);

	//返回队尾元素
	int Heads = GetWeiCirQueue(CQptr);
	printf("%d\n", Heads);

	//剩余容量
	int num = GetSurplusCirQueue(CQptr);
	printf("%d\n", num);
	system("pause");
	return 0;
}

结果显示：

<-- 5 <-- 4 <-- 3 <-- 2 <-- 1
<-- 5 <-- 4 <-- 3 <-- 2 <-- 1 <-- 0
<-- 4 <-- 3 <-- 2 <-- 1 <-- 0
<-- 4 <-- 3 <-- 2 <-- 1 <-- 0 <-- 5
循环队列已满,插入失败！！！
<-- 4 <-- 3 <-- 2 <-- 1 <-- 0 <-- 5
4
5
0
请按任意键继续. . .