循环队列的接口
目录目录
[*]目录
[*]队列的概念
[*]假溢出问题
[*]循环队列的实现
[*]1.以数组为基础实现循环队列
[*]2.以链表为基础实现循环队列
[*]两个栈实现队列
队列的概念
队列（Queue）和栈类似，相同点是都属于线性结构，不同点是栈遵循“后进先出”原则，而队列遵循“先进先出”的原则，也被称为“FIFO”结构，就是“First Input First Output”。
数据结构中的队列的两端都允许操作，只不过要求数据只能从队列的一端插入（入队），从队列的另一端删除（出队），可以把队列理解为一根水管，水管有进水口和出水口。一般把允许数据插入的一端称为队尾（Tail或者Rear），一般把允许删除数据的一端称为队头队首（Head或者Front）。
和栈一样，队列也可以通过数组或者链表来实现，通过数组来实现的队列我们称之为“顺序队列”，通过链表实现的队列称之为“链式队列”
假溢出问题
如果使用数据实现简单的队列，当执行多次入队和出队之后，队列的尾指针 Rear 和头指针 Front 已经到达数组的末尾，即使队列中有许多空闲位置（前面的元素删除后就会有位置），也无法再进行入队操作。这种情况被称为 “假溢出”，也就是队列又是空的又是满的，这看起来是一个自相矛盾的事情却在队列里面出现了，如下图所示：
解决方案：
[*]在学习顺序表（数组）的时候，当顺序表（数组）中删除一个元素，那么这个位置之后的所有元素都需要往前移动一位，所以队列中也是同理，假如我们用数组来实现的话，当元素出队时，我们把所有元素都往前移，不过这样因为每次都需要搬移数据，导致入队的时间复杂度是O(n)
[*]可以把队列设置为循环队列，循环队列也被称为“环形缓冲区”，通过使队列的尾部与头部相连，形成一个闭环，可以使得出队后的空间得到重新利用，从而最大限度地使用数组空间，避免了空间的浪费，在移动数据的时候只需要移一次即可，所以时间复杂度就是O(1)
循环队列的实现
1.以数组为基础实现循环队列
/**
* @file name ： Cirqueue.c
* @brief :该程序以数组为基础实现循环队列元素的初始化、入队、出队、遍历，另外为了提高可移植性，所以循环队列中
* 数据元素的类型为DataType_t，用户可以根据实际情况修改循环队列中元素的类型
* @author :MINDSETT@163.com
* @date :2025/7/5
* @version :1.0
* @note :以数组末尾浪费一个存储空间为代价来换取更简便的代码
* CopyRight (c)2025MINDSETT@163.comAll Right Reserved
*/
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
//指定循环队列中的元素的数据类型，用户可根据需要进行修改
typedef int DataType_t;
//构造一个实现循环队列的各项参数（循环队列首地址+循环队列的容量+队尾下标+队首下标）的结构体
typedef struct Circular_Queue
{
DataType_t *addr; //循环队列首地址
unsigned intsize; //循环队列的容量
int rear; //队尾下标
int front; //队首下标
}Cirqueue_t;
/**
* @name :Cirqueue_Create
* @brief :创建一个循环队列并进行初始化
* @param :None
* @retval:返回栈底地址
* @date :2025/7/5
* @version :1.0
* @note :None
*/
Cirqueue_t *Cirqueue_Create(unsigned int size)
{
//1.利用calloc对循环队列的管理结构体申请一个内存
Cirqueue_t *manager=(Cirqueue_t *)calloc(1,sizeof(Cirqueue_t));
if (NULL == manager){
perror("calloc memory for manager is failed\n");
exit(-1);
}
//2.对循环队列管理结构体的所有元素进行初始化
manager->addr=(DataType_t *)calloc(size,sizeof(DataType_t));
if (NULL == manager->addr){
perror("calloc memory for Stack is failed\n");
exit(-1);
}
manager->size=size;
manager->rear=0;
manager->front=0;
return manager;
}
/**
* @name :Cirqueue_IsFull
* @brief :判断循环队列是否已满
* @param :
* @manager:需要判断的循环队列
* @retval:已满返回true，未满返回false
* @date :2025/7/5
* @version :1.0
* @note :None
*/
bool Cirqueue_IsFull(Cirqueue_t *manager)
{
return ( ( (manager->rear+1)%manager->size )==manager->front )? true : false;
}
/**
* @name :Cirqueue_IsEmpty
* @brief :判断循环队列是否为空
* @param :
* @manager:需要判断的循环队列
* @retval:为空返回true，不为空返回false
* @date :2025/7/5
* @version :1.0
* @note :None
*/
bool Cirqueue_IsEmpty(Cirqueue_t *manager)
{
return (manager->rear==manager->front)? true : false;
}
/**
* @name :Cirqueue_Enqueue
* @brief :入队
* @param :
* @manager:需要操作的循环队列
* @Data:需要入队的元素
* @retval:已满返回true，未满返回false
* @date :2025/7/5
* @version :1.0
* @note :None
*/
bool Cirqueue_Enqueue(Cirqueue_t *manager,DataType_t Data)
{
//判断循环队列是否已满
if ( Cirqueue_IsFull(manager) ){
printf("Circular Queue is Full\n");
return false;
}
//如果循环队列有剩余空间，则把新元素插入循环队列的队尾
manager->addr=Data;
//防止队尾下标越界
manager->rear=(manager->rear+1)%manager->size;
return true;
}
/**
* @name :Cirqueue_Dequeue
* @brief :出队
* @param :
* @manager:需要操作的循环队列
* @retval:成功返回出队的元素
* @date :2025/7/5
* @version :1.0
* @note :None
*/
DataType_t Cirqueue_Dequeue(Cirqueue_t *manager)
{
//判断循环队列是否为空
if ( Cirqueue_IsEmpty(manager) ){
printf("Circular Queue is empty\n");
return false;
}
//定义临时变量存储要出队的元素
DataType_t temp=0;
//队首元素出队，队首下标+1
temp=manager->addr;
//防止队首下标越界
manager->front=(manager->front+1)%manager->size;
return temp;
}
/**
* @name :Cirqueue_Print
* @brief :遍历
* @param :
* @manager:需要操作的循环队列
* @retval:成功返回true，失败返回false
* @date :2025/7/5
* @version :1.0
* @note :None
*/
bool Cirqueue_Print(Cirqueue_t *manager)
{
if (Cirqueue_IsEmpty(manager)) {
printf("Circular Queue is empty\n");
return false;
}
int i = manager->front;
printf("Queue: ");
while (i != manager->rear) {
printf("%d ", manager->addr);
i = (i + 1) % manager->size;
}
printf("\n");
return true;
}2.以链表为基础实现循环队列
/**
* @file name ： CirLnList_Queue.c
* @brief :该程序以链表为基础实现循环队列元素的初始化、入队、出队、遍历，另外为了提高可移植性，所以循环队列中
* 数据元素的类型为DataType_t，用户可以根据实际情况修改循环队列中元素的类型
* @author :MINDSETT@163.com
* @date :2025/7/11
* @version :1.0
* @note :头结点不存储数据，仅用于管理队列
* CopyRight (c)2025MINDSETT@163.comAll Right Reserved
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//指定循环队列中元素的数据类型，用户可根据需要进行修改
typedef int DataType_t;
//构造循环队列的结点，循环队列中所有结点的数据类型应该是相同的（数据域+指针域）
typedef struct CircularLinkedList_Queue
{
DataType_t data; //结点的数据域
struct CircularLinkedList_Queue * next; //结点的指针域
}CirLnList_Queue_t;
/**
* @name :Queue_Create
* @brief :创建一个空循环队列，空循环队列应该有一个头节点，对循环队列进行初始化
* @param :None
* @retval:返回头结点的地址
* @date :2025/7/11
* @version :1.0
* @note :None
*/
CirLnList_Queue_t *Queue_Create(void)
{
//创建一个头结点并对头结点申请内存
CirLnList_Queue_t* Head=(CirLnList_Queue_t*)calloc(1,sizeof(CirLnList_Queue_t));
if (NULL==Head){
perror("calloc memory for Head is failed\n");
exit(-1);
}
//对头结点进行初始化,头结点不存储数据域，指针域指向自身，体现“循环”思想
Head->next=Head;
//将头结点的地址返回
return Head;
}
/**
* @name :Queue_NewNode
* @brief :创建一个新结点，并为新结点申请堆内存以及对新结点的数据域和指针域进行初始化
* @param :
* @data:新结点的数据
* @retval:返回新结点的地址
* @date :2025/7/11
* @version :1.0
* @note :None
*/
CirLnList_Queue_t * Queue_NewNode(DataType_t data)
{
//创建新结点，并未新结点申请堆内存
CirLnList_Queue_t * New=(CirLnList_Queue_t*)calloc(1,sizeof(CirLnList_Queue_t));
if (NULL==New){
perror("calloc memory for NewNode is failed\n");
return NULL;
}
//对新结点的数据域和指针域进行初始化
New->data=data;
New->next=NULL;
return New;
}
/**
* @name :Queue_Enqueue
* @brief :入队
* @param :
* @Head:插入的循环队列
* @data:新结点的数据
* @retval:成功返回true，失败返回false
* @date :2025/7/11
* @version :1.0
* @note :None
*/
bool Queue_Enqueue(CirLnList_Queue_t * Head,DataType_t data)
{
//创建新结点，并对新结点进行初始化
CirLnList_Queue_t* New=Queue_NewNode(data);
if (NULL==New){
perror("Create New node is failed\n");
return false;
}
//判断循环队列是否为空，如果为空，则将新结点直接插入
if (Head==Head->next){
Head->next=New;
New->next=New;//指针域指向自身，体现“循环”思想
return true;
}
//备份首结点的地址
CirLnList_Queue_t * tail=Head->next;
//找到尾结点
while( tail->next != Head->next ){
tail=tail->next;
}
//新结点指向首结点，旧尾结点指向新结点
New->next=tail->next;
tail->next=New;
return true;
}
/**
* @name :Queue_Dequeue
* @brief :出队
* @param :
* @Head:循环队列的头结点
* @retval:成功返回true，失败返回false
* @date :2025/7/11
* @version :1.0
* @note :None
*/
bool Queue_Dequeue(CirLnList_Queue_t* Head)
{
//备份首结点
CirLnList_Queue_t * first=Head->next;
CirLnList_Queue_t * tail=Head->next;
//判断传参错误或循环队列为空
if (NULL==Head || Head==Head->next){
perror("Linked list is empty\n");
return false;
}
//1.只有一个首结点
if (Head->next->next==Head->next){
Head->next=Head;
first->next=NULL;//首结点的指针域指向NULL,从循环队列中断开(避免野指针)
free(first);
return true;
}
//2.循环队列有多个结点
//找到尾结点
while( tail->next!=Head->next ){
tail=tail->next;
}
//尾结点指向首结点的直接后驱
tail->next=first->next;
//将头结点指针域指向首结点的直接后驱
Head->next=first->next;
//旧的首结点的指针域指向NULL,从循环队列中断开(避免野指针)
first->next=NULL;
//释放首结点占用的内存
free(first);
return true;
}
/**
* @name :Queue_Print
* @brief :遍历输出循环队列中各个结点的数据
* @param :
* @Head:需要遍历的循环队列
* @retval:成功返回true，失败返回false
* @date :2025/7/11
* @version :1.0
* @note :None
*/
bool Queue_Print(CirLnList_Queue_t* Head)
{
//判断传参错误或循环队列为空
if (NULL==Head || Head==Head->next){
perror("Current CircularLinkedList is empty\n");
return false;
}
//对循环队列的头节点的地址进行备份
CirLnList_Queue_t *curr=Head;
//循环遍历循环队列
while(curr->next){
curr=curr->next;
printf("Data=%d ",curr->data);
if( curr->next == Head->next){
break;
}
}
return true;
}两个栈实现队列
// 基本思想：利用栈s1和栈s2实现队列，栈的思想是“先进后出”，队列的思想是“先进先出”，可以选择把栈s1作为入队缓存，栈s2作为出队缓存//代码实现：在栈的基础上使用两个栈实现循环队列的入队和出队
/**
* @file name ： Stack_Queue.c
* @brief :该程序以栈为基础实现循环队列元素的初始化、入队、出队、遍历，另外为了提高可移植性，所以循环队列中
* 数据元素的类型为DataType_t，用户可以根据实际情况修改循环队列中元素的类型
* @author :MINDSETT@163.com
* @date :2025/7/5
* @version :1.0
* @note :None
* CopyRight (c)2025MINDSETT@163.comAll Right Reserved
*/
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#define maxSize 10
//指定顺序栈中的元素的数据类型，用户可根据需要进行修改
typedef int DataType_t;
//构造一个实现顺序栈的各项参数（栈底地址+栈容量+栈顶元素的下标）的结构体
typedef struct Sequence_Stack
{
DataType_t *bottom; //栈底地址
unsigned intsize; //栈容量
int top; //栈顶元素的下标
}SeqStack_t;
/**
* @name :SeqStack_Create
* @brief :创建一个顺序栈并进行初始化
* @param :None
* @retval:返回栈底地址
* @date :2025/7/5
* @version :1.0
* @note :None
*/
SeqStack_t *SeqStack_Create(unsigned int size)
{
//1.利用calloc对顺序栈的管理结构体申请一个内存
SeqStack_t *manager=(SeqStack_t *)calloc(1,sizeof(SeqStack_t));
if (NULL == manager){
perror("calloc memory for manager is failed\n");
exit(-1);
}
//2.对顺序栈管理结构体的所有元素进行初始化
manager->bottom=(DataType_t *)calloc(size,sizeof(DataType_t));
if (NULL == manager->bottom){
perror("calloc memory for Stack is failed\n");
exit(-1);
}
manager->size=size;
manager->top=-1;
return manager;
}
/**
* @name :SeqStack_IsFull
* @brief :判断顺序栈是否已满
* @param :
* @manager:需要判断的顺序栈
* @retval:已满返回true，未满返回false
* @date :2025/7/5
* @version :1.0
* @note :None
*/
bool SeqStack_IsFull(SeqStack_t *manager)
{
return (manager->top+1==manager->size)? true : false;
}
/**
* @name :SeqStack_IsEmpty
* @brief :判断顺序栈是否为空
* @param :
* @manager:需要判断的顺序栈
* @retval:为空返回true，不为空返回false
* @date :2025/7/5
* @version :1.0
* @note :None
*/
bool SeqStack_IsEmpty(SeqStack_t *manager)
{
return (-1==manager->top)? true : false;
}
/**
* @name :SeqStack_Push
* @brief :入栈
* @param :
* @manager:需要操作的顺序栈
* @Data:需要压入的元素
* @retval:成功返回true，失败返回false
* @date :2025/7/5
* @version :1.0
* @note :None
*/
bool SeqStack_Push(SeqStack_t *manager,DataType_t Data)
{
//判断顺序栈是否已满
if ( SeqStack_IsFull(manager) ){
printf("Sequence Stack is Full\n");
return false;
}
//如果顺序栈有剩余空间，则把新元素插入顺序栈的栈顶，并更新管理结构体中最后栈顶的元素下标
manager->bottom[++manager->top]=Data;
return true;
}
/**
* @name :SeqStack_Pop
* @brief :出栈
* @param :
* @manager:需要操作的顺序栈
* @out:接收弹出的值
* @retval:成功返回true，失败返回false
* @date :2025/7/5
* @version :1.0
* @note :None
*/
bool SeqStack_Pop(SeqStack_t *manager, DataType_t *out)
{
//判断顺序栈是否为空
if ( SeqStack_IsEmpty(manager) ){
printf("Sequence Stack is empty\n");
return false;
}
//删除一个元素，栈顶元素下标-1
*out=manager->bottom;
return true;
}
/**
* @name :SeqStack_print
* @brief :遍历顺序栈
* @param :
* @manager:需要操作的顺序栈
* @retval:成功返回true，失败返回false
* @date :2025/7/5
* @version :1.0
* @note :None
*/
void SeqStack_print(SeqStack_t *manager)
{
//判断顺序栈是否为空
if ( SeqStack_IsEmpty(manager) ){
printf("Sequence Stack is empty\n");
return;
}
//如果顺序栈不为空，则打印顺序栈的元素
for (int i=0;i<manager->top+1;i++){
printf("Element[%d]=%d\n",i,manager->bottom);
}
printf("\n");
}
/**
* @name :Enqueue
* @brief :入队
* @param :
* @s1:传入栈s1
* @s2:传入栈s2
* @Data：需要入队的数据
* @retval:成功返回true，失败返回false
* @date :2025/7/5
* @version :1.0
* @note :使用栈s1和栈s2模拟队列，具有“先进先出”的思想
*/
bool Enqueue(SeqStack_t *s1,SeqStack_t *s2,DataType_t Data)
{
DataType_t temp;//用于临时存储栈1出栈到栈2的元素的值
//判断栈1是否已满（已满 OR 未满）
if(s1->top+1>=maxSize){
//判断栈2是否为空（空 OR 不空）
if(SeqStack_IsEmpty(s2)){
//栈2为空，一次将栈1中的元素出战到栈2
while(!SeqStack_IsEmpty(s1)){
if(!SeqStack_Pop(s1,&temp)) return false;
if(!SeqStack_Push(s2,temp)) return false;
}
//栈1为空后，将元素插入栈1
if(!SeqStack_Push(s1,Data)) return false;
return true;
}else{
//栈2不为空，无法入队
return false;
}
}else{
// 栈1未满，直接将元素插入栈1
if(!SeqStack_Push(s1,Data)) return false;
}
return true;
}
/**
* @name :Dequeue
* @brief :出队
* @param :
* @s1:传入栈s1
* @s2:传入栈s2
* @out：接收出队的数据
* @retval:成功返回true，失败返回false
* @date :2025/7/5
* @version :1.0
* @note :使用栈s1和栈s2模拟队列，具有“先进先出”的思想
*/
bool Dequeue(SeqStack_t *s1,SeqStack_t *s2,DataType_t *out)
{
DataType_t temp;//用于临时存储栈1出栈到栈2的元素的值
//判断队列是否为空，即栈1和栈2是否都为空（空 OR 不空）
if(SeqStack_IsEmpty(s1) && SeqStack_IsEmpty(s2)){
return false;
}else{
//判断栈2是否为空（空 OR 不空）
if(!SeqStack_IsEmpty(s2)){
//栈2不为空，直接出栈
if(!SeqStack_Pop(s2,out)) return false;
}else{
//栈2为空，将栈1内的元素一次出栈到栈2
while(!SeqStack_IsEmpty(s1)){
if(!SeqStack_Pop(s1,&temp)) return false;
if(!SeqStack_Push(s2,temp)) return false;
}
//栈1为空后，将栈2元素出栈
if(!SeqStack_Pop(s2,out)) return false;
}
}
return true;
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]