Queue Implementation using Linked List
A Queue is a FIFO
list that means FIRST IN FIRST OUT. In this type of data structure the
element inserted first is to be taken out first.
The element in the
Queue are added at the one end which is called rear end and the element removed
from the other is called the front end.
Types of Queues
1. Circular Queue
2. De-Queue
3.Priority Queue
4.Multiple Queue
1. Circular Queue:-
When we want to insert a
new element in the queue ,where the space is available but overflow condition
also exist that means REAR= n-1 it is the main drawback of Liner Queue
(a).To resolve this
problem we can choose two situation shift the element to the left to
the left to fill the vacant
space .
(b). Use of circular
queue where first index (front) comes right after the index (rear).
2. De-Queue :-
It is the list in which
the element can be inserted or deleted either from front or rear it is
also known as Head -Tail linked list.
There are two type
of De -Queue:
1. Input restricted De-queue:- In this De -queue
insertion can be done by only one end but deletion can be done by both
end.
2. Output restricted :- In this,Queue deletion can be
done at only one end but insertion at both end.
3.Priority Queue :-
It is a special type of
data structure in which each element assigned with it's priority.
The element with higher
priority will processed before an element which has lower priority,
when two element with
same priority then FCFS rule is applied.
4.Multiple Queue :-
To consesrve memory it
is better efficient to use a multiple Queue where
more than one queue can be used in the same array.
Applications of Queue:
There are following fields where queue are
applied:-
1. They are widely used as waiting list for single share
resources like printer ,disk,plotter,cpu.
2. Queues are also used in playlist for adding songs to
the end and play from front of list.
3.Queues are used in O.S for handling interception.
Queue Implementation using Linked List
#include<stdio.h>
#include<conio.h>
// structure creation
struct Node
{
int data;
struct Node *next;
}
*front = NULL,*rear = NULL;
//prototype
void insert(int);
void del();
void display();
void main()
{
int choice, value;
clrscr();
printf("\n:: Queue Implementation using Linked List ::\n");
while(1){
printf("\n****** MENU ******\n");
printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d", &value);
insert(value);
break;
case 2: del(); break;
case 3: display(); break;
case 4: exit(0);
default: printf("\nWrong selection!!! Please try again!!!\n");
}
}
}
void insert(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode -> next = NULL;
if(front == NULL)
front = rear = newNode;
else{
rear -> next = newNode;
rear = newNode;
}
printf("\nInsertion is Success!!!\n");
}
void del()
{
if(front == NULL)
printf("\nQueue is Empty!!!\n");
else{
struct Node *temp = front;
front = front -> next;
printf("\nDeleted element: %d\n", temp->data);
free(temp);
}
}
void display()
{
if(front == NULL)
printf("\nQueue is Empty!!!\n");
else{
struct Node *temp = front;
while(temp->next != NULL){
printf("%d--->",temp->data);
temp = temp -> next;
}
printf("%d--->NULL\n",temp->data);
}
}
Download source code
'
Int arr[5] int rear=-1; int front=-1;
//header files
#include<conio.h>
#include<stdio.h>
//macro
#define MAX 10
//global variable
int q[MAX];
int r=-1,f=-1;
//user defined functions prototype
void insert(void);
void display(void);
int del(void);
int peek(void);
//drive code
void main()
{
int option ,val;
clrscr();
do{
printf("\n main menu");
printf("\n1:INSERT");
printf("\n2:DISPLAY");
printf("\n3:DELETE");
printf("\n4:PEEP");
printf("\n5:EXIT");
printf("\nenter your option");
scanf("%d",&option);
switch(option)
{
case 1: insert();
break;
case 2: display();
break;
case 3: val=del();
if(val!=-1)
printf("%d delete from queue ",val);
break;
case 4:val=peep();
if(val!=1)
printf("%d element found on front of queue",val);
break;
case 5: exit(0);
default :
printf("not a correct option") ;
}
}
while(option!=5);
getch();
}
// definition of user defined function
void insert(void)
{
int val;
printf("enter element ");
scanf("%d",&val);
if(r==MAX-1)
{
printf("overflow");
}
else
if(r==-1&&f==-1)
f=r=0;
else
{
r++;
q[r]=val;
}
}
// definition of user defined function
void display(void)
{
int i;
if(f==-1||f>r)
printf("underflow");
else
{
for(i=f;i<r;i++)
{
printf("%d",q[i]);
}
}
}
//definition of user defined function
int del(void)
{
int val;
if(f==-1||f>r)
{
printf("under flow");
return -1;
}
else
{
val=q[f];
f++;
if(f>r)
{
printf("all elements deleted");
f=r=-1;
}
return(val);
}
}
int peep(void)
{
if(f==-1||f>r)
{
printf("under flow");
return -1;
}
else
return q[f];
}
Algorithm to Display
Queue
'
Algorithm to insert an element in the Queue:
STEP 1 Allocate memory for newnode and name it as ptr
STEP 2. Set ptr->data=val
STEP 3. If(ptr->next=NULL)
Then
Set F=R=ptr
Set F->next=R->next=NULL
Else
Set R->next=ptr
Set R=ptr
Set
R->next=NULL
[end of if]
STEP 4. EXIT
Algorithm to display Queue:
STEP 1. [initilize] Front=-1,Rear=-1,ptr=NULL
STEP 2. If ptr->Front=NULL or
ptr->Front>ptr->Rear
Print OVERFLOW
GOTO STEP 3
ELSE
While(ptr!=NULL)
Print
ptr->data
Set ptr=ptr->front
STEP 3. EXIT
Algorithm to delete an element in Queue
STEP 1. [initilize] Front=-1,rear=-1,ptr=NULL
STEP 2. If ptr->front=NULL orptr->front>ptr->rear
Print Empty
GOTO STEP 5
[END OF IF]
STEP 3. Set ptr=front
STEP 4. Set front=front->next
STEP 5.free(ptr)
STEP 6.EXIT
QUEUE IMPLEMENATATION USING ARRAY
Int arr[5] int rear=-1; int front=-1;
Initial when the queue is empty, the value of both front and rear will be -1
For insertion ,the value of rear is incremented by 1 and the element is inserted at the rear
position
We can implement Queue with the help of array data structure by using two variable front and rear suppose an array with size 10 at initial stage FRONT=REAR=0
When inserted any value then rear is incremented by one and value could be stored at the position pointed by rear but the front is unchanged
But in the delete operation the front will be incremented by one
//header files
#include<conio.h>
#include<stdio.h>
//macro
#define MAX 10//global variable
int q[MAX];
int r=-1,f=-1;
//user defined functions prototype
void insert(void);
void display(void);
int del(void);
int peek(void);
//drive code
void main()
{
int option ,val;
clrscr();
do{
printf("\n main menu");
printf("\n1:INSERT");
printf("\n2:DISPLAY");
printf("\n3:DELETE");
printf("\n4:PEEP");
printf("\n5:EXIT");
printf("\nenter your option");
scanf("%d",&option);
switch(option)
{
case 1: insert();
break;
case 2: display();
break;
case 3: val=del();
if(val!=-1)
printf("%d delete from queue ",val);
break;
case 4:val=peep();
if(val!=1)
printf("%d element found on front of queue",val);
break;
case 5: exit(0);
default :
printf("not a correct option") ;
}
}
while(option!=5);
getch();
}
// definition of user defined function
void insert(void)
{
int val;
printf("enter element ");
scanf("%d",&val);
if(r==MAX-1)
{
printf("overflow");
}
else
if(r==-1&&f==-1)
f=r=0;
else
{
r++;
q[r]=val;
}
}
// definition of user defined function
void display(void)
{
int i;
if(f==-1||f>r)
printf("underflow");
else
{
for(i=f;i<r;i++)
{
printf("%d",q[i]);
}
}
}
//definition of user defined function
int del(void)
{
int val;
if(f==-1||f>r)
{
printf("under flow");
return -1;
}
else
{
val=q[f];
f++;
if(f>r)
{
printf("all elements deleted");
f=r=-1;
}
return(val);
}
}
int peep(void)
{
if(f==-1||f>r)
{
printf("under flow");
return -1;
}
else
return q[f];
}
Algorithm to insert an element
STEP 1. [initialize] front=-1,rear=-1
STEP 2. Rear=-1
Print OVERFLOW
GO TO STEP 5
[end of if]
STEP 3. If front =-1 and rear=-1
Set front=rear=0
[end
of if]
STEP 4. Set q[rear]=Val
STEP 5. EXIT
Algorithm to Display
Queue
STEP 1. [initialize] front=-1,rear=-1, MAX=10
STEP 2. If front=-1 orfront>MAX-1
Print UNDERFLOW
GOTO STEP
4
[end of if]
STEP 3. Set Val=Q[front]
Set
front=front+1
STEP 4. EXIT
Algorithm to delete an element in Queue
STEP 1. [initilize] Front=-1,rear=-1,MAX=0
STEP 2. If front=-1 or front >MAX-1
Print UNDERFLOW
ELSE
Val=Q[Front]
Front=Font+1
If
front>Rear
Print All
element deleted
Front =Rear=-1
[END OF IF]
STEP 3. EXIT
Post a Comment