GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
933 views

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

asked in DS by Veteran (12.9k points)   | 933 views

3 Answers

+8 votes
Best answer

 

 

rear = Write 

front = Read

full: (REAR+1) mod n == FRONT

empty: REAR == FRONT

Only option A matches.

 

answered by Veteran (47.3k points)  
From the Given options it is clear that  Option A is Ans.

@Anirudh but

Initially when queue is empty @time Front=Rear=0

Now after Insertion of 1 element into empty Q at which index does front and rear point?? Can u plz explain??
First of all, i did not understand - circular queue of size = n-1, while array has n elements ...
Does it mean that circular queue can only accomodate n-1 element or its index can varry from 0 to n-1 ??
Same here..@vijaycs this was my next confusion ;p
@rajeshpradhan+vijaycs
in this implementation of circular queue it is given that "Suppose a circular queue of capacity (n−1) elements is implemented with an array of n elements. " so it means that its index varies from 1 to n{array contains n slots} but it can accomodate n-1 elements
now initially rear=front=0 // means queue is empty
  in this implementation rear is always points to an empty location where a new element will be inserted suppose n=10 front is at 6 and rear is at 5 this means currently 5 is an empty location and new element will be inserted at location 5 but before insertion at loc 5 it will check for full condition "(rear+1)modn=front" so for this case (5+1)mod 10=6 so this meets the full condition as  "(rear+1)modn=front"  but here is still an empty slot so that is the reason that why we can accomodate only n-1 elements.
and now if f=r so as i told u before that rear is always pointed to an empty location so at ths tme both front and rear pointing to an empty location so this meets the condtion that circular queue is empty.
-------- i hope tht this will help u if u have any doubt after then plzz refer to CLRS (Ed 3) Pg:234-235and excercise 10.1.4
it means that the no of elements in the circular array in max on n-1 . Yes it means that the no of elements is of maximum of n-1 . this is done to make sure that rear==front means that the array is empty.

 

if we allow maximum of n elements in the circular array then if the circular array is full in that case rear would be equal to front. which by the convention means the array is empty.
so in order to avoid this confusion . we allow a maximum of n-1 elements.
@ Saurabh, front never points to any queue element right? Queue starts from front+1 , i mean if front is currently at say 4 and the size of queue is 5, then queue will contain elements at 5,0,1,2,3 right?
+5 votes
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..
answered by Veteran (13.1k points)  
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 :

+2 votes

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.

answered by Veteran (41.4k points)  
Answer:

Related questions



Top Users May 2017
  1. akash.dinkar12

    3338 Points

  2. pawan kumarln

    2108 Points

  3. Bikram

    1922 Points

  4. sh!va

    1682 Points

  5. Arjun

    1614 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1208 Points

  8. Angkit

    1056 Points

  9. LeenSharma

    1018 Points

  10. Arnab Bhadra

    812 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    1008 Points

  2. pawan kumarln

    734 Points

  3. Arnab Bhadra

    726 Points

  4. Arjun

    342 Points

  5. bharti

    328 Points


22,893 questions
29,196 answers
65,302 comments
27,695 users