Disadvantage of circular queue?

Question

Recently, in an interview I was asked the disadvantage of using circular queue. I couldn't think of any. Searching the internet the only answer I found is that it's difficult to implement than linear queue :). Is there any other disadvantage?

Benedetto

Depending on implementation, you may have to leave a node empty in a circular queue whereas a linear queue ca be filled completely. Not much of a disadvantage, unless each node is gigantic! – Obscene

why a node have to left empty ? – Benedetto

It depends on how you implement the circular queue. If you store data in every node, then there is no easy way to differentiate between an empty and full list. – Obscene

@Obscene - You can distinguish full and empty if the 2 variables are "head" and "size" rather than head and tail. You can also do it with "head" and "tail", but use a special value (e.g. -1) for the "tail" index when the queue is empty (or full). A reserved slot is a viable option too, provided it is OK to "waste" an entry. It is a CPU vs memory trade-off. – Roomette

Answer 1

I would say the biggest disadvantage to a circular queue is you can only store queue.length elements. If you are using it as a buffer, you are limiting your history depth.

Another smaller disadvantage is it's hard to tell an empty queue from a full queue without retaining additional information.

Fame

Not that hard. See comments on Question. There are at least 2 ways to do it ... – Roomette

Answer 2

The answer that the interviewer was looking for probably depends on some additional context that isn't in the above question.

For instance, often circular queues are considered for highly concurrent producer/consumer systems. When the queue is full, operations at the front and back of the queue can contend for the same cache lines, and that can be a problem in contexts like this.

Or maybe the interviewer wanted you to talk about how much easier it is in a garbage-collected language to make a lock-free linked queue as compared with a circular array-based queue.

Or maybe it's just about how you can make much better use of the vector containers provided by your language if you use a linear queue with periodic shifting instead of a circular queue.

Hanker

Answer 3

It seems to me that any code that traverses the queue would have to keep track of the first node in order to detect the end of the traverse. But in a multi-threaded environment another thread might remove the first node, which would cause the traversing thread to go into an infinite loop. So the traversing thread would have to keep the first node locked for the duration of its cycle through the queue.

Garnish

Then again, there are usually hazards to using any sort of list during enumeration. For example, the tail of a regular linked list could get deleted and moved to the head (not uncommon when dealing with queues), which could break an iterator. – Wojcik

Will that not happen in the case of shared memory between multiple processes ? I ask as you explicitly mention threads – Obscene

@AshRj Yes, it could certainly happen with multiple processes. – Garnish

@Nneonneo Yes, I suppose that's true. – Garnish

In the case of a circular queue, once the queue is created, no nodes are added or deleted, only pointers to the head and tail are advanced. – Triadelphous