How does this enqueue function work?

Question

I am having trouble understanding this line:

rear->next = temp; 

in this queue function:

  void Queue::enqueue(int data) { Node *temp = new Node(); // make a temporary node temp->info = data; // assign passed in data to it temp->next = 0; // make it point to null if(front == 0) // if there is no front node front = temp; // make this a front node else // else, if there is already a front node rear->next = temp; // make this rear next pointer???? why? rear = temp; // in any case make this a rear node } 

Wouldn't it make sense to do that?

  else // else, if there is already a front node temp->next = rear; // make temp point to REAR; not other way around rear = temp; // make temp a new rear node 

Answer 1

rear indicates the last element. You want to place temp after the current rear , and then move rear to point to the recently placed last element. So, if we wanted to queue 4 in the queue (1, 2, 3) , we want:

 1 -> 2 -> 3 -> 4 | | front rear 

Your solution allows temp cut in front of the current rear , and then move the rear to the cutout position. It doesn't even cut properly, because the element in front of the rear still points to the original rear . rear no longer points to the last element, and your queue will be in an inconsistent state.

 1 -> 2 -> 3 | 4 -^ | | front rear 

Answer 2

This code makes sense to me

 if(front == 0) front = temp; 

This means that the queue is empty. Add your element and make the forefinger a single element. You already understand that.

 else rear->next = temp; 

else, there are already items in the queue. So, go to the last element, at the back, and place the new element in the very back. Now this is a new rear. The old back pointer now points to your new rear.

 rear = temp; 

Make the new rear official!

Answer 3

This simple queue example will help you understand how enqueue works.

 #include<iostream> #include<cstdlib> using namespace std; struct node{ int info; struct node *next; }; class Queue{ private: node *rear; node *front; public: Queue(); void enqueue(); void dequeue(); void display(); }; Queue::Queue(){ rear = NULL; front = NULL; } void Queue::enqueue(){ int data; node *temp = new node; cout<<"Enter the data to enqueue: "; cin>>data; temp->info = data; temp->next = NULL; if(front == NULL){ front = temp; }else{ rear->next = temp; } rear = temp; } void Queue::dequeue(){ node *temp = new node; if(front == NULL){ cout<<"\nQueue is Emtpty\n"; }else{ temp = front; front = front->next; cout<<"The data Dequeued is "<<temp->info; delete temp; } } void Queue::display(){ node *p = new node; p = front; if(front == NULL){ cout<<"\nNothing to Display\n"; }else{ while(p!=NULL){ cout<<endl<<p->info; p = p->next; } } } int main(){ Queue queue; int choice; while(true){ cout<<"\n1.Enqueue\n2. Dequeue\n3. Display\n4.Quit"; cout<<"\nEnter your choice: "; cin>>choice; switch(choice){ case 1: queue.enqueue(); break; case 2: queue.dequeue(); break; case 3: queue.display(); break; case 4: exit(0); break; default: cout<<"\nInvalid Input. Try again! \n"; break; } } return 0; }