Priority Queue using Doubly Linked List

pq.cpp

/**
 *  Priority Queue using Doubly Linked List
 *  Auther : Syed Zain Ul Hasan
 *  01-134132-185
 *  BS(CS) 4A
 *  Bahria University Islamabad.
 *  [email protected].
 *
 **/


#include <iostream>
#include<stdlib.h>
#include<string>

using namespace std;



/**
 *
 * Defining Node class to hold data of student.
 *
 */

class Node
{
public:

	// Defining variables for class.

	int Priority;
	int roll_number;
	string name;
	string phone;
	float cgpa;



	//Node pointers to store address of next and last node.

	Node *next;
	Node *previous;


	//Constructor to set values passed as arguments.

	Node(int p, int r, string n, string ph, float c)
	{


		Priority = p;
		roll_number = r;
		name = n;
		phone = ph;
		cgpa = c;


		next = NULL;
		previous = NULL;
	}

};

//Defining d_link_list class.

class d_link_list
{

//Pointers to hold address of first and last node in linked list.

private:
	Node *first;
	Node *last;

public:

	d_link_list()
	{

		first = last = NULL;
	}



	/**
	 * Insert Function.

	 * 1-Define three nodes one that will be inserted in linked list second to find node with
	 *  highest priority and last to point the second with the hight priority node.
	 * 2-Traverse through Linked List and find node with highest priority.
	 * 3-Insert new Node in between second and third  node.
	 *
	 */

	void insert(int p, int r, string n, string ph, float c)
	{

		Node *newNode = new Node(p, r, n, ph, c);
		Node *curr = first;
		Node *prev = curr;

		if(curr == NULL)
		{

			first = last = newNode;
			delete curr;
			delete prev;

		}
		else
		{


			while(curr != NULL && curr->Priority <= p)
			{

				prev = curr;
				curr = curr->next;

			}

			prev->next = newNode;
			newNode->previous = prev;
			newNode->next = curr;






		}
	}




	/**
	 * Pop Function.

	 * 1-Define a node and assigned address of head node.
	 * 2-Traverse through Linked List and find second last node of linked list.
	 * 3-Delete last node and set second last node as last node.
	 *
	 */



	void pop()
	{



		Node *tmp = first;

		while(tmp->next->next != NULL)
		{

			tmp = tmp->next;

		}


		tmp->next = NULL;
		last = tmp;


	}


	/**
	 * Display Function
	 *
	 * 1-Traverse through Linked List and display value of data in every Node.
	 *
	 */


	void display()
	{

		Node *tmp = first;

		while(tmp != NULL)
		{

			cout << "Priority :" << tmp->Priority << endl;
			cout << "Roll Number :" << tmp->roll_number << endl;
			cout << "Name :" << tmp->name << endl;
			cout << "Phone :" << tmp->phone << endl;
			cout << "CGPA :" << tmp->cgpa << endl;
			cout << endl;
			cout << endl;
			tmp = tmp->next;
		}
	}

};


int main(int argc, char** argv)
{
	d_link_list d;


	cout << "\t\tPriority Queue Implementation using Linked List" << endl << endl;


	//Inserting some random values in linked list.

	d.insert(1, 185, "Syed Zain Ul Hasan", "0300-0012541", 3);
	d.insert(4, 193, "Usama Ahmad", "0300-5555", 3.5);
	d.insert(3, 021, "Aizad Raza", "0300-54522", 3.52);
	d.insert(10, 057, "Rahim Ullah", "0300-5555", 4.1);

	//Display Function called.

	d.display();



	//Pop Function called.
	d.pop();
	cout << endl;
	cout << endl;
	d.display();


	system("pause");
	return 0;
}