一尘不染

为什么将队列实现为循环数组?

java

当实现像队列这样的FIFO时,我的教练总是建议我们将其表示为圆形数组,而不是常规数组。为什么?

是因为在后者中,我们最终将在数组中包含垃圾数据吗?


阅读 262

收藏
2020-12-03

共1个答案

一尘不染

如果您使用固定数量的Array-Slots /
Elements,则以循环方式回收插槽比较容易,因为您不需要重新排列Elements的顺序。每当第一个Element以类似Array的方式移除时,您都必须将剩余的Elements向前移动一个位置,因此头部不会移动null。在循环队列中,只需将指针增加到第一个位置即可。这是对更新的较少操作,可为您提供更好的性能。

如果您要构建一个具有无限/动态插槽数的队列,则没关系,因为您可以动态释放和分配内存。

2020-12-03