为什么要实现队列作为圆阵列？ [英] Why implement Queues as Circular Array?

问题描述

当实现像队列这样的FIFO时，我的教练总是建议我们将其表示为循环数组，而不是在一个常规数组中。为什么？

When implementing a FIFO like Queues, my instructor always advise us to represent it as a circular array and not in a regular array. Why?

是因为在后者中，我们最终会在数组中有垃圾数据？

Is it because in the latter, we would end up having garbage data in the array?

推荐答案

如果您正在使用固定数量的阵列插槽/元素，则以圆形排列方式回收您的插槽更为容易，因为您不需要重新排序元素。每当第一个元素以Array-Like的方式被删除时，您必须将剩余的元素移动到前面，所以头不是 null 。在您的循环队列中，您只需增加指向第一个Position的指针。这是更新的操作更少，并提供更好的性能。

If your are using a fixed number of Array-Slots/Elements, it is easier to recycle your slots in a circular arrangement, because you do not need to reorder your Elements. Whenever the first Element gets removed in an Array-Like arrangement, you must move your remaining Elements one position to the front, so the head is not null. In your circular Queue, you just increase your pointer to the first Position. That are less operations on an update and gives you a better performance.

如果您正在构建无限/动态插槽数的队列，这并不重要，因为您可以免费并动态分配内存。

If your are constructing a Queue with unlimited/dynamic number of slots this does not matter, because you can free and allocate the memory dynamically.

这篇关于为什么要实现队列作为圆阵列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！