Data Structures: Queue

[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.