知识卡片
环形队列用索引复用空间
用front记录队首、size记录有效数量,下一入队位置由(front+size)对容量取模得到。出队只推进front并减少size,越过数组末尾后回到开头,使空出的前部槽位可再次使用。
容量必须为正,并维护0≤size≤capacity。原书pop在空时仍移动front并减size,是实现错误;满时静默返回也不代表已入队,调用合同应明确成功、满和空的结果。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
我们可以使用一个变量 front 指向队首元素的索引,并维护一个变量 size 用于记录队列长度。定义 rear = front + size ,这个公式计算出的rear 指向队尾元素之后的下一个位置。 基于此设计,数组
参考来源
- 位置:《Hello 算法--Go版本》第05章《栈与队列》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/3.html;spine 2,归一字符[3530,3640))
- 结论依据:实际front/size/rear与取模代码,保留容量及空/满边界。
- 原始内容:我们可以使用一个变量 front 指向队首元素的索引,并维护一个变量 size 用于记录队列长度。定义 rear = front + size ,这个公式计算出的rear 指向队尾元素之后的下一个位置。 基于此设计,数组