Scribd
Upload
8 views

Queue Using Linked List

The document describes a queue implementation using a linked list to address the limitations of array-based queues, such as fixed size and garbage values. It outlines the structure of a node, the FIFO mechanism, and provides algorithms for adding, deleting, and traversing elements in the queue. A sample C program is included to demonstrate the queue operations.

Uploaded by

srinu vas
Copyright
© © All Rights Reserved
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
8 views

Queue Using Linked List

The document describes a queue implementation using a linked list to address the limitations of array-based queues, such as fixed size and garbage values. It outlines the structure of a node, the FIFO mechanism, and provides algorithms for adding, deleting, and traversing elements in the queue. A sample C program is included to demonstrate the queue operations.

Uploaded by

srinu vas
Copyright
© © All Rights Reserved
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

Queue using linked list:

 To overcome the queue array drawbacks that is


1. Fixed size
2. Garbage values
 In queue using linked list the elements are in the form of nodes, a node which contains two
parts, the part is data part which stores a value and second part is address part which stores
the address of another variable
 Queue linked list also follows the FIFO mechanism
 In queue using linked list adding of an element, we use rear variable and deleting of an
element front variable

Algorithm on Queue using Linked list:

Step -1: create a node in Queue linked list

struct node
{
int data;
struct node*next;
};
struct node *front=NULL;
struct node *rear=NULL;
Step -2: addQ / enQueue:

Adding an element into the queue linked list

Step -1: Create a newNode with given value

Step-2: Check whether list is empty (front==NULL && rear == NULL)

Step -3: If it is Empty then, set newNode->next=NULL and front = newNode, rear =newNode

Step -4: If it is not Empty then, set rear->next=newNode, rear=newNode and newNode-
>next=NULL.

Step – 2: delQ() / deQueue()

Deleting / removing an element from the queue linked list

Step-1: check whether list is Empty (front==NULL && rear == NULL)

Step -2: if it is empty then, display ‘Queue list is empty!!! Deletion is not possible” and
terminate the function

Step -3: if it is not empty then, define a node pointer temp and initialize with front

Step -4: check whether list is having only one node(temp->next ==NULL)

Step -5: if it is true then set front =NULL, rear=NULL and delete temp

Step -6: if it is false then set front= temp->next, temp->next=NULL and delete temp
Step-3: Traversal()

Traversal means visiting each node in sequence.

Step -1: check whether list is empty (front==NULL && rear == NULL)

Step -2: if it is empty then, display ‘Queue list is empty!!!’ and terminate the function

Step -3: if it is not empty then, define a node pointer temp and initialize with front

Step -4: keep displaying temp->data with arrow (--) until temp reaches to the last node

Step -5: finally display temp->data with arrow pointing to NULL (temp->data-NULL)

Program:

// implements queue using linked list


#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *front =NULL;
struct node *rear =NULL;

void addQ(int ele);


void delQ();
void traverse();

void addQ(int ele)


{
//node memory allocation
struct node *newnode=(struct node*)malloc(sizeof(struct node));
if(front == NULL && rear == NULL)
{
newnode->data =ele;
newnode->next =NULL;
front=newnode;
rear=newnode;
}
else
{
newnode->data=ele;
newnode->next=NULL;
rear->next=newnode;
rear=newnode;
}
printf("insertion successfully...\n");

}
void delQ()
{
struct node *temp;
temp=front;
if(front == NULL && rear == NULL)
{
printf("Queue list is empty!!! Deletion is not possible\n");
}
else if(front->next==NULL) //check whether list is having only one node
{
front = NULL;
rear = NULL;
printf("deletion successfully...\n");
}
else
{
front = temp->next;
temp->next = NULL;
printf("deletion successfully...\n");
}

}
void traverse()
{
struct node * temp;
temp = front;
if(front == NULL && rear == NULL)
{
printf("Queue is empty..\n");
}
else
{
while(temp->next!=NULL)
{
printf("%d-->",temp->data);
temp=temp->next;
}
printf("%d-->NULL\n",temp->data);
}

}
void main() {
int choice,ele;
clrscr();
while(1)
{
printf("************ Queue menu ************\n");
printf("\n 1.addQ \n 2. delQ \n 3. traverse \n 4. exit \n");
printf("Choose one: ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("enter a value to insert");
scanf("%d",&ele);
addQ(ele);
break;
case 2: delQ();
break;
case 3: traverse();
break;
case 4: exit(0);
break;
default: printf("\nInvalid choice (1-4)\n");
}
}

getch();

You might also like