CODEWITHSUNDEEP
data-structuresqueuecircular-queue
Java Enthusiast
Java Enthusiast

Reputation: 1191

Understanding queue arithmetic in data structures

When an element is inserted in a queue, REAR = REAR + 1. When an element is deleted from the queue, FRONT = FRONT + 1 when queues are implemented using arrays.

Now, initially, both FRONT = REAR = -1 indicating the queue is empty. When the first element is added, FRONT = REAR = 0 (assuming array from 0 to n-1).

Now, if we assume a condition where FRONT = 0 and REAR = n-1 implying the queue is full. When a few elements are removed the FRONT pointer changes. Let us say FRONT = 5 and REAR = 10. Hence, array locations 0 to 4 are free.

When I wish to add an element now, I add at the location 0 and FRONT points to it. But the locations 1, 2, 3 and 4 are free.

But, when the next time I try to insert an element, the code for the queueing arithmetic will throw an error saying the queue is full. Since FRONT = 0 and REAR = n-1. How do I insert at the remaining free locations and also understand this queuing arithmetic better?

I would also like to understand how FRONT = REAR + 1 acts as a condition for checking if the queue is full?

Upvotes: 2

Views: 945

Answers (1)

user4842163
user4842163

Reputation:

You want to think circularly here in terms of relative, circular ranges instead of absolute, linear ones. So you don't want to get too hung up on the absolute indices/addresses of FRONT and REAR. They're relative to each other, and you can use modulo arithmetic to start getting back to the beginning of the array like Pac-Man when he goes off the side of the screen. It can be useful when you're drawing these things out to literally draw your array as a circle on your whiteboard.

When I wish to add an element now, I add at the location 0 and FRONT points to it. But the locations 1, 2, 3 and 4 are free.

I think in your statement above you got it backwards a bit. Insertions in a queue advance REAR, not FRONT. In such a case, REAR would be at 0, and FRONT would still be at 5. If you push again, REAR would be at 1 and you'd overwrite the first index, and FRONT would still be 5.

If N=3 and FRONT=2 and REAR=2, we have one element in the queue after pushing and popping a lot. When you push (enqueue), we set: REAR=(REAR+1)%N making FRONT=2, REAR=0 giving us two elements. If we push again, FRONT=2, REAR=1 giving us 3 elements, and the queue is full.

Visually:

     R
  [..x]
     F

   R
  [x.x]
     F

    R
  [xxx]
     F

... and now we're full. A queue is full if the next circular index from the REAR is the FRONT. In the case where FRONT=2, REAR=1, we can see that (REAR+1)%N is equal to FRONT, so it's full.

If we popped (dequeued) at this point at this point, we would set FRONT=(FRONT+1)%N and it would look like this:

    R
  [xx.]
   F

I would also like to understand how FRONT = REAR + 1 acts as a condition for checking if the queue is full?

This doesn't suffice when you use this kind of circular indexing. We need a slight augmentation: the queue is full when FRONT is equal to (REAR+1)%N. We need that modulo arithmetic to handle those "wrap around to the other side" cases.

Upvotes: 2

Related Questions