dedecms模板站,外包制作app,平台销售,石家庄做网站百度推广这道题讲了两种方法#xff0c;第一个代码是用数组实现的#xff0c;第二个是用链表实现的#xff0c;希望对你们有帮助
#xff08;最好在VS自己测试一遍#xff0c;再放到 leetcode上哦#xff09;
下面的是主函数#xff08;作参考#xff09;#xff0c;静下心来…这道题讲了两种方法第一个代码是用数组实现的第二个是用链表实现的希望对你们有帮助
最好在VS自己测试一遍再放到 leetcode上哦
下面的是主函数作参考静下心来慢慢测试 622. 设计循环链表 题目 设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。 你的实现应该支持如下操作 MyCircularQueue(k): 构造器设置队列长度为 k 。Front: 从队首获取元素。如果队列为空返回 -1 。Rear: 获取队尾元素。如果队列为空返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。 题目链接 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 文字 和 画图 分析 思考什么情况下队列为空队列为满 定义一个 指针head用来存放头节点的地址和一个指针tail用来存放尾节点的地址这个思路和队列的实现是一样的 按照正常思路大多数人会以为队列长度为k 当 head tail 为空而 tail 是第 k 个节点的时候为满却忽略一点这是个循环链表 以下这种情况就不成立 通过图我们知道 head tail 无法判断是空还是满 所以我们换一种思路 存放 k 个元素但是开辟k 1个节点故意留下一个节点不放元素 情况就是这样的: 我们发现 当 head tail 为空 当 tail 的下一个节点 head为满; 2. 选用数组还是链表去做 这里两者思路我都讲代码仅供参考能通过但是我个人觉得有些地方没有处理好其实可以更完善听思路即可 用数组head 和 tail 就是元素下标 a. 首先明确这本质是一个循环链表 b. 实现过程可能会遇到的问题 问题1 这里可以看到 tail 不可能一直加加 如果是正确的思路此时的图应该是这样 所以我们这里要对 tail 进行处理 这里可以通用 tail tail % (k 1)head也会出现这样的情况同样要这么处理 问题2 判断为满时我们可能会犯错误 这种情况我们非常容易知道判断 tail 1 head 但是这种情况就不适用了 所以我们要写一个通式 (tail 1 ) % (k 1) head 问题3 找到尾元素 正常情况下的尾元素很好找 尾元素的下标就是 tail - 1 如果是这样就不好判断了 这里我们可以用 if else语句做区分 也可以写一个通式 (tail - 1 k 1) % (k 1) 即tail k %k 1 用链表head 和 tail 就是头节点和 尾节点的地址 a. 这里可以写一个循环链表 可以在初始化的时候先搭建好这个循环链表后面再存放元素 b. 只有一个地方需要注意 就是找尾元素实际上应该是tail的上一个节点 这里选择可以记录上一个节点的地址 或者 循环找到上一个节点 代码 代码1
typedef int SLType;
typedef struct StackList
{SLType* a;int top;int rear;int k;
}SL;//创建数组
void SLInit(SL* head, int k)
{assert(head);head-a (SLType*)malloc((k 1) * sizeof(SLType));head-top 0;head-rear 0;head-k k;
}//初始化数组
void SLPush(SL* head, SLType x)
{assert(head);head-a[head-rear] x;head-rear;
}//存放元素
void SLPop(SL* head)
{assert(head);head-top;
}//删除元素//以上都是数组的实现typedef struct
{SL q;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));SLInit(obj-q, k);return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{SL* q1 obj-q;return q1-rear q1-top;
}//判断是否为空bool myCircularQueueIsFull(MyCircularQueue* obj)
{SL* q1 obj-q;int a q1-rear;a (q1-rear 1) % (q1-k 1);return a q1-top;
}//判断是否为满bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{if (myCircularQueueIsFull(obj)){return false;}else{SLPush(obj-q, value);SL* q1 obj-q;q1-rear q1-rear % (q1-k 1);return true;}}//存放元素bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj)){return false;}else{SLPop(obj-q);SL* q1 obj-q;q1-top q1-top % (q1-k 1);return true;}}//删除元素int myCircularQueueFront(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj)){return -1;}else{return (obj-q)-a[(obj-q)-top];}
}//返回头元素int myCircularQueueRear(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj)){return -1;}else{if ((obj-q)-rear 0){return (obj-q)-a[(obj-q)-k];} return(obj-q)-a[(obj-q)-rear - 1];}
}//返回尾元素void myCircularQueueFree(MyCircularQueue* obj)
{free(obj);
}//销毁空间 代码2
typedef int QLType;
typedef struct QueueNode
{QLType val;struct QueueNode* next;
}QN;//创建节点
typedef struct StackList
{QN* head;QN* tail;}QL;//创建队列
void QNInit(QL* pphead, int k)
{pphead-head pphead-tail NULL;QN* prev NULL;k k 1;while (k--){QN* newnode (QN*)malloc(sizeof(QN));if (pphead-head NULL){prev pphead-head pphead-tail newnode;}else{pphead-tail newnode;pphead-head-next pphead-tail;pphead-tail-next prev;pphead-head pphead-tail;}}pphead-head pphead-tail prev;
}//初始化并链接节点QLType QLTop(QL* pphead)
{return pphead-head-val;
}//返回首元素
QLType QLtail(QL* pphead)
{QN* rear pphead-head;while (rear-next ! pphead-tail){rear rear-next;}return rear-val;
}//返回尾元素
void QLpush(QL* pphead, int val)
{pphead-tail-val val;pphead-tail pphead-tail-next;
}//存放元素
void QLPop(QL* pphead)
{pphead-head pphead-head-next;
}//删除元素//以上是链表的创建typedef struct
{QL q;
} MyCircularQueue;MyCircularQueue * myCircularQueueCreate(int k)
{MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));QNInit(obj-q, k);return obj;
}//初始化
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{QL* q1 obj-q;return q1-head q1-tail;
}//判断是否为空bool myCircularQueueIsFull(MyCircularQueue* obj)
{QL* q1 obj-q;return q1-tail-next q1-head;
}//判断是否为满
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{if (myCircularQueueIsFull(obj)){return false;}else{QLpush(obj-q, value);return true;}}//存放元素bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj)){return false;}else{QLPop(obj-q);return true;}
}//删除元素int myCircularQueueFront(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj)){return -1;}else{return QLTop(obj-q);}
}//返回首元素int myCircularQueueRear(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj)){return -1;}else{return QLtail(obj-q);}
}//返回尾元素void myCircularQueueFree(MyCircularQueue* obj)
{free(obj);
}//释放空间
