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 REAR and FRONT as array index variables, respectively. Initially, $REAR = FRONT = 0$. The conditions to detect queue full and queue empty are

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

Comments

this link will remove every confusion –

www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/8-List/array-queue2.html

---

Watch this you got one of the best explaination from here 

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

---

The question itself kind of gives away half the answer “Initially REAR = FRONT = 0” since it can  mean  one of the three things :
Queue is empty 

Queue is Full

Exactly one element in the queue (but this cant be possible because  the option says  REAR = =FRONT should either be full or empty )

Also because of this line  “capacity (n−1) elements is implemented with an array of n elements”

 REAR = =FRONT can never mean the queue is Full. Hence the answer should be either B,D

 

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

Can you please tell me how you are considering that rear will always point to the next empty location.As rear always point to the newly inserted element not to the next memory location of newly inserted element

---

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/

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???