GATE CSE 2012 | Question: 35

Question

Suppose a circular queue of capacity $(n −1)$ elements is implemented with an array of $n$ elements. Assume that the insertion and deletion operations are carried out using $\textsf{REAR}$ and $\textsf{FRONT}$ as array index variables, respectively. Initially, $\textsf{REAR} = \textsf{FRONT} = 0$. The conditions to detect queue full and queue empty are:

• A. $\text{full}: (\textsf{REAR}+1) \mod n == \textsf{FRONT}$
  $\text{empty}: \textsf{REAR} == \textsf{FRONT}$
• B. $\text{full}: (\textsf{REAR}+1) \mod n == \textsf{FRONT}$
  $\text{empty}: (\textsf{FRONT}+1) \mod n == \textsf{REAR}$
• C. $\text{full}: \textsf{REAR} == \textsf{FRONT}$
  $\text{empty}: (\textsf{REAR}+1) \mod n == \textsf{FRONT}$
• D. $\text{full}: (\textsf{FRONT}+1) \mod n == \textsf{REAR}$
  $\text{empty}: \textsf{REAR} == \textsf{FRONT}$

Comments

@soyank,

If Rear =8, then element present ar 8 or not ??

Given that rear=0 at initially. Therefore if rear =m, element not present at position m.

Therefore in first round, at position 8 and 9, elements not present. Then how queue is full ?

---

Some Observation : if it was given that (say n - 2) was the circular queue capacity, and array used for implmentation had 'n' capacity.

Then the full condition become (REAR + 2) mod n == FRONT,  

i.e in general for n-k capacity, (REAR + k) mod n == FRONT is the full condition.

---

i think REAR==FRONT==0 ..is for empty condition

because if REAR==FRONT equal but not 0 then must 1 element in QUEUE ???

i am i correct ?

 

Answer 1

$\text{REAR} =\text{Write}$ 

$\text{FRONT} = \text{Read}$

full: $(\text{REAR}+1) \mod n == \text{FRONT}$

empty: $\text{REAR} == \text{FRONT}$

Only option (A) matches.

Comments

If the capacity of the queue itself is "n-1", are we not supposed to use       

 (rear +1)mod(n-1) == front?

---

https://embedjournal.com/implementing-circular-buffer-embedded-c/

---

@saurabh rai I read many answers, but couldnot understood how array with size n having 1 to n index is implementing n-1 elements only, but your way of answering helped me dry run that case on pen paper and made it crystal clear, you should post this answer as it is highly helpful. 

 

Answer 2

D -> This is incorrect, because if you have two elements in Queue of size 5, Front + 1 will not point to Rear. full: (FRONT+1) mod n == REAR is incorrect.

C-> full: REAR == FRONT This is wrong part. Even initially we had rear = front = 0 , does this means queue is full ?

B-> empty: (FRONT+1) mod n == REAR , Initially queuee is empty, still  this heuristic will say that queue is not empty. As Rear = front = 0, So Front + 1 % mod n = 1 != 0

A is correct option.

Answer 3

A will be the correct option just dry run it with smaller size of array..i did a programme on it earlier so i just answered to it by looking at it..

Comments

after one insertion the queue will not be empty and still rear and front will point to the same location?

---

No.
FRONT will be pointing to the first item in the queue, while REAR will be pointing to the next empty location. 

See this :

• http://stackoverflow.com/a/16399414/3451554
• CLRS (Ed 3) Pg:234-235

---

Don’t post that these type of answers that you ran this program in your computer. its of no use.

Answer 4

In Circular Queue 

If Queue is full then first element should 0^th element and last element should be n-1^th element , lets assume an example if circular queue contains 5 element then :- 

1st element should be 0th element or front =0 and last will be 4th element or rear =4

so according to option A :- full: (REAR+1) mod n == FRONT

(4+1) mod 5 = 0 = Front then this condition satisfies so option C and D eliminated 

now we have to check 2^nd condition of option A whether it is correct or not 

empty: $REAR == FRONT$ 

As we know in queue

if Front = Rear = -1 then queue is Empty 

So option B is eliminated 

Option A will be right option

Comments

But this can also mean that there is a single element right???

Answer 5

One of the best explaination you can find from here.

https://www.youtube.com/watch?v=4BKihDq6gB4

Answer 6

full : (R+1)modn==F

empty : R=F=-1 but here R=F=0 is the empty condition

hence ans A

Comments

People not getting this question. This is the only thing we need to understand that when queue is empty, F==R=0 is given in question. Sad to see that this comment has only one thumbs up and that too by me. Great comment.