1.5. Bulk move queues

A bulk move queue is a particular implementation of a queue. It is not quite as efficient as a circular queue and uses much more memory, but this is made up for by its simplicity.

How does it work?

It works very much like a circular queue, except that it doesn't "wrap around". Instead, you make the array much bigger than the maximum number of items in the queue. When you run out of room at the end of the array, you move the entire contents of the queue back to the front of the array (this is the "bulk move" from which the structure gets its name).


Insertion and deletion are very simple. To insert, write the element to the tail index and increment the tail. To delete, save the head element and increment the head. If after an insertion the tail points beyond the end of the array, then do the following:

  1. Copy the contents of the queue to the front of the array (I recommend the move procedure in Pascal or the memcpy function in C, rather than doing it manually).
  2. Set the head pointer to the new head of the queue and the new tail pointer to the new tail of the queue.

Note if the queue occupies more than half the array, then you must be careful that you don't overwrite the frontmost queue elements before they are copied because the old and new queue will overlap (and memcpy doesn't allow overlap - use memmove in this case).

[Prev] [Next] [Up]

Last updated Sun Nov 28 22:04:38.0000000000 2004. Copyright Bruce Merry (bmerry '@' gmail dot. com).