test question

Question

We wish to implement a double ended queue using link list. The double ended queue must support , the operations of
(i) struct node *push_back(struct node*,struct node * ,int ) - pushing at the end of the list
(ii) struct node *pop_back(struct node* ) -popping for the end of the list
(iii) struct node *push_front(struct node *,struct node *,int) -pushing at the end of the list
(iv) struct node *pop_front(struct node *) -popping from the front of the list

Given below is an incomplete linked list implementation of the functions push_back() and pop_front() 

 

 

Initially both head and rear pointers are initialised to NULL. Choose the correct option that selects the missing statements

1.   S1: rear->next=temp
   S2:rear=temp;
   S3:rear==NULL
   S4:front->next=front
2.   S1:rear->next=temp;
   S2:temp=rear;
   S3:front==NULL
   S4:front=front->next
3.   S1:rear->next=temp;
   S2:rear=temp;
   S3:front==NULL
   S4:front=front->next

Comments

option 3 is matching.

But in the second image,

return head;

should be replaced by

return ptr;

---

yess shaikh bro

Answer 1

Option 3 is correct.

In push_back function, in this linked list representation of queue the condition is for the case when the Queue is empty originally, the else part considers the case when there are nodes so to add a node at the rear, we first add new node next to rear and also make the rear point to the new node 

So, S1:rear->next=temp; 
and S2:rear=temp; 

In pop fu_front function, it is the case when the Queue is empty originally, the else part considers the case when there are nodes so to pop i.e. the underflow condition,

so, if condition is S3:front==NULL 

else simply make the front pointer point to the second (next) node and then delete the first node.

this is done by S4: front=front->next