The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
1.5k 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 (3.5k points) | 1.5k 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.9k 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 (33.2k 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.5k 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 Junior (607 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,947 questions
36,793 answers
91,077 comments
34,690 users