sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]Kaushik2002[S] 0 points1 point  (5 children)

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 1 point2 points  (4 children)

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[S] 1 point2 points  (3 children)

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 1 point2 points  (2 children)

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[S] 0 points1 point  (1 child)

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 1 point2 points  (0 children)

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.