CODEWITHSUNDEEP
javadata-structuresqueue
Jony
Jony

Reputation: 6774

Circular Arrays in Queues

How is mod used to determine the beginning and end of a circular array in a queue?

Upvotes: 0

Views: 6565

Answers (2)

kuriouscoder
kuriouscoder

Reputation: 5582

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.

Upvotes: 0

Jon Skeet
Jon Skeet

Reputation: 1499810

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.

Upvotes: 9

Related Questions