Implementation of Queue using Linked List

Implementation of Queue using Linked List

• The main advantage of using linked representation of queues is that there is no limit on the size of the queue. We can insert as many elements as we want in the queue by creating the required number of nodes. If the elements are no longer needed then those the nodes can be removed from the queue.

• The linked representation of the queue is as shown below -

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<stdio.h>

#include<stdlib.h>

#include<conio.h>

/*Declaration of Linked Queue data structure*/

typedef struct node

{

int data;

struct node *next;

}Q;

Q *front, *rear;

void main(void)

{

char ans;

int choice;

void insert();

Q *delet();

void display(Q *);

front=NULL;

rear= NULL;

do

{

printf("\n\tProgram For Queue Using Linked List\n");

printf("\n Main Menu")

printf("\n1.Insert\n2.Delete \n3.Display");

printf("\n Enter Your Choice");

scanf("%d", &choice);

switch(choice)

{

case 1: insert();

break;

case 2:front = delet();

break;

case 3 display(front);

break;

default: printf("\nYou have entered Wrong Choice\n");

break;

}

printf("\nDo you want to continue?\n");

flushall();

ans = getch();

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

getch();

clrscr();

}

Q *get_node(Q *temp)

{

temp =(Q*)malloc(sizeof(Q));

temp->next=NULL;

return temp;

}

void insert()

{

char ch;

Q *temp;

clrscr();

temp = get_node(temp); /* allocates memory for temp node*/

printf("\n\n\n\tInsert the element in the Queue\n");

scanf("%d", &temp->data);

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

{

front= temp;

rear=temp;

else /* attaching other nodes*/

{

rear->next=temp; .

rear = rear->next;

}

}

int Qempty(Q *front)

{

if(front== NULL)/*front is NULL means memory is not allocated to queue*

return 1;

else

return 0;

}

Q *delet()

{

Q *temp;

temp=front;

if(Qempty(front))

{

Note;  Qempty (front) function returns 1 (true). Hence queue is empty.

printf("\n\n\t\tSorry!The Queue Is Empty\n");

printf("\n Can not delete the element");

}

else

{

printf("\n\tThe deleted Element Is %d ",temp->data);

front front->next;/*deleting the front node*/

temp->next = NULL;

free(temp);

}

Note; After delete operation, front is changed. Hence updated front pointer has to be returned from delete function.

return front;

}

void display(Q *front)

{

if(Qempty(front))

printf("\n The Queue Is Empty\n");

else

{

printf("\n\t The Display Of Queue Is \n"); /*queue is displayed from front to rear*/

for(;front !=rear->next;front=front->next)

printf("\t%d ",front->data);

}

getch();

}

Output

Program For Queue Using Linked List

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice1      

Insert the element in the Queue

10

Do you want to continue?

Program For Queue Using Linked List

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice1

Insert the element in the Queue 20

Do you want to continue?

Program For Queue Using Linked List

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice1

Insert the element in the Queue 30

Do you want to continue?

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

Do you want to continue?

Program For Queue Using Linked List

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice2

The deleted Element Is 10

Do you want to continue?

Program For Queue Using Linked List

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice3

The Display Of Queue Is

20 30

Do you want to continue?