DataStructureDeQueue

Question

Suppose a dequeue is stored in a circular array with N memory cells. At which of the following condition is the dequeue is full? 

(i) LEFT = N and RIGHT = 1 
(ii) LEFT = RIGHT + 1 
(iii) LEFT = 1 and RIGHT = N 
(iv) LEFT = RIGHT - 1 + N

• A. (i) and (iii)
• B. (iii) and (iv)
• C. (ii) and (iii)
• D. (i) and (iv)

Comments

what is Rear pointer in your view ?

is ar[rear] = new element or ar[rear+1] = new element ? which convention you are following ?

---

Nothing is mentioned in the Question so

1. i think we have to check both possibility i.e Left =front/Rear.

2. As its circular array  we should go with ar[rear+1]=new.

---

then option c is good choice !

---

Yes C is the given ans.

please explain ii i think this condition can be fulfilled though there is space in array(after deletion).

---

let think there are 5 slots in array index 1-5 !

after inserting 4 elements, you deleted 3 elements,

Now left ( used as front pointer ), points to arr[4]

again insert 4 elements, right ( used as rear pointer ) is points at arr[3].

Now for inserting one more element, arr[right+1] == Left, which indicates it is FULL.

PS :- we have to use mod technique, to rotate indices in loop !

---

@Shaik Masthan

what is meaning of left =N and right=1

means rear contains N elements and front 1 element?

---

left means, front pointer position and right means rear pointer position

---

then why front=1?

It means front always contain 1 element in the circular array?

---

no, it means at particular time, front = 1 and rear=N, indicates queue is full !