-
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 en-queue and dequeue can be performed in constant time?
-
- Rear node
- Front node
- Not possible with a single pointer (d)
- Node next to front
- Rear node
Correct Option: A
Answer is not “(b) front node”, as we cannot get rear from front in O(1), but if P is rear we can implement both enqueue and de-Queue in O(1) because from rear we can get front in O(1). Below are sample functions. Shows The pointer points to the rear node : -
Enqueue :- Insert new node after rear, and make rear point to the newly inserted node :
Struct Node * New Node;
New Node → Next = Rear → Next,
Rear → Next = New Node;
Rear = New Node;
Dequeue :- Delete the front node, and make the second node the front node.
Rear → Next points to the front node.
Front → Next points to the second node.
Struct Node * Front;
Front = Rear → Next;
Rear → Next = Front → Next;
Free (front);
