Class notes AIDS Stacks and Queue

Data Structures



UNIT-II
Queues
Queue:
Queue is an ordered collection of items from which items may be deleted at one end
(called the front of the Queue) and into which items may be inserted at the other end (called
rear of the Queue).
The first inserted element into the Queue is the first deleted element. For this reason, a Queue is
sometimes called First-In-First-Out (FIFO).

Array representation of Queue:
Use an array to hold the elements of the Queue and to use two variables, front and rear to hold
the positions within the array of the first and last elements of the Queue.
#define max 10
struct queue
{
int items[max];
int front, rear;
};
struct queue q;
Initially q.front = 0; and q.rear = -1;
The queue is empty whenever q.front > q.rear.
No of elements in Queue = q.rear – q.front + 1;

Operations on Queue:

Empty operation;
int empty(struct queue *q)
{
if(q→rear < q→front)
return 1;
else
return 0;
}

Insert operation:
Using an array to hold a queue, check overflow condition.

void insert(struct queue *q, int a)
{
if(q→rear = = max-1)
printf(“\nQueue is overflow”);
else

K SRINIVAS DEPT OF IT SRKREC 1

,Data Structures


{
q→rear++;
q→items[q→rear] = a;
}
}

Remove operation:
Check empty condition.
int remove(struct queue *q)
{
int a;
if(q→rear < q→front)
return -1;
else
{
a = q→items[q→front];
q→front++;
return a;
}
}

Peek operation:
int peek(struct queue *qu)
{
if(qu->front>qu->rear)
return -1;
else
return(qu->items[qu->front]);
}

/*queue operations using Array program*/
/*queue operations using Array*/
#define max 10
#include<stdio.h>
struct queue
{
int front,rear;
int items[max];
};
void insert(struct queue *,int);
int del(struct queue *);
int empty(struct queue *);
int peek(struct queue *);

K SRINIVAS DEPT OF IT SRKREC 2

, Data Structures


void display(struct queue *);
main()
{
int choice,x;
struct queue q;
q.front=0;
q.rear=-1;
while(1)
{
printf("\n\n***************************\n\n");
printf("\t\tMENU\n");
printf("\n***************************\n");
printf("1.insert\n2.delete\n3.empty\n4.peek\n5.display\n6.exit\n");
printf("Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:printf("\nEnter the element:");
scanf("%d",&x);
insert(&q,x);
printf("\nElements are:");
display(&q);
break;
case 2: x=del(&q);
if(x==-1)
printf("\nqueue is empty");
else
printf("\ndeleted element is %d",x);
printf("\nelements are:");
display(&q);
break;
case 3: x=empty(&q);
if(x==1)
printf("\nqueue is empty");
else
printf("\nqueue is not empty");
break;
case 4: x=peek(&q);
if(x==-1)
printf("\nQueue is empty");
else
printf("\nFront element is:%d",x);
break;

K SRINIVAS DEPT OF IT SRKREC 3