Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 575
Sobiaholic Avatar asked Oct 05 '12 23:10

Sobiaholic


1 Answers

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.

like image 68
Simulant Avatar answered Oct 27 '22 13:10

Simulant