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.