目录
一.循环队列简单介绍
循环队列
一般
是一种
静态的线性数据结构
,其中的
数据符合先进先出的原则
.
循环队列的
容器首地址
和
容器尾地址
通过特定操作(比如
指针链接,数组下标取余
等方式
)相连通,从而
实现了容器空间的重复利用
(
在一个
非循环静态队列
里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间
)
二.用静态数组实现循环队列
维护队列的结构体:
typedef struct { int * arry; //指向堆区数组的指针 int head; //队头指针 int tail; //队尾指针(指向队尾数据的下一个位置)(不指向有效数据) int capacity;//静态队列的容量 } MyCircularQueue;
1.数组循环队列结构设计
我们假定
静态数组的容量为k(
可存储k个数据
)
：
根据
队列的基本数据结构
:有
两个指针
用于
维护数组中的有效数据空间
,分别为head指针和tail指针,head指针用于指向
队头数据
,tail用于
指向队尾数据的下一个位置
(即tail指针不指向有效数据)
如图所示,
head指针和tail指针之间
就是
有效数据的内存空间
通过
head指针和tail指针的关系
来实现队列的判满(
判断队列空间是否已被占满
)与判空(
判断队列是否为空队列
)；为了达到这个目的,我们需要将
静态数组的容量大小
设置为k+1(即多设置一个元素空间)
队列的判空条件: tail == head;
队列的判满条件: (tail+1)%(k+1) == head;
另外一种情形:
由此我们可以先设计出
队列的判满和判空接口
：
bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判断队列是否为空 { assert(obj); return (obj->tail == obj->head); } bool myCircularQueueIsFull(MyCircularQueue* obj) //判断队列是否为满 { assert(obj); return ((obj->tail+1)%(obj->capacity +1) == obj->head); }
2.数组循环队列的堆区内存申请接口
在
堆区上
创建MyCircularQueue结构体,同时为队列申请一个
空间大小
为(k+1)*sizeof(DataType)字节的数组：
MyCircularQueue* myCircularQueueCreate(int k) //k个容量大小的循环队列的初始化接口 { MyCircularQueue * tem = (MyCircularQueue *)malloc(sizeof(MyCircularQueue)); //开辟维护循环队列的结构体 if(NULL == tem) { perror("malloc failed"); exit(-1); } tem->arry = NULL; tem->capacity = k; //队列的数据容量为k tem->arry = (int*)malloc((k+1)*sizeof(int)); //开辟堆区数组 if(NULL == tem->arry) { perror("malloc failed"); exit(-1); } //将head,tail下标初始化为0 tem->head = 0; tem->tail = 0; return tem; }
3.数据出队和入队的接口实现
数据出队和入队的图解:
根据图解我们可以设计出数据入队和出队的接口:
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //数据入队接口 { assert(obj); if(myCircularQueueIsFull(obj)) { return false; } //确保队列没满 obj->arry[obj->tail]=value; obj->tail = (obj->tail + 1)%(obj->capacity +1); return true; }bool myCircularQueueDeQueue(MyCircularQueue* obj) //数据出队接口 { assert(obj); if(myCircularQueueIsEmpty(obj)) { return false; } //确保队列不为空 obj->head = (obj->head +1)%(obj->capacity +1); return true; }
4.其他操作接口
返回队头数据的接口:
int myCircularQueueFront(MyCircularQueue* obj) //返回队头数据的接口 { assert(obj); if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->arry[obj->head]; }
返回队尾数据的接口:
int myCircularQueueRear(MyCircularQueue* obj) //返回队尾数据的接口 { assert(obj); if(myCircularQueueIsEmpty(obj)) { return -1; } int labelret = ((obj->tail-1)>=0)? obj->tail-1 : obj->capacity; //注意tail如果指向数组首地址,则尾数据位于数组最后一个位置 return obj->arry[labelret]; }
队列的销毁接口:
void myCircularQueueFree(MyCircularQueue* obj) //销毁队列的接口 { assert(obj); free(obj->arry); obj->arry = NULL; free(obj); obj = NULL; }
5.数组循环队列的实现代码总览
数组循环队列总体代码:
typedef struct { int * arry; //指向堆区数组的指针 int head; //队头指针 int tail; //队尾指针(指向队尾数据的下一个位置)(不指向有效数据) int capacity;//静态队列容量 } MyCircularQueue; bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueIsFull(MyCircularQueue* obj); //顺序编译注意:先被使用而后被定义的函数要记得进行声明 MyCircularQueue* myCircularQueueCreate(int k) //循环队列初始化接口 { MyCircularQueue * tem = (MyCircularQueue *)malloc(sizeof(MyCircularQueue)); //开辟维护循环队列的结构体 if(NULL == tem) { perror("malloc failed"); exit(-1); } tem->arry = NULL; tem->capacity = k; //队列的数据容量为k tem->arry = (int*)malloc((k+1)*sizeof(int)); //开辟堆区数组 if(NULL == tem->arry) { perror("malloc failed"); exit(-1); } tem->head = 0; tem->tail = 0; return tem; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //数据入队接口 { assert(obj); if(myCircularQueueIsFull(obj)) { return false; } //确保队列没满 obj->arry[obj->tail]=value; obj->tail = (obj->tail + 1)%(obj->capacity +1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) //数据出队接口 { assert(obj); if(myCircularQueueIsEmpty(obj)) { return false; } //确保队列不为空 obj->head = (obj->head +1)%(obj->capacity +1); return true; } int myCircularQueueFront(MyCircularQueue* obj) //返回队头数据的接口 { assert(obj); if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->arry[obj->head]; } int myCircularQueueRear(MyCircularQueue* obj) //返回队尾数据的接口 { assert(obj); if(myCircularQueueIsEmpty(obj)) { return -1; } int labelret = ((obj->tail-1)>=0)? obj->tail-1 : obj->capacity; //注意tail如果指向数组首地址,则尾数据位于数组最后一个位置 return obj->arry[labelret]; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判断队列是否为空 { assert(obj); return (obj->tail == obj->head); } bool myCircularQueueIsFull(MyCircularQueue* obj) //判断队列是否为满 { assert(obj); return ((obj->tail+1)%(obj->capacity +1) == obj->head); } void myCircularQueueFree(MyCircularQueue* obj) //销毁队列的接口 { assert(obj); free(obj->arry); obj->arry = NULL; free(obj); obj = NULL; }
力扣题解测试:
三.静态单向循环链表实现循环队列
链表节点结构体定义:
typedef struct listnode { int data; struct listnode * next; }ListNode;
维护链表循环队列的结构体:
typedef struct { int capacity; //记录队列容量大小 ListNode * head; //指向队头节点 ListNode * tail; //指向队尾节点 } MyCircularQueue;
1.链表循环队列的结构设计
静态单向循环链表的
容量大小为k
:
与数组循环队列类似,我们同样需要
开辟一个节点个数为k+1的静态循环链表
链表循环队列的总体结构图示:
另外一种队列判满的情形:
链表循环队列的判满条件(判断队列空间是否被占满的关系式):tail->next == head;
链表循环队列的判空条件(判断队列是否为空队列的关系式): tail == head;
链表循环队列的判满和判空的接口:
bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判断队列是否为空 { assert(obj); return(obj->head == obj->tail); } bool myCircularQueueIsFull(MyCircularQueue* obj) //判断队列是否为满 { assert(obj); return (obj->tail->next == obj->head); }
2.创建静态单向循环链表的接口
实现一个接口,创建一个
维护链表循环队列的结构体
同时
创建容量大小为k+1的静态单向循环链表:
MyCircularQueue* myCircularQueueCreate(int k) //循环队列初始化接口 { int NodeNum =k+1; //创建k+1个链表节点 MyCircularQueue* object = (MyCircularQueue *)malloc(sizeof(MyCircularQueue)); assert(object); //申请维护循环队列的结构体 object->capacity = k; ListNode * preNode = NULL; //用于记录前一个链接节点的地址 while(NodeNum) { if(NodeNum == k+1) { ListNode * tem = (ListNode *)malloc(sizeof(ListNode)); assert(tem); preNode = tem; object->tail = object->head=tem; //让tail和head指向同一个初始节点 } else { ListNode * tem = (ListNode *)malloc(sizeof(ListNode)); assert(tem); preNode->next = tem; //链接链表节点 preNode = tem; } NodeNum--; } preNode->next = object->head; //将表尾与表头相接 return object; }
3.数据的出队和入队接口
数据出入队图解:
根据图解实现数据出入队接口:
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)//数据入队接口(从队尾入队) { assert(obj); if(!obj || myCircularQueueIsFull(obj)) //确定队列没满 { return false; } obj->tail->data = value; //数据入队 obj->tail = obj->tail->next; return true; }bool myCircularQueueDeQueue(MyCircularQueue* obj) //数据出队接口 { assert(obj); if(!obj || myCircularQueueIsEmpty(obj)) { return false; } //数据出队 obj->head = obj->head->next; return true; }
4.其他队列操作接口
返回队头数据的接口:
int myCircularQueueFront(MyCircularQueue* obj) //返回队头数据的接口 { assert(obj); if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->head->data; //返回队头元素 }
返回队尾数据的接口:
int myCircularQueueRear(MyCircularQueue* obj) //返回队尾数据的接口 { assert(obj); if(myCircularQueueIsEmpty(obj)) { return -1; } ListNode * tem = obj->head; while(tem->next != obj->tail) //寻找队尾元素 { tem=tem->next; } return tem->data; //返回队尾元素 }
队列销毁接口:
队列销毁过程图解:
void myCircularQueueFree(MyCircularQueue* obj) //销毁队列的接口 { assert(obj); //利用头指针来完成链表节点的释放 ListNode * endpoint = obj->head; //记录一个节点释放的终点 obj->head = obj->head->next; while(obj->head!=endpoint) { ListNode * tem = obj->head->next; free(obj->head); obj->head = tem; } free(endpoint); //释放掉终点节点 free(obj); //释放掉维护环形队列的结构体 }
5.静态链表循环队列总体代码
总体代码:
typedef struct listnode { int data; struct listnode * next; }ListNode; typedef struct { int capacity; ListNode * head; ListNode * tail; int taildata; //单向链表找尾复杂度为O(N),因此我们用一个变量来记录队尾数据 } MyCircularQueue; bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueIsFull(MyCircularQueue* obj); //顺序编译注意:先被使用而后被定义的函数要记得进行声明 MyCircularQueue* myCircularQueueCreate(int k) //循环队列初始化接口 { int NodeNum =k+1; //创建k+1个链表节点 MyCircularQueue* object = (MyCircularQueue *)malloc(sizeof(MyCircularQueue)); assert(object); //申请维护循环队列的结构体 object->capacity = k; ListNode * preNode = NULL; //用于记录前一个链接节点的地址 while(NodeNum) { if(NodeNum == k+1) { ListNode * tem = (ListNode *)malloc(sizeof(ListNode)); assert(tem); preNode = tem; object->tail = object->head=tem; //让tail和head指向同一个初始节点 } else { ListNode * tem = (ListNode *)malloc(sizeof(ListNode)); assert(tem); preNode->next = tem; //链接链表节点 preNode = tem; } NodeNum--; } preNode->next = object->head; //将表尾与表头相接 return object; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //数据入队接口(从队尾入队) { assert(obj); if(!obj || myCircularQueueIsFull(obj)) //确定队列没满 { return false; } obj->tail->data = value; //数据入队 obj->tail = obj->tail->next; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) //数据出队接口 { assert(obj); if(!obj || myCircularQueueIsEmpty(obj)) { return false; } obj->head = obj->head->next; return true; } int myCircularQueueFront(MyCircularQueue* obj) //返回队头数据的接口 { assert(obj); if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->head->data; } int myCircularQueueRear(MyCircularQueue* obj) //返回队尾数据的接口 { assert(obj); if(myCircularQueueIsEmpty(obj)) { return -1; } ListNode * tem = obj->head; while(tem->next != obj->tail) //寻找队尾元素 { tem=tem->next; } return tem->data; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判断队列是否为空 { assert(obj); return(obj->head == obj->tail); } bool myCircularQueueIsFull(MyCircularQueue* obj) //判断队列是否为满 { assert(obj); return (obj->tail->next == obj->head); } void myCircularQueueFree(MyCircularQueue* obj) //销毁队列的接口 { assert(obj); //利用头指针来完成链表节点的释放 ListNode * endpoint = obj->head; //记录一个节点释放的终点 obj->head = obj->head->next; while(obj->head!=endpoint) { ListNode * tem = obj->head->next; free(obj->head); obj->head = tem; } free(endpoint); //释放掉终点节点 free(obj); //释放掉维护环形队列的结构体 }
leetcode题解测试:
版权声明：本文为weixin_73470348原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。