edited by
27,130 views
35 votes
35 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?

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

11 Answers

2 votes
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 by
1 votes
1 votes

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 by
1 votes
1 votes

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

Answer:

Related questions