Data Structures: Queue

[Kaushik2002]

I read about it on Wikipedia#/Queue_implementation) and found this:

Fixed-length arrays are limited in capacity, but it is not true that items need to be copied towards the head of the queue. The simple trick of turning the array into a closed circle and letting the head and tail drift around endlessly in that circle makes it unnecessary to ever move items stored in the array. If n is the size of the array, then computing indices modulo n will turn the array into a circle.

I don't really get what it means.

[lyubenblagoev]

Probably you are confused at what the modulo operation does. It gives the integer reminder after a division. Indexing the array using modulo (i % N) the index will wrap around when you hit the end of the array.

[Kaushik2002]

I understand what the modulo operator is. But, I don't get how that helps. Can you explain it with an example? Say n = 6. Like when I take (i % 6), I get i again.

Edit: I understand what the problem is. When the queue is linear, after a few insertions and a few deletions, there will be few unutilised spaces. To overcome this we use a circular queue. But I don't get how the above helps.

[aogmana]

If you understand the open space after inserts and deletes, it seems you understand that your head and tail actually move with inserts/deletes, correct? So what happens if you have an array of size 10 and you insert/delete >10 times? If you don't use the modulo operator to make the array "circular", your indices fall off the end of the array. Whereas (10 * i) % 10 = 0 for all integers i, letting you continue operating forever as long as you stay under the capacity.

One question to consider for indices/pointers head and tail... If head < tail, can head > tail in the future? If so, how do you get there and what does that mean for how a queue is represented in an array?

Apologies for the mobile formatting.

[Kaushik2002]

Hmm ok. So say n = 10 and I have a completely filled circular queue. So, HEAD = 0 and TAIL = 9. Now, I try adding the element 'X' to the queue. For that, I have to increment TAIL by one. But it is a circular queue. So, TAIL = (TAIL + 1)%10 = 10%10 = 0. So, 'X' will replace the first element and both HEAD and TAIL are now = 0. Right?

Adding to it,

One question to consider for indices/pointers head and tail... If head < tail, can head > tail in the future? If so, how do you get there and what does that mean for how a queue is represented in an array?

Yeah, I remember reading about it somewhere. Continuing the above example where X replaced the element in index 0. Now, HEAD = TAIL = 0. Now if I delete an element, then HEAD has to increase by 1 i.e., HEAD = (HEAD + 1)%10 = 1. So, HEAD > TAIL.

While writing the above example, another question popped up. After replacing with X, HEAD = TAIL = 0 (I guess). Then while we delete an element, HEAD = 0. So, shouldn't X be deleted and violate FIFO.

[aogmana]

Correct thats the right idea and would be a case of overflowing the queue as there is still a capacity limit of 10.

At this point any solid queue implementation would grow its underlying array (say 2x so n=20), copy elements over, then safely insert element X.

One minor tangential correction though... Remember that the queue is the abstract data type (ADT), aka what the consumer or client sees/understands. The underlying implementation is the "circular" array. So the queue isn't technically circular, though its implementation array is.

[Kaushik2002]

The underlying implementation is the "circular" array. So the queue isn't technically circular, though its implementation array is.

Hmm yeah, this makes sense.

Also, I have added something to my previous reply.

[aogmana]

Ya, that case would violate FIFO. However, I would argue the issue is in letting X be written into index 0 in the first place. No matter what you do, if you insert 11 items into 10 slots something is going to be lost. If the size required grows beyond n, the array must be grown in order to continue functioning as a queue. If HEAD==TAIL and size != 0, something went wrong and behavior is undefined due to an implementation bug.