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

Question

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

是因为在后者中,我们最终会在阵列中有垃圾数据吗？

Answer 1

如果您使用固定数量的阵列插槽/元素,则更容易以圆形排列回收插槽,因为您无需重新排序元素.每当第一个元素以类似数组的方式移除时,您必须将剩余的元素移动到前面一个位置,因此头部不是null.在循环队列中,只需将指针增加到第一个位置即可.这对更新的操作较少,并为您提供更好的性能.

如果您正在构建具有无限/动态插槽数的队列,则无关紧要,因为您可以动态释放和分配内存.

Answer 2

我会给你一个比喻.

想象一下街头小贩的队列,人们在线路末端加入并从前面获得服务.当每个人都得到服务时,队列中的其余人员会向前推进(通常会嘀咕其服用多长时间),最后新人加入.在此示例中,人们必须向前移动以使其他人加入该行,否则队列的末尾将始终远离供应商.因此,在此示例中,服务器停留在队列的前端,并处理前方或任何人的任何人.

现在想象一下,如果人们没有移动,而是在服务队列的头部后,卖家自己沿着队列进一步移动,实际上移动到队列的头部.最终服务100人之后,服务器就在街道的一半,500之后,服务器现在在下一条街道等等......它在哪里停止？

因此,为了方便起见,卖方映射了一个大的电路区域,人们总是可以加入队列的末端,并且他总是移动到下一个人,但队列仍然在一个地方.他只是为人们服务.当然他只能为队列中的人服务,但如果他足够大,那么他就能满足需求,而且他不必离开他指定的销售区域.

将这个类比带回计算机......在第一个例子中,有一个队列管理器,当项目被服务时,它会沿着缓冲区随机播放项目.在第二个例子中,程序运行,直到没有更多的内存要添加到数组=它的固定大小(由空间定义或限制).在第三个例子中,服务器像第二个例子一样移动到队列的头部,但是数组是固定的,只有很多项可以加入队列,但它们仍然会得到服务FIFO.

tl; dr:有效的资源管理.