Queues:
Queue is a non-primitive linear data structure.
In the queues
insertion can takes place at one end and deletion can take place at other end.
i.e., it is having two ends: front
and rear.
We can insert the elements into the queue by
using rear end and we can delete the element form queue by using front end
Queue follows FIFO(First in First out) principle.
i.e., first element inserted into the queue is to be the first element deleted
from the queue.
Eg:
1
|
2
|
3
|
4
|
5
|
Front rear
Inserting the
element:
1
|
2
|
3
|
4
|
5
|
6
|
Front
rear
Deleting the
element:
2
|
3
|
4
|
5
|
6
|
The basic
operations that can be performed on queue are
(1) To insert an element in a queue.
(2) To delete an element from the queue.
Implementation of queue:
Like stacks, queues can also be
implemented in two ways:
(1) Static implementation (Using arrays)
(2) Dynamic implementation (Using pointers)
If queue is
implemented using arrays, we must be sure about the exact number of elements we
want to store in the queue, because we have to declare the size of the array at
the design time or before the processing starts.
In this case the
beginning of the array will become the front for the queue and the last
location of the array will act as rear for the queue.
Program to implement the queue
using arrays:
#include<stdio.h>
#include<conio.h>
void addque();
void delque();
void display();
int queue[5];
int front,rear;
front=rear=-1;
void main()
{
int choice;
do
{
clscr();
printf("1.inserting
element");
printf("2.deleting
element");
printf("3.display
the elements");
printf("4.exit");
printf("enter
your choice");
scanf("%d",&choice);
switch(choice)
{
case
1:addque();
break;
case
2:delque();
break;
case
3:display();
break;
case
4:exit(0);
}
}while(choice!=4);
}
void addque()
{
int item;
if(rear<4)
{
printf("enter
the number");
scanf("%d",&item);
if(front==-1)
{
front=0;
rear=0;
}
else
{
rear=rear+1;
}
queue[rear]=item;
}
else
printf("queue is
full");
}
void delque()
{
int item;
if(front!=-1)
{
item=queue[front];
if(front==rear)
{
front=-1;
rear=-1;
}
else
front=front+1;
printf("number
deleted is=%d",item);
}
else
printf("queue is
empty");
}
void display()
{
for(int i=front;i<=rear;i++)
printf("%d",queue[i]);
}
Program to implement the queue
using linked list:
Circular Queue:
A circular queue is
one in which the insertion of a new element is done at the very first location
of the queue, if the last location of the queue is full.
In other words, if
we have a queue ‘Q’ of say ‘n’ elements, then after inserting an element last
location of array (i.e., n-1), the next element will be inserted at the very
first location of the array.
It is possible to
insert the new element, if and only if those locations (slots) are empty.
We can say that a
circular queue is one in which the first element comes just after the last
element.
A circular queue
overcomes the problem of unutilized space in linear queues implemented as
arrays.
A circular queue
also has a front and rear to keep the track of elements to ne deleted and
inserted, and therefore to maintain the unique characteristic of queue.
The below
assumptions are made using circular queues:
(1) Front will always be pointing to the first element (as
in linear queue)
(2) If front= rear= -1, the queue will be empty.
(3) Each time a new element is inserted into the queue, the
rear is incremented by one
Rear= rear+1
(4) Each time an element is deleted from the queue the value
of front is incremented by one.
Front= front+1
If we want to
insert an element, then the relation is,
rear= (rear+1)%
MAXSIZE
Queue[rear]=value
Also, if front= (rear+1)% MAXSIZE, then Queue is full.
After deleting an
element every time, the new position of the front is indicating by the
following relation,
front= (front+1)%
MAXSIZE
Implementation of circular queue
using arrays:
Implementation of circular queue
using pointers:
#include<stdio.h>
#include<conio.h>
#define SIZE 5
void addque(int
*arr,int data,int *front, int *rear);
int delque(int
*arr,int *front,int *rear);
void main()
{
int
array[SIZE],front,rear,value,choice;
front=rear=-1;
do
{
printf("1.Add\n
2.Delete\n 3.Display\n 4.exit\n Enter your choice");
scanf("%d",&choice);
switch(choice)
{
case
1: if((front==0&&rear==SIZE-1)||(front==rear+1))
printf("Queue
is full");
else
{
printf("Enter
value to add");
scanf("%d",&values);
addque(array,
value, &front,&rear);
}
break;
case
2: if(front==-1)
printf("Queue
is empty");
else
{
value=delque(array,&front,&rear);
printf("deleted
element is %d",value);
}
break;
case
3: if(front==-1)
printf("Queue
is empty");
else
{
printf("Queue
elements are");
while(front>-1)
{
value=delque(array,
&front,&rear);
printf("%d",value);
}
}
break;
case
4:exit(0);
}
}while(choice!=4);
}
void addque(int *arr,
int data, int *front, int *rear)
{
if(*rear==SIZE-1)
rear=0;
else
{
(*rear)++;
array[*rear]=data;
if(*front==-1)
*front=0;
}
}
int delque(int *arr,
int *front, int *rear)
{
int data;
data=array[*front];
if(*front==*rear)
*frint=*rear=-1;
else if(*front==SIZE-1)
*front=0;
else
{
(*front)++;
return(data);
}
}
No comments:
Post a Comment