What is the correct term for a fixed sized FIFO queue?

Question

What is the correct name for the following data structure? It is:

• A queue of fixed size
• New elements are added to the start
• Whenever the queue gets above a certain size a number of elements are removed from the end

Answer 1

it is a circular buffer

Answer 2

I think it may depend on the actual implementation of this. A practical example of what you describe is the Circular Buffer or Ring Buffer where the oldest data is overwritten by new data once the buffer is full. This would be one of traditional ways of implementing such a data structure in something like C.

EDIT: Ok, so the Circular Buffer doesn't quite fit. How about Finite Buffer Queue, or Finite Capacity Queue? But those don't really cover the self-limiting aspect...

Self-limiting Finite Capacity Bratt Queue.

Auto-popping...

My point being that I don't think there's an official name for a data structure with the exact properties that you mention, so you might as well make one up based on the data structure that nearest resembles it, perhaps combined with some of your structure's unique properties. It's probably going to be pretty wordy though...

EDIT: Or perhaps it's a Cyclic Queue. The article describes it as:

this article describes a Queue similar to the System.Collections.Queue, except that it has > a fixed buffer size. This means, of course, that the buffer could not be large enough to > hold all the items added to the Queue, in which case the oldest items are being dropped.

...which sounds a lot like yours. Nice and concise too.

Answer 3

In hardware, a similar structure is called a shift register.

Answer 4

"a fixed sized FIFO queue"

Sometimes buffer, sometimes ring buffer ( as that's how it's normally implemented ). I'm not aware of anything which denotes your strategy for removing items in batches, though it's not uncommon.

Answer 5

In embedded systems, this is almost universally referred to as circular buffers.