# GATE2017-2-13

23 votes
13.5k views

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.
1. (I) only.
2. (II) only.
3. Both (I) and (II).
4. Neither (I) nor (II).
in DS
edited
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
According to yr explanation option A should be same then ,why are u going for option D
0
Can anyone explain this question pictorially, so that I can visualize the concept of the question.
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.

## 9 Answers

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$

edited
27 votes

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

Hence, only (II) is correct.

4
Why isn't the answer option(d) since we only need just front and rear pointers and nothing else?
0
@Bongbirdie what do you mean by that statement that we do not need anything else?
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)? :(
0
Then show it via code.
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.
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) .
2
If you say "can be done", please show it via code or at least an algorithm.
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
9
yes, by GATE standard this is a poorly framed question.
3

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

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

0
@Venkat Sai

I really like your comment.
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

0
can u explain wat u hav done ... i am nt getting ur enqueue operation ...
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

edited
0
I agree with you.
0
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??
0
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.
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).

edited
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.
0
Lets see what they come up with in the  answer key.
0
@fauzdar65 ... but answer is given option B.... and also explain that how we'll have Our(1)operation always?
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

edited
1 vote

Answer is B

It is circular linked list implementation for Queue

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

0
This is really Ambiguous. Many would have lost unnecessary marks.Such questions do make me nervous before Gate 2021.π
Answer:

## Related questions

24 votes
5 answers
1
4.6k views
The pre-order traversal of a binary search tree is given by $12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20$. Then the post-order traversal of this tree is $2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20$ $2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12$ $7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12$ $7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12$
16 votes
5 answers
2
11.7k views
What is the minimum number of stacks of size $n$ required to implement a queue of size $n$? One Two Three Four
0 votes
2 answers
3
189 views
Which of the following is useful in traversing a given graph by breadth first search? Stack Set List Queue
0 votes
1 answer
4
265 views
If queue is implemented using arrays, what would be the worst run time complexity of queue and dequeue operations? $O(n),O(n)$ $O(n),O(1)$ $O(1),O(n)$ $O(1),O(1)$