leetcode 622 循环队列设计

要求:设计实现循环队列
循环队列定义:队尾指向队首;
构造:设置一个长度为k的循环队列;
要求的操作:取队首队尾/插入/删除/空判断/满判断

那根据要求,这个队列至少拥有以下部分:
指向队列的指针()
指向队首/队尾的指针;
空判断:队首=队尾
满判断:队首=队尾
所以需要一点处理区分空和满;
常规的处理方式是:申请时留一个不用的空位,这样一来:
空:队首=队尾;
满:队尾+1=队首;

官方的题解提供了两种思路:
1)用数组实现
构造:申请一个k+1的数组空间,队首队尾都置于0;
通过对k的取余操作保证取值永远在0-k-1之间
取队尾的时候需要注意:
rear实际指向的是队尾的下一个,实际取出来的应该是[rear-1]
2)用链表实现
链表就直接不用顾忌空间了
加入:size++;修改尾部到tail->next;
删除:size-1;修改头部到head->next,之前的释放;
空判断/满判断:直接看size啊 0就是空k就是满
(但我不知道为啥ListNode它就直接用了 这玩意儿不用声明的吗)

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容