Circular Arrays in Queues
How is mod used to determine the begi开发者_开发知识库nning and end of a circular array in a queue?
Well, usually you keep track of the index of the first element, and the current size. If the size is equal to the size of the array, that means the array is full. Enqueuing a new item then requires you to grow the array. Otherwise, you just write to element (start + size + 1) % array_size
.
When you dequeue an element, you just take the element at start
, overwrite it with null to allow for garbage collection, decrement size
, and increment start
, wrapping to 0 if necessary.
An alternative to keeping track of start
and size
is to keep track of start
and next
- where next
is the index of the next element to be enqueued. You spot if the array is full when start == next
. Then enqueuing (when not full) only requires you to change next
, and dequeuing only requires you to change start
. As before, you need to wrap when you increment or decrement start
/next
.
In a circular array the rear of queue is (front + number_of_elements_in_queue - 1) mod size_of_queue
and front of the queue should be tracked after each dequeue.
精彩评论