GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
1.3k views

Consider a standard Circular Queue implementation (which has the same condition for Queue Full and Queue Empty) whose size is $11$ and the elements of the queue are $q[0], q[1], \ldots q[10]$.

The front and rear pointers are initialized to point at $q[2]$. In which position will the ninth element be added?

  1. $q[0]$
  2. $q[1]$
  3. $q[9]$
  4. $q[10]$
asked in DS by Loyal (2.6k points)   | 1.3k views

4 Answers

+5 votes
Best answer

Answer (A)

In Standard Implementation of Circular Queue,

  • For enqueue, we increment the REAR pointer and then insert an element
  • For dequeue, we increment the FRONT and then remove the element at that position.
  • For empty check, when FRONT == REAR, we declare queue as empty

 

 

 

 

answered by Loyal (3.2k points)  
selected by
we initialize front and rear as -1, so first element should be inserted at q[2].

In your solution first element is added at q[3](means 2nd position). Can you explain why?

@Arjuna Sir @Bikram Sir, if you can explain

Correct. So when we initialize to -1, the element is inserted at [0].

The question says

 

The front and rear pointers are initialized to point at q[2]

So, element is inserted at q[3]

Got it. Thank You :)

since the condition of FULL is Front ==( Rear+1) % size, we cannot insert anything at the FRONT position. It will remain empty but satisfies overflow condition.

So to make it correct, Front should point to index 3. Its because in standard circular queue,

initially Front = Rear = -1.

and on the very first insertion both Front and Rear becomes 0. So that front can delete this element. and from 2nd element onwards only Rear is incremented.

 

By looking at the diagram of this answer, we can never delete anything from FRONT as its pointing to NULL. So it must point to index 3.

Wrong. As per the standard algorithm of Circular queue, to delete an item, move from Front to next and if it is not null, delete. This is the standard practice of implementation and same is followed in above answer
I disagree.

Standard Algorithm for deletion :

Step 1 : if FRONT = -1, return underflow.

Step 2 : return Q[FRONT]

Step 3 : if FRONT == Rear then FRONT = REAR = -1

Step 4 : if FRONT = size -1 then FRONT = 0

              else FRONT = FRONT + 1.

In simple terms, we return the value at which FRONT is pointing and just increment the FRONT. that's it.

I am not sure what is the source of your algorithm. I am referring to the one from below, which is considered standard.

http://nptel.ac.in/courses/Webcourse-contents/IIT-%20Guwahati/data_str_algo/queue/add&delete_circular_queue.htm

I am confused now. Please guide me if I'm wrong. If NPTEL algo is correct then,

Lets take an example, size of queue = 5. (1 to 5 indices)

FRONT pointing to 3 and REAR pointing to 2.

According to algo,

Enqueue(Q, 5) :

now, FRONT = 3 and REAR = 3. and Queue is Full.

(here actually Index 3 is empty. only N-1 elements. right ?? )

Enqueue(Q,20):

now, FRONT = 3 but REAR = 4. Even when queue was full its overwriting the queue elements. REAR just passed the FRONT. It should not happen. Correct me please
+3 votes

in circular queue front =rear queue is empty

(rear+1) mod n == front queue is full

1st element inserted at q[2] 2nd at q[3] and so on so 9th element inserted at q[10]

answered by Veteran (31.3k points)  
Pooja please explain your approach of solving.
 
@Pooja: hi I wanna ask you something about the answer you answered in this question:
if the front and rear starts at index 2 then the array will be like this
2  3  4  5  6  7  8  9  10  0   1     ------>    INDEX
0  1  2  3  4  5  6  7   8   9  10    ------> ELEMENT

So 9th element will be in the 8th  right starts from 0th ordering?

So answer should be 10 right?

Please correct me if I am wrong.
front and rear at q[2] then first element is at q[3] na
I think it is implementation dependent, where we are inserting the first element...
i think first element is inserted at q[3].
i too solved like this... my nd ur answer match.. yeh.......

but answer is given option b ..
+1 vote
in a circular queue if front=rear then the queue is empty, insert first element at q[2] thus the ninth element will go to q[10].
answered by Active (2.2k points)  
0 votes

at q[2] first element should be inserted... so like this .. 9th element should be at q[10] ..

but ... answer is option b ... i dont know how .. anybody plz explain

https://www.youtube.com/watch?v=xQdoA_7k4I4

watch this vedio

answered by (389 points)  


Top Users Jul 2017
  1. Bikram

    3782 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1832 Points

  4. joshi_nitish

    1494 Points

  5. Arnab Bhadra

    1096 Points

  6. Arjun

    1054 Points

  7. Hemant Parihar

    1050 Points

  8. Shubhanshu

    972 Points

  9. Ahwan

    876 Points

  10. akash.dinkar12

    642 Points


23,953 questions
30,895 answers
70,107 comments
29,272 users