GATE CSE 2017 Set 2 | Question: 13

Question

A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in $O(1)$ time?

1. Next pointer of front node points to the rear node.
2. Next pointer of rear node points to the front node.

• A. (I) only.
• B. (II) only.
• C. Both (I) and (II).
• D. Neither (I) nor (II).

Comments

not exactly the same I would say.

There they have used circular Linked List to implement a normal queue.

Here they are asking whether we need circular linked list necessarily to implement a queue with the benefits of a circular queue.

And the answer should have been challenged and marks should have been given to both the options B and D. See the discussion between Arjun sir and Venkat sai below.

 

---

Is there any proof of that ??

---

B

Answer 1

ANSWER SHOULD BE D!!

Here’s how: Let’s assume a Circular Queue of size-4 having elements a,b,c,d

a

b

c

d

 

Now assume front is pointing to ‘a’ and rear is pointing to ‘d’, then if we dequeue then a will be dequeued and again then b will be dequeued.

So now circular queue will look like this,

c

d

Where Front is pointing to c and rear is pointing to d.

Now if we enqueue f and g then it will change like this

c

d

f

g

Where front is pointing to c and rear is pointing to g.

Now to implement via Singly linked list we really don’t need any extra thing rather than front pointing to front node of the list and rear pointing to last and rear’s next pointing to null.

First we will have a->b->c->d ,Front =a and Rear=d.

then we will do 2 dequeue then it will be just c->d, Front at c and Rear at d.

 then if we do 2 enqueue then c->d->f->g.

Front at c and rear at g.

So Simply L.L code will look like this to Implement Circular Queue.

Enqueue Via L.L:                                    Dequeue Via L.L:

 

Rear->next=New;                      Temp=front;

New->next=Null;                        Front=Front->next;

Rear=new;                                 Free(temp);

 

So Rear does not require to point to Front and Front Does not require to point to Rear, SO ANSWER SHOULD BE D!!

Answer 2

Adding avalue:- 

Rear ->next = new;

 

Rear= Rear ->Next;

 

Rear->next= Front;

 

Delete avvalue:- 

Rear->next = Front->next;

 

Front = Front->next;

Solution

Answer 3

Can anyone explain this question pictorially, so that I can visualize the concept of the question.