Linked List based Implementation of Queues

Linked List based Implementation of Queues

• The main advantage in linked representation is that we need not have to worry about size of the queue. As in linked organization we can create as many nodes as we want so there will not be a queue full condition at all. The queue using linked list will be very much similar to a linked list. The only difference between the two is in queue, the left most node is called front node and the right most node is called rear node. And we can not remove any arbitrary node from queue. We have to remove front node always :

• The typical node structure will be,

typedef struct node

{

   int data;

   struct node next;

}Q;

 

• Various operations that can be performed on queue are

1. Insertion of a node in queue

2. Deletion of node from the queue

3. Checking whether queue is empty or not

4. Display of a queue

All these operations are implemented in following C++ program.

C++ Program

/************************************************************************

Program For implementing the Queue using the linked list. The queue full condition will never occur in this program.

************************************************************************/

#include<iostream>

#include<cstdlib>

using namespace std;

//Declaration of Linked Queue data structure

class Lqueue

{

private:

typedef struct node

{

   int data;

   struct node *next;

}Q;

Q*front, *rear;

public:

Lqueue();

~Lqueue();

void create(),remove(),show();

void insert();

Q *delet();

void display(Q *);

};

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The constructor defined

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒*/

Lqueue::Lqueue()

{

   front=NULL;

   rear= NULL;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The create function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒*/

void Lqueue::create()

{

   insert();

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The remove function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒*/

void Lqueue::remove()

{

   front =delet();

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The show function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒*/

void Lqueue::show()

{

   display(front);

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The insert Function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒*/

void Lqueue::insert()

{

   char ch;

   Q *temp;

   clrscr();

   temp =new Q://allocates memory for temp node

   temp‒>next=NULL;

   cout<<"\n\n\n\tInsert the element in the Queue\n";

   cin>>temp‒>data;

   if(front = = NULL)//creating first node

   {

      front= temp;

      rear=temp;

   }

   else    //attaching other nodes

   {

      rear‒>next=temp;

      rear = rear‒>next;

   }

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The QEmpty Function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒*/

int Qempty(Q *front)

{

   if(front = = NULL)

      return 1;

   else

      return 0;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The delet Function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

Q *Lqueue::delet()

{

Q *temp;

temp=front;

if(Qempty(front))

{

   cout<<"\n\n\t\tSorry!The Queue Is Empty\n";

   cout<<"\n Can not delete the element";

}

else

{

   cout<<"\n\tThe deleted Element Is "<<temp‒>data;

   front=front‒>next;

   temp‒>next=NULL;

   delete temp;

}

return front;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The display Function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void Lqueue::display(Q *front)

{

   if(Qempty(front))

      cout<<"\n The Queue Is Empty\n";

   else

   {

      cout<<"\n\t The Display Of Queue Is \n ";

      for(;front‒rear‒>next;front‒front‒>next)

         cout<<" "<<front‒>data;

   }

   getch();

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The destructor defined

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

Lqueue::~Lqueue()

{

   if((front!= NULL)&&(rear!= NULL))

   {

      front=NULL;

      rear=NULL;

      delete front;

      delete rear;

   }

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The main Function

Calls:create,remove,show

Called By:O.S.

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void main(void)

{

   char ans;

   int choice;

   Lqueue Que;

   do

   {

      clrscr();

      cout<<"\n\tProgram For Queue Using Linked List\n";

      cout<<"\n          Main Menu";

      cout<<"\n1.Insert\n2.Delete \n3.Display";

      cout<<"\n Enter Your Choice";

      cin>>choice;

      switch(choice)

      {

      case 1 :Que.create();

            break;

      case 2:Que.remove();

            break;

      case 3:Que.show();

            break;

      default:cout<<"\nYou have entered Wrong Choice"<<endl;

      break;

}

cout<<"\nDo You Want To See Main Menu?(y/n)"<<endl;

ans = getch();

}while(ans = = 'y' || ans = = 'Y');

getch();

}

Output

Program For Queue Using Linked List

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice 1

Insert the element in the Queue

10

Do You Want To See Main Menu?(y/n)

Program For Queue Using Linked List

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice 1

Insert the element in the Queue

20

Do You Want To See Main Menu?(y/n)

Program For Queue Using Linked List

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice 1

Insert the element in the Queue

30

Do You Want To See Main Menu?(y/n)

Program For Queue Using Linked List

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice 1

Insert the element in the Queue

40

Do You Want To See Main Menu?(y/n)

Program For Queue Using Linked List

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice3

The Display Of Queue Is

10 20 30 40

Do You Want To See Main Menu?(y/n)

 

In insert function

• First we will allocate a node called 'temp' with next field assigned with 'Null' value. Suppose we want to insert data 10 then

• Now mark this node as queue's front and rear

• Now next, suppose we want to insert 20 in queue then a new node 'temp' will be created with data 20.

• Then, the queue will be formed by setting appropriate front and rear.

• Then

• Continuing in this fashion we can create a linked queue.

 

In delete function

We assume that a queue is created like this ‒

Simply display a message that "The deleted Element is 10" (i.e. temp → data). Then set front as

 

Review Questions

1. Write suitable routines to perform insertion and deletion operations in a linked queue.

2. Write a set of routines for implementing queue using linked lists.