要求:设计实现循环队列
循环队列定义:队尾指向队首;
构造:设置一个长度为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它就直接用了 这玩意儿不用声明的吗)