上海网站建设企业,一个网站网站建设下来要花多少钱,采招网,wordpress评论者头像目录
一.循环队列简单介绍
二.用静态数组实现循环队列
1.数组循环队列结构设计
2.数组循环队列的堆区内存申请接口
3.数据出队和入队的接口实现
4.其他操作接口
5.数组循环队列的实现代码总览
三.静态单向循环链表实现循环队列
1.链表循环队列的结构设计
2.创建静…
目录
一.循环队列简单介绍
二.用静态数组实现循环队列
1.数组循环队列结构设计
2.数组循环队列的堆区内存申请接口
3.数据出队和入队的接口实现
4.其他操作接口
5.数组循环队列的实现代码总览
三.静态单向循环链表实现循环队列
1.链表循环队列的结构设计
2.创建静态单向循环链表的接口
3.数据的出队和入队接口
4.其他队列操作接口
5.静态链表循环队列总体代码 问题来源: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指针的关系来实现队列的判满(判断队列空间是否已被占满)与判空(判断队列是否为空队列)为了达到这个目的,我们需要将静态数组的容量大小设置为k1(即多设置一个元素空间) 队列的判空条件: tail head;队列的判满条件: (tail1)%(k1) head; 另外一种情形:由此我们可以先设计出队列的判满和判空接口 bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判断队列是否为空
{assert(obj);return (obj-tail obj-head);
}bool myCircularQueueIsFull(MyCircularQueue* obj) //判断队列是否为满
{assert(obj);return ((obj-tail1)%(obj-capacity 1) obj-head);
} 2.数组循环队列的堆区内存申请接口 在堆区上创建MyCircularQueue结构体,同时为队列申请一个空间大小为(k1)*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; //队列的数据容量为ktem-arry (int*)malloc((k1)*sizeof(int));//开辟堆区数组if(NULL tem-arry){perror(malloc failed);exit(-1);}//将head,tail下标初始化为0tem-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; //队列的数据容量为ktem-arry (int*)malloc((k1)*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-tail1)%(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: 与数组循环队列类似,我们同样需要开辟一个节点个数为k1的静态循环链表链表循环队列的总体结构图示:另外一种队列判满的情形: 链表循环队列的判满条件(判断队列空间是否被占满的关系式):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.创建静态单向循环链表的接口 实现一个接口,创建一个维护链表循环队列的结构体同时创建容量大小为k1的静态单向循环链表: MyCircularQueue* myCircularQueueCreate(int k) //循环队列初始化接口
{int NodeNum k1; //创建k1个链表节点MyCircularQueue* object (MyCircularQueue *)malloc(sizeof(MyCircularQueue));assert(object); //申请维护循环队列的结构体object-capacity k;ListNode * preNode NULL; //用于记录前一个链接节点的地址while(NodeNum){if(NodeNum k1){ ListNode * tem (ListNode *)malloc(sizeof(ListNode));assert(tem);preNode tem;object-tail object-headtem; //让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) //寻找队尾元素{temtem-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 k1; //创建k1个链表节点MyCircularQueue* object (MyCircularQueue *)malloc(sizeof(MyCircularQueue));assert(object); //申请维护循环队列的结构体object-capacity k;ListNode * preNode NULL; //用于记录前一个链接节点的地址while(NodeNum){if(NodeNum k1){ ListNode * tem (ListNode *)malloc(sizeof(ListNode));assert(tem);preNode tem;object-tail object-headtem; //让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) //寻找队尾元素{temtem-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题解测试:
