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?

Solution 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.

Solution 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.