Queue
A queue is an ordered list in which
all insertions take place at one end called rare end, while the deletions take
place at the other end called front end. A queue is represented as follows:
|
10
|
20
|
30
|
40
|
50
|
.
|
.
|
.
|
.
|
.
|
.
|
|
|
Q[0]
|
Q[1]
|
Q[2]
|
Q[3]
|
Q[4]
|
.
|
.
|
.
|
.
|
.
|
.
|
Q[n-1
|
front=-1 rear=4
Front End
Rear End
The front element (i.e first element)
of the queue is indicated by the pointer F while the rear element is indicated
by the pointer R
Since the insertions are performed at
rear end and deletions are performed at front end, the element can deleted in
the same order in which they were added to the Queue. For eg: in the above
figure, the elements are added in the order 10,20,30. The front element is 10, while
rear element is 30. The first element that can be deleted from the Queue is 10
and the last element to be deleted is 30. Thus the first element inserted into
the Queue is the first element to be deleted .Therefore, Queue is also called (First
in First out) FIFO list.
Queues can be implemented by either
using one dimensional arrays or using linked list. However, the simplest way to represent a
Queue is by using one dimensional array say Q[0…n-1] where ‘n’ is the No. of locations in the
queue. The first element in the queue is
stored at Q[0], second element at Q[1] and nth element is at Q[n-1]. There are two types variables associated
with queue i.e., front and rear variables. Initially, when the queue is empty
front=rear=-1.
Operations
on Queues
1. Insertion:
To insert an element ‘x’ into a queue
Q, first we increment rear by one and then insert new element at Q[rear]. If rear=n-1 then new element cannot be
inserted since queue is full. Hence,
insertion cannot be performed. Before
inserting the element, first we have to check whether rear=n-1 or not. Insertion is possible only when rear is less
than ‘n-1’.
void
Qinsert(int n)
{
if(rear==max-1)
{
printf("Queue is full\n");
}
else
{
rear=rear+1;
Q[rear]=n;
}
}
2. Deletion:
To Delete the front element from the
queue ‘Q’ we increment front by 1.
However, if front=rear then we say queue is empty and deletion cannot be
performed. Thus before deleting the
element from the queue we have to check whether front=rear or not. Deletion is possible only when front is less
than equal to rear.
int Qdelete()
{
int
n;
if(rear==front)
{
printf("Queue is empty\n");
}
else
{
front=front+1;
n=Q[front];
}
return
n;
}
C
Program for implementing Queue
int rear,front,Q[5],max;
void main()
{
int n;
void Qinsert(int);
int Qdelete();
void dispQue();
clrscr();
rear=-1;
front=-1;
max=5;
Qinsert(10);
Qinsert(20);
dispQue();
Qinsert(30);
Qinsert(40);
Qinsert(50);
Qinsert(60);
dispQue();
n=Qdelete();
printf("deleted element=%d\n",n);
n=Qdelete();
printf("deleted element=%d\n",n);
n=Qdelete();
n=Qdelete();
n=Qdelete();
dispQue();
getch();
}
void Qinsert(int n)
{
if(rear==max-1)
{
printf("Queue is full\n");
}
else
{
rear=rear+1;
Q[rear]=n;
}
}
int Qdelete()
{
int
n;
if(rear==front)
{
printf("Queue is empty\n");
}
else
{
front=front+1;
n=Q[front];
}
return
n;
}
void dispQue()
{
int
i;
for(i=front+1;i<=rear;i++)
{
printf("%d ",Q[i]);
}
printf("\n");
}
No comments:
Post a Comment