Queue
A queue refers to
lining up jobs for a computer or device. For example, if you want to print a
number of documents, the operating system or spooler queues the documents by
placing them in a special area called a print buffer or print queue. The
printer then pulls the documents off the queue one at a time. Another term for
this is print spooling. This is often referred to as FIFO (first in, first
out).
The order in which
a system executes jobs on a queue depends on the priority system being used.
Most commonly, jobs are executed in the same order that they were placed on the
queue, but in some schemes certain jobs are given higher priority is know as
priority queue. Queues are common in computer programs, where they are
implemented as data structures coupled with access routines, as an abstract
data structure or in object-oriented languages as classes. Common
implementations are circular buffers and linked lists.
Algorithm
Addition into a queue
procedure Push (var Elem)
{
add
item to the queue q
}
begin
if
rear=n
then
display
queue full
else
begin
rear
:=rear+1;
q[rear]:=Elem;
end
end (of Push)
Deletion in a queue
procedure POP ()
begin
if front = rear
then
display
queue empty
else
begin
front
:= front+1
item
:= q[front];
end
end
(of Pop}
Source Code
#include <stdio.h>
#include <conio.h>
#define MAX 5
int
front,rear;
int
qu[MAX];
void
push()
{
if(rear>=MAX)
{
printf("\n\tQueue
is full\n");
}
else
{
printf("\n\tEnter
an Element : ");
scanf("%d",&qu[rear]);
rear++;
}
}
void
pop()
{
if(front==rear)
{
printf("\n\tQueue
is empty ");
}
else
{
printf("\n\tNumber
popped = %d",qu[front]);
front++;
}
}
void
disp()
{
int
i;
if(front==rear)
{
printf("\n\tQueue
is empty ");
}
else
{
printf("\n\tQueue
List ..");
for(i=front;i<rear;i++)
{
printf("%d ",qu[i]);
}
}
}
void
main()
{
int
ch,num;
rear=front=0;
clrscr();
front=rear=0;
while(ch!=4)
{
printf("\n\t
---- Queue Menu ----\n");
printf("\n\t1.Push\n\t2.Pop\n\t3.Display\n\t4.Exit");
printf("\n\t\tEnter
a Choice : ");
scanf("%d",&ch);
switch(ch)
{
case
1: push();break;
case
2: pop();break;
case
3: disp();break;
case
4: printf("\n\t\tQuit......");
getch();
exit(0);
default
:printf("\n\tInvalid Choice ..\n");
}
}
getch();
}
Circular Queue
In case of a
ordinary queue, the insertion take place from the front end and the deletion
take place from the rear end and the
space of the queue is not utilized for the further storage. Circular Queue can
effectively utilise the memory space. If we have a normal queue and have
deleted some elements from there then empty space is created there and even if
the queue has empty cells then also we cannot insert any new element because
the insertion has to be done from one side only. But in case of circular queue
the front and rear are adjacent to each other.
Source Code
#include
<stdio.h>
#include
<conio.h>
int Cqueue[MAX];
int front,int rear;
//Push
Function
void
Push()
{
if((front
== 0 && rear == MAX-1) || (front == rear+1))
{
printf("\n\tQueue
is Full\n");
return;
}
if(front==-1)
{
front=rear=0;
}
else
if(rear == MAX-1)
{
rear
= 0;
}
else
{
rear
= rear+1;
}
printf("\n\tEnter
the Element : ");
scanf("%d",
&Cqueue[rear]);
}
//Pop
Function
void
Pop()
{
if
(front < 0)
{
printf("\n\tQueue
is Empty\n");
return;
}
printf("\n\tElement
Popped from the Queue :
%d\n",Cqueue[front]);
if(front
== rear)
{
front=-1;
rear
=-1;
}
else
if(front == MAX-1)
{
front
= 0;
}
else
{
front
= front+1;
}
}
//Print the Queue
void
disp()
{
int
frnt = front;
if(front
<0 )
{
printf("\n\tQueue
is empty\n");
return;
}
printf("Elements
in the Queue : ");
if(
frnt <= rear )
{
for(frnt=front;frnt<=rear;frnt++)
{
printf("%d
",Cqueue[frnt]);
}
}
else
{
for(frnt=front;frnt<MAX;frnt++)
{
printf("%d
",Cqueue[frnt]);
}
for(frnt=0;frnt<=
rear;frnt++)
{
printf("%d
",Cqueue[frnt]);
}
}
printf("\n");
}
//Main
Function
void
main()
{
int
ch=0;
clrscr();
rear=front=-1;
while(ch!=4)
{
printf("\n\t1.Push\n\t2.Pop\n\t3.Display\n\t4.Quit");
printf("\n\tEnter
a choice : ");
scanf("%d",&ch);
switch(ch)
{
case
1 :Push();break;
case
2 :Pop();break;
case
3: disp();break;
case 4:
printf("\n\t..Quit...");getch();exit(0);
default:printf("\n\t*
Invalid Option *\n");
}
}
getch();
}
Priority Queue
a priority queue is
an abstract data type which is like a regular queue or stack data structure,
but additionally, each element is associated with a "priority". The
node with highest priority will be popped first. Priority queuing can be used
to manage limited resources such as bandwidth on a transmission line from a
network router.
Source Code
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 5
int
rear,front,qu[MAX],priority[MAX];
void
add()
{
int
i,j,t,t1;
if(rear>=MAX)
{
printf("\n\tQueue
is full. ");
return;
}
printf("\n\n\n\n\tEnter
job name : ");
scanf("%d",&qu[rear]);
printf("\n\tEnter
job priority : ");
scanf("%d",&priority[rear]);
rear++;
for(i=front;i<rear;i++)
{
for(j=front;j<rear-front-1;j++)
{
if(priority[j]>priority[j+1])
{
t=priority[j];
t1=qu[j];
priority[j]=priority[j+1];
priority[j+1]=t;
qu[j]=qu[j+1];
qu[j+1]=t1;
}
}
}
}
void
display()
{
int
i;
if(front==rear)
{
printf("\n\n\t***Queue
is Empty***");
return;
}
printf("\n\t
--- Queue on Priority ---");
printf("\n\t----------------------------
");
for(i=front;i<rear;i++)
{
printf("\n\t\t
%d\t %d",qu[i],priority[i]);
}
}
void
del
{
if(front==rear)
{
printf("\n\n\t\t***Underflow***");
return;
}
printf("\n\n\tElement
Popped = %d.",qu[front]);
front++;
}
void
main()
{
int
ch;
rear=front=0;
clrscr();
printf("\n\t*Queue
Menu*\n");
do
{
printf("\n\n\t1. Push.\n\t2.
Pop.\n\t3. Display\n\t4. Exit");
printf("\n\tEnter
a choice : ");
scanf("%d",&ch);
switch(ch)
{
case
1: add();break;
case
2: del
case
3: display();break;
case
4: printf("\n\t\t.....Quit.....");
getch();
exit(0);
default: printf("\n\t**Invalid Choice
**");
}
}while(1);
getch();
}
No comments:
Post a Comment