3 ms·
It really is a double ended queue. A circular buffer is a particular data structure that share some properties with the double ended queue. One of the differen
by chmike 10y ago
It really is a double ended queue. A circular buffer is a particular data structure that share some properties with the double ended queue.
One of the difference is that a circular buffer has a fixed capacity. The double ended queue has no capacity limit.
- falcor84 10y agoWell, from what I remember from my data structures class, a queue/dequeue has to have O(1) worst case insertion, but otherwise, yeah, it's pretty much the same. But your part made me think, indeed there's no inherent reason for a circular buffer to have a fixed capacity. You could use pretty much the same logic but implement reallocation when it's 100% full, and get most of the benefit of both.
- clarkd99 10y agoA circular buffer can contain a number of nodes and get bigger when it runs out of space by making a larger buffer and copying the old data or clustering as I described above. It doesn't have a "fixed capacity". My circular queue works without moving any elements on insertion (with cluster method) or just moving the nodes each time the buffer size is exceeded. It seems this "double ended queue" isn't as useful because it has to copy nodes, find a middle etc. Even in the "cluster" version of my circular queue, you can quickly calculate the actual location of any node directly using it's "virtual" index number, even though the head and tail can "float" anywhere along each cluster array of structs.