【图解算法】622. 设计循环队列
2021/11/4 11:09:42
本文主要是介绍【图解算法】622. 设计循环队列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
实际中我们有时还会使用一种队列叫循环队列。环形队列可以使用数组实现,也可以使用循环链表实现。
本文使用数组实现。
循环链表实现此处不议。
循环队列分析
- 符合先进先出
- 空间大小确定
解题思路
通过一个定长数组实现循环队列。
入队:首先要判断队列是否已满,再进行入队的操作。入队操作要考虑索引循环的问题,索引越界时,需要让他变成最小值。
出队:首先要判断队列是否为空,再进行出队操作,出队也需要考虑索引循环的问题。
队空:队头 == 队尾
队满:队尾+1 == 队头
图解步骤
开一个长度k=5的队列,所以需要k+1个空间。
因为这里我们的tail指向是最后一个元素的后一个位置(和判空条件有关系)
循环队列结构
- 头指针,尾指针
- 顺序表
- k队列长度
题解
C:
typedef struct { int* a; int front; int tail; int k; } MyCircularQueue; bool myCircularQueueIsFull(MyCircularQueue* obj); bool myCircularQueueIsEmpty(MyCircularQueue* obj); MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue *cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); cq->a = (int*)malloc(sizeof(int)*(k+1)); cq->front = cq->tail = 0; cq->k = k; return cq; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { // 队列已满 if(myCircularQueueIsFull(obj)) return false; // 队尾入 obj->a[obj->tail] = value; obj->tail = (obj->tail + 1)%(obj->k+1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; // 队头出 ++obj->front; obj->front %= (obj->k + 1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { // 从队头获取元素 if(myCircularQueueIsEmpty(obj)) return -1; return obj->a[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { // 从队尾获取元素 if(myCircularQueueIsEmpty(obj)) return -1; int i = (obj->tail+obj->k)%(obj->k+1); return obj->a[i]; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->tail; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->tail+1)%(obj->k+1) == obj->front; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); obj = NULL; } /** * Your MyCircularQueue struct will be instantiated and called as such: * MyCircularQueue* obj = myCircularQueueCreate(k); * bool param_1 = myCircularQueueEnQueue(obj, value); * bool param_2 = myCircularQueueDeQueue(obj); * int param_3 = myCircularQueueFront(obj); * int param_4 = myCircularQueueRear(obj); * bool param_5 = myCircularQueueIsEmpty(obj); * bool param_6 = myCircularQueueIsFull(obj); * myCircularQueueFree(obj); */
这篇关于【图解算法】622. 设计循环队列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-02Java管理系统项目实战入门教程
- 2024-11-02Java监控系统项目实战教程
- 2024-11-02Java就业项目项目实战:从入门到初级工程师的必备技能
- 2024-11-02Java全端项目实战入门教程
- 2024-11-02Java全栈项目实战:从入门到初级应用
- 2024-11-02Java日志系统项目实战:初学者完全指南
- 2024-11-02Java微服务系统项目实战入门教程
- 2024-11-02Java微服务项目实战:新手入门指南
- 2024-11-02Java项目实战:新手入门教程
- 2024-11-02Java小程序项目实战:从入门到简单应用