3 ms·

> I thought array-based queues resulted in O(n) queue/dequeue. Not necessarily. A circular buffer[1] can be used as a queue with O(1) queue/dequeue. C++ implem

> I thought array-based queues resulted in O(n) queue/dequeue. Not necessarily. A circular buffer[1] can be used as a queue with O(1) queue/dequeue. C++ implementations (gcc?), IIRC, uses an interesting array-of-arrays approach; it also has O(1) queue/dequeue. I'm not sure why the array-of-arrays approach is better than a circular buffer, though. Array based designs can result is less allocations, and maybe less overhead. For example, if you have a circular buffer with space for 16 items, it only needs to allocate space if you need more room, whereas a linked list queue would allocate for each and every item placed into it. Linked lists also require space for the pointer to the next link, for each link in the list. (And, if you keep them, back pointers, though these aren't necessary for just a queue.) Arrays might have some unused slack space, however. [1]: https://en.wikipedia.org/wiki/Circular_buffer https://en.wikipedia.org/wiki/Circular_buffer

jayd16 8y ago
Resizing a fully contiguous circle buffer would cause a copy every element as well forcing you to make a single contiguous memory section. Array of arrays just needs to resize the top level array.
- manwe150 8y ago
  But the copy only has to move n items, but was constructed with m items, where n < m (and usually n << m). Where n is the max size of the queue and m is the total number of items that will ever be enqueued. On the other hand, an array of arrays (no recursion) doesn’t change the big-O complexity cost, just the constant multiplier. That should definitely improve performance of the uncommon operation (the copy), but hypothetically might slow down the actual queuing operations (and drastically reduce throughout) But maybe you meant the array of arrays to be recursive? That seems like it would alter the big-O (from n+m to log(n)+m). But typically m>>n, so the net result is the same.

jayd16 8y ago

Resizing a fully contiguous circle buffer would cause a copy every element as well forcing you to make a single contiguous memory section. Array of arrays just needs to resize the top level array.

manwe150 8y ago
But the copy only has to move n items, but was constructed with m items, where n < m (and usually n << m). Where n is the max size of the queue and m is the total number of items that will ever be enqueued. On the other hand, an array of arrays (no recursion) doesn’t change the big-O complexity cost, just the constant multiplier. That should definitely improve performance of the uncommon operation (the copy), but hypothetically might slow down the actual queuing operations (and drastically reduce throughout) But maybe you meant the array of arrays to be recursive? That seems like it would alter the big-O (from n+m to log(n)+m). But typically m>>n, so the net result is the same.