ISRO2014-36

Question

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?

• A. $q[0]$
• B. $q[1]$
• C. $q[9]$
• D. $q[10]$

Comments

this question’s answer is implementation dependent cuz we can implement

enqueue two way:

i. way One : we first insert element at rear index then increment the rear.This will result to option-D

2.way Two : we first increment rear pointer then insert data at the new value of rear.This will result to option-A

Answer 1

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

Comments

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 :)

---

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

---

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

---

I think the answer should be option b, because in the question the elements of the queue are given as q[0],q[1]....q[10].. which means a total of 11 elements. So if we place element 0 at the 3rd position, the ninth element would occupy q[1]. @Arjun sir, please confirm.

Answer 2

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]

Comments

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

Answer 3

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].

Answer 4

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