edited by
30,722 views
55 votes
55 votes

A circularly linked list is used to represent a Queue. A single variable $p$ is used to access the Queue. To which node should $p$ point such that both the operations $\text{enQueue}$ and $\text{deQueue}$ can be performed in constant time?

  1. rear node
  2. front node
  3. not possible with a single pointer
  4. node next to front
edited by

8 Answers

Best answer
119 votes
119 votes

The pointer points to the Rear node.

EnQueue: Insert newNode after Rear, and make Rear point to the newly inserted node: 

//struct node *newNode;
newNode->next = rear->next;
rear->next = newNode;
rear=newNode;

DeQueue: Delete the Front node, and make the second node the front node.

//rear->next points to the front node.
//front->next points to the second node.
struct node* front;
front = rear->next;
rear->next = front->next;
free(front);


Since there has been a lot of confusion in the comments, let me explain the answer using the pointer `p`

Note that the answer remains unchanged – the below code is just written in a different style.

struct node *p; // a pointer to the rear node

void enqueue(struct node *item) {
    item->next = p->next;
    p->next = item;
    p = item;
}

void dequeue() {
    struct node* temp = p->next;
    p->next = p->next->next;
    free(temp);
}

 

A single variable $p$ is used to access the Queue

This means that the data-structure only tracks the rear node.

You can create as many temporary pointers as you want – that has nothing to do with the data-structure’s internals.

In enqueue, there’s an extra pointer struct node *item because if you wish to enqueue something, you need that thing in the first place.

In dequeue, there’s an extra pointer struct node *temp because if you don’t keep track of the thing that you’re removing in order to free the memory, you will have a memory leak in your code.

edited by
19 votes
19 votes

The pointer points to the Rear node.


EnQueue: Insert newNode after Rear, and make Rear point to the newly inserted node:

//struct node *newNode;
newNode->next = p->next;
p->next = newNode;
rear=newNode;

DeQueue: Delete the Front node, and make the second node the front node.

rear->next = rear->next->next;
7 votes
7 votes

Answer should be A.

P should point to Last node(rear), so as to perform enqueue in constant time.

To perform dequeue operation, since it is circular linked list, rear node will point front. Therefor dequeue can be performed as below:

temp= p->next->next//stores the address of node next to front node.

Delete (p->next)// delete current front node

p->next= temp// update the rear node to point to new front node.

Thus dequeue can also be perform in constant time.

edited by
0 votes
0 votes
answer should be C

enqueue is possible with 1 pointer but for dequeue we have to take 1 more pointer bcoz if dequeue compulsory we have to free the memory also which is not possible with only 1 pointer.if modify then we can do whatever we want but in dequeue free the memory also.

@ arjun sir plz verify
Answer:

Related questions

62 votes
62 votes
4 answers
1
103 votes
103 votes
11 answers
2
27 votes
27 votes
3 answers
4
Kathleen asked Sep 18, 2014
8,743 views
Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?preorder and postorderi...