目录
问题来源:622. 设计循环队列 – 力扣(Leetcode)
一.循环队列简单介绍
- 循环队列一般是一种静态的线性数据结构,其中的数据符合先进先出的原则.
- 循环队列的容器首地址和容器尾地址通过特定操作(比如指针链接,数组下标取余等方式)相连通,从而实现了容器空间的重复利用(在一个非循环静态队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间)
![]()
二.用静态数组实现循环队列
维护队列的结构体:
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题解测试:
版权声明:本文为博主作者:努力的青菜原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/weixin_73470348/article/details/129167702