为什么将队列实现为循环数组? [英] Why implement Queues as Circular Array?

问题描述

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?

解决方案

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屋！