Bissoy.com
Doctors Medicines MCQs Q&A

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 near 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? I. Next pointer of front node points to the rear node. II. Next pointer of rear node points to the front node.

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 near 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? I. Next pointer of front node points to the rear node. II. Next pointer of rear node points to the front node. Correct Answer II only

Solution:

Concept:

In a queue, elements are deleted from front and inserted from rear end. Whenever a new element is inserted, rear is incremented.

Explanation:

Diagram

[ alt="F1 R.S Deepak 09.12.2019 D3" src="//storage.googleapis.com/tb-img/production/19/12/F1_R.S_Deepak_09.12.2019_D3.png" style="width: 387px; height: 116px;">

So, in case of a circular queue to make an insert and delete operation in O (1) time, the rear pointer will point to the next node i.e. front node. After storing this pointer rear will point to the newly created node.

For enqueue: struct node *ptr

ptr -> next = rear -> next;

rear -> next = ptr

rear = ptr

For dequeue: ptr(front node)

rear -> next = front ->next

ptr = front

front =rear -> next

free(ptr)

Important Points:

For above enqueue and dequeue,

Assume linked list contains more than one element

Structure:

struct node

{

int data;

struct node *next;

}

Related Questions

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let enqueue be implemented by inserting a new node at the head, and dequeue be implemented by deletion of a node from the tail. Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?
Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?
In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into a NONEMPTY queue?
In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into EMPTY queue?
Consider a singly linked list of the form where F is a pointer to the first element in the linked list and L is the pointer to the last element in the list. The time of which of the following operations depends on the length of the list?
A Double-ended queue supports operations such as adding and removing items from both the sides of the queue. They support four operations like addFront(adding item to top of the queue), addRear(adding item to the bottom of the queue), removeFront(removing item from the top of the queue) and removeRear(removing item from the bottom of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What are the total number of stacks required for this operation?(you can reuse the stack)
Consider a single linked list where F and L are pointers to the first and last elements respectively of the linked list. The time for performing which of the given operations depends on the length of the linked list ?
A double-ended queue supports operations like adding and removing items from both the sides of the queue. They support four operations like addFront(adding item to top of the queue), addRear(adding item to the bottom of the queue), removeFront(removing item from the top of the queue) and removeRear(removing item from the bottom of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What’s the time complexity of performing addFront and addRear? (Assume ‘m’ to be the size of the stack and ‘n’ to be the number of elements)
In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?
Consider a standard circular queue ‘q’ implementation (which has same condition for queue full and queue empty) whose size is 11 and the elements of the queue are q[0], q[1], .... q[10]. The front and rear pointers are initialized to point at q[2]. In which position will the ninth element be added ?