Why implement Queues as Circular Array?

java data-structures queue fifo
Sobiaholic picture Sobiaholic · Oct 6, 2012 · Viewed 15.1k times · Source

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?

Answer

Simulant picture Simulant · Oct 6, 2012

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.

Related questions

How do I instantiate a Queue object in java?

When I try: Queue<Integer> q = new Queue<Integer>(); the compiler is giving me an error. Any help? Also, if I want to initialize a queue do I have to implement the methods of the queue?

Read More
LinkedBlockingQueue vs ConcurrentLinkedQueue

My question relates to this question asked earlier. In situations where I am using a queue for communication between producer and consumer threads would people generally recommend using LinkedBlockingQueue or ConcurrentLinkedQueue? What are the advantages / disadvantages of using one over …

Read More
Queue vs Dequeue in java

What is the difference between them? I know that A queue is designed to have elements inserted at the end of the queue, and elements removed from the beginning of the queue. Where as Dequeue represents a queue where you …

Read More