23 votes

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?

- Next pointer of front node points to the rear node.
- Next pointer of rear node points to the front node.

- (I) only.
- (II) only.
- Both (I) and (II).
- Neither (I) nor (II).

1

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.

0

0

As insertion takes place from the rear side, so the next node to rear must point to the front node, to be a circular queue. I think this is the logic in simple terms.

0

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.

10 votes

Best answer

https://gateoverflow.in/1033/gate2004-36 Found from Comments.

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$

27 votes

0

@Arjun Sir... To perform the enque deque operations IN CONSTANT TIME, just the front and rear pointers are required( necessary) and the question asks how can we perform these operations in constant time...we don't require the next pointer of rear to point to front necessarily...even without this constant time operations can be achieved...then why is the answer (b) and not (d)? :(

3

Sir, I think we can enqueue and dequeue in O(1) without using any extra pointers(other than FRONT and REAR). Here's how: (Correct me if I'm wrong)

a->b->c->d

this is the queue and FRONT is pointing to a and REAR is pointing to d.

To delete an element (i.e. only from the front end): FRONT should now point at a->next, i.e. b

And for insertion (i.e. at the rear end): Create a new node, REAR element should now point at this new element, i.e. d -> e (e is the new element), and REAR now points to e.

a->b->c->d

this is the queue and FRONT is pointing to a and REAR is pointing to d.

To delete an element (i.e. only from the front end): FRONT should now point at a->next, i.e. b

And for insertion (i.e. at the rear end): Create a new node, REAR element should now point at this new element, i.e. d -> e (e is the new element), and REAR now points to e.

1

@Arjun sir dont u think that this question is ambiguous as with simple linked list implementation of queue alone we can do both insertion and deletion in O(1) time and they told that we have a circular queue and they are asking about the property of circular queue which they expect it to have here even if the rear pointer doesnt point to front we can do both in O(1) .

0

in any queue implementation we have both front and rare pointers

/*Queue - Linked List implementation*/ #include<stdio.h> #include<stdlib.h> struct Node { int data; struct Node* next; }; // Two glboal variables to store address of front and rear nodes. struct Node* front = NULL; struct Node* rear = NULL; // To Enqueue an integer void Enqueue(int x) { struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->data =x; temp->next = NULL; if(front == NULL && rear == NULL){ front = rear = temp; return; } rear->next = temp; rear = temp; } // To Dequeue an integer. void Dequeue() { struct Node* temp = front; if(front == NULL) { printf("Queue is Empty\n"); return; } if(front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); } int Front() { if(front == NULL) { printf("Queue is empty\n"); return; } return front->data; } void Print() { struct Node* temp = front; while(temp != NULL) { printf("%d ",temp->data); temp = temp->next; } printf("\n"); } int main(){ /* Drive code to test the implementation. */ // Printing elements in Queue after each Enqueue or Dequeue Enqueue(2); Print(); Enqueue(4); Print(); Enqueue(6); Print(); Dequeue(); Print(); Enqueue(8); Print(); }

@Arjun sir see this

1

@Venkat Yes, it is possible in simple queue. Circular queue is an extension of simple queue for better space utilization and the question is specifically for circular queue.

15

sir circular queue is used in case of arrays only as we for example if we continuosly enqueue elements and then dequeue elements into the queue in case of array the locations before the front pointer cannot be accesed but in case of linked list we need not use a circular queue because we have dynamically allocated memory and we free the space after the dequeue the elements and hence there is no waste of space and making a circular queue will not make changes in time complexity here but it would be nice if he says his perception about a circular queue in the question what he thinks as a circular queue with linked list but unfortunately that itself would be the answer :( there is no logic in this question what do u say @Arjun sir

3

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/

0

@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

9 votes

**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

3

**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 ...

6 votes

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

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

2 votes

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).

0

I think II stmt may be correct. They are asking which stmt(if assumed correct) will allow insertion and deletion to be done in constant time. I.e sufficient condition. Though what have u said is also correct. I also thought so in the exam. II stmt(if assumed coorect) will not prohibit the enque and deque in const time.

0

If rear points to the front, then the condition for buffer being full is satisfied , and hence we can't perform enqueue.

0

I suppose so. But can't we ignore this condition since we are using infinite buffer(linked list) and both ADT of circular queue(or queue) can still be implemented in constant time while satiafying enqueue and dequeue rules(i.e insertion done at rear and deletion done from front)

0

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.

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

1 vote

question asks "which of the following statements is/are correct for a circular queue, so that insertion and deletion CAN be performed in O(1) time?"

Both operations can be performed in O(1) time only in one case, where the list contains exactly 1 element i.e. where front and rear both points to the same element and so do their `next`

pointer.

Therefore both statements must be correct in order to achieve O(1) time complexity for both insert and delete.

C must be the answer

EDIT: Sorry, both insertion and deletion can be performed in O(1) time in any regular circular queue. So rear just needs to point to front. That's it. Hence (II) is correct. B is the answer

1 vote

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**