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

 

ENQUEUE(x)   \( \text{REAR.next} = \text{temp} \)     // link new node after REAR   \( \text{REAR} = \text{temp} \)     // update REAR   \( \text{REAR.next} = \text{FRONT} \)    // maintain circular connection

DEQUEUE()   \( \text{FRONT} = \text{FRONT.next} \)     // move FRONT forward   \( \text{REAR.next} = \text{FRONT} \)     // maintain circular connection

---

• Both operations maintain the circular link with \( \text{REAR.next} = \text{FRONT} \).
• Edge cases like empty or single-element queue are ignored here for simplicity.

---

In a circular queue implemented using a linked list,

• Insertion (Enqueue): Add a new node after REAR, update REAR, and keep the link from REAR to FRONT to maintain circularity.
   
• Deletion (Dequeue): Move the FRONT pointer to the next node and update REAR.next to the new FRONT.

---

but if option b is correct then it will become circular linked list not singly linked list??

---

@Rachuri_Shashikanth

I suppose you meant it as "Circular queue" and not SLL but you don't have to make the question too complicated since the 1st option generally cannot be the case due to it's breaking of link(unless only 2 nodes where it is just a SLL)...2nd option we see that the underlying data structure is a Circular Linked List and the ADT being implemented is a Circular Queue

 

Answer 1

Reference: https://gateoverflow.in/1033/gate2004-36

This is how the things look.

We do insertion by cutting in between Rear and Front and we do deletion by forwarding the Front pointer and updating the Rear accordingly.

Correct Answer: $B$

Comments

You are right, because if we dequeue an element from your first drawn option, we will not be technically implementing any circular queue at all! So, that's right, the first option is not at all possible!

---

can  there  be  special condition in which  1st  statmeent  is  true when like  ideally only 2nd should be true but lets say only two nodes are there this makes next of front the rear in that case then    what would   you say   ?

---

this same question is asked in past but asked where need to put pointer p such that we can insert and delete element in constant time

Answer 2

Answer is Next pointer to Rear node has Pointer to Front node.

Hence, only (II) is correct.

Comments

Maybe, they meant about "ring" property of circular queue that option (b) is correct.

Ref : http://basicdatastructures.blogspot.in/2007/12/circular-queue-data-structure.html

http://www.geeksforgeeks.org/circular-queue-set-1-introduction-array-implementation/

---

@Venkat Sai

I really like your comment.

---

@Arjun Sir please help....If we have only two nodes in our queue...then next pointer of the front node will point to rear node....though it will not be always true...but it is a possibility ... as the question says which of the following is/are CORRECT...and question is not saying which of the following is ALWAYS TRUE...I think C is the answer....please correct me if I am mistaking ...and guide me on how to tackle these kinds of ambiguous questions

Answer 3

Answer B

for circular queue using single link list, for enqueue and dequeue operation in O(1) time rear->next should point front

When you create a new node then there should be a pointer which points that newly created node . This pointer is necessary.

For enqueue

pointer->next = rear->next

rear->next=pointer

rear=pointer

 It takes O(1) times

For dequeue

rear->next = front->next

pointer=front ( this extra pointer required to    free the memory  deleted node)

front= rear->next

Free(pointer)

It takes O(1) times

Comments

can u explain wat u hav done ... i am nt getting ur enqueue operation ...

---

For enqueue

pointer->next = rear->next ; // rear -> next is pointing to Front so when we copy pointer->next will point to Front node

rear->next=pointer ; // after storing rear->next in pointer->next , rear->next is pointed to new node which is created.

rear=pointer ; // then updating rear pointer to point new node.

 It takes O(1) times

For dequeue

rear->next = front->next; // rear->next  is pointing to next of Front because we're performing Dequeue...

pointer=front ( this extra pointer required to    free the memory  deleted node) ; // just taking Front node ref into a new pointer to avoid garbage...

front= rear->next ; // updating Front pointer to point newly updated Front node

Free(pointer); // then release pointer memory ... 

Answer 4

Since linked list is a dynamic data structure we don't need to worry about efficient space utilization (as we do in case of implementing circular queue using array). We can perform both enqueue and dequeue in constant time by using only front and rear pointers. Simply the next pointer of rear node points to NULL and next pointer of front node points to the node which was inserted just after front node in the  queue (i.e second element from left in the list). Enqueue is done at rear and dequeue is done from front ,both in constant time. So both options are false.  D should be the answer.

http://googleweblight.com/i?u=http://btechsmartclass.com/DS/U2_T9.html&grqid=wV00kE3q&hl=en-IN

Comments

I agree with you.

---

Ok, by this method you can do both of them in O(1), but how will you maintain circular queue  prop,  which itself means when rear is connected to front... and in ques. it is mentioned that queue is circular and  is not simple got it??

---

circular linked list means that last node points to first node..here rear and front do not neccesarily mean first and last pointer..they can be at any position in the linked list.

Answer 5

Only Front and Rear pointers are enough to enqueue and dequeue in constant time in a circular queue.

Code for it can be easily found with a simple Google search. The heart of the algorithm is:

To enqueue, increment rear and add the element there

To dequeue, delete the element in "front", then increment front.

A circular queue has been implemented 

Question says that the queue is already circular, so we already have everything we need to perform enqueue and dequque in constant time.

Option D is the actual correct answer

---

However, the answer in the official key is Option B.

Option B can be the answer when the question asks what to do to implement enqueue and dequque ninconstant time. Then we do what Option B says, which will make the Queue a circular queue, hence making enqueue and dequue constant time operations.

---

Official answer: B. Actual answer: D

Comments

This is really Ambiguous. Many would have lost unnecessary marks.Such questions do make me nervous before Gate 2021.😑

---

You the only guy who given clearity.

Answer 6

A Circular Queue by definition ,https://en.wikipedia.org/wiki/Circular_buffer , is a Data Structure that uses a circular buffer of fixed size. Each element in this buffer points to the next element. 

Now initially , front and rear point to the same element . Upon insertion , rear moves forward, and upon deletion front moves forward. While trying to insert an element, if rear->next points to front, we know that buffer is full.

This image shows this clearly :

So , it is clear that , rear->next need not be front , and front->next need not be rear, and we will always have O(1) operations.

Therefore , answer is D

Edit: Note, there is a difference between a circular linked list, and implementing a circular queue using a circular linked list. In the first case, last element has to point to first, by definition .

In the second case, we will use a circular linked list, but front and rear have different meaning with respect to the queue and they are different from the first and last of the circular linked list(which will be fixed while front and rear vary).

Comments

Well we can certainly implement a queue that way , but by definition on wikipedia , circular queue has a fixed size buffer not variable sized. If we are to give variable size buffer, then it just becomes a normal queue with rear pointing to front instead of NULL. Advantage of a fixed size buffer is that we can use memory efficiently.

I guess it comes down to what the question setters think about this, how you define a circular queue changes everything.

---

Lets see what they come up with in the  answer key.

---

@fauzdar65 ... but answer is given option B.... and also explain that how we'll have Our(1)operation always?