GATE CSE 2004 | Question: 36

Question

A circularly linked list is used to represent a Queue. A single variable $p$ is used to access the Queue. To which node should $p$ point such that both the operations $\text{enQueue}$ and $\text{deQueue}$ can be performed in constant time?

• A. rear node
• B. front node
• C. not possible with a single pointer
• D. node next to front

Comments

Similar -> https://gateoverflow.in/118253/gate2017-2-13

---

the condition should be given in question that the next of rear points to the front node because that will be the case only when the queue is full.

---

what if there is only one node in linked list?

Answer 1

Answer can be both....if p points to rear then answer is already given

Now the  case if p points to front:

Enqueue:

1.save the data of the node pointed by p in a temp variable.

2.copy the data of new node to the node p is pointing to.

3.copy the data of the temp variable to the new node created

4.make newnode->next=p->next point to the new node

5.make p->next=newnode

6.make p=p->next

 

Dequeue:

1.copy the data of the node in p->next to p.

2.make p->next=p->next->next

Comments

@Arjun sir : please check this

---

If $p$ points to $Front$, the problem will arise when during $deQueue()$. We won’t be able maintain the cyclic nature of linked list in constant time.

Answer 2

We do insertion by cutting in between Rear and Front

and

we do deletion by forwarding Front pointer and updating Rear accordingly. so ans is rear end

Answer 3

ans is c    not possible with a single pointer bcoz any node to point every time cross the circal …!!

Answer 4

I think there is no front or rear pointer here only p pointer so enQueue() and deQueue operation should be this

1.) newNode-->next=p-->next-->next;

2.) p-->next-->next=NULL;

3.) free(p-->next);

4.) p-->next=newNode;

Comments

@One

yes u r right they were not mentioned about rear and front pointers they only give us pointer P