ISRO CSE 2014 | Question: 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

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

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

---

In the standard implementation of queue, the rear pointer points to the most recently added element, so when we enqueue a new element we will first increment the rear pointer and then add the element. So in this case the first element will be added at q[3].

• Element 1: q[3] 

• Element 2: q[4]

• Element 3: q[5]

• Element 4: q[6]

• Element 5: q[7]

• Element 6: q[8]

• Element 7: q[9]

• Element 8: q[10]

• Element 9: q[0]

So, the answer is A.) q[0]

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

Answer 5

you ate right 9th element should be added in q10 position.

Comments

as here front and rear are intialized to q[2] so first rear will be incremented and then insertion should be done so 9'th element should come at q[0] position.Is n't it?