Queue is a linear data structure where the elements could be inserted at one end called the “rear” of the queue and could be retrieved from the other end called “front” of the queue.

Queue implements First In First Our (FIFO)/ Last In Last Out  (LILO) Order on its elements, that is elements inserted first into the queue would be retrieved first from the queue and vice-versa.

Typically queue follows FIFO order, but there could a pre-defined priority for the elements that decides the deletion sequence of the queue elements, in such cases the queue does not follow the traditional FIFO order, such queues are termed as Priority Queue.

Basically FIFO queue are also priority queue as the element inserted first into the queue gets the highest priority.

Queue q is an array of size=10 elements. rear is the poition/index of last inserted element intially rear =-1
front is the position/index of last retrived element intially front=0

Insert operation on queue
1.START Insert (Element e)
2.If rear = size -1 Then        ( If rear is the last element index)
3.Display “Queue OVERDERFLOW”
4.Goto END
5.END If
6.rear:=rear+1
7.q[rear]:=e
8.END Insert

Retrieve operation on queue
1.START Retrive()
2.If front>rear Then
3.Display “Queue UNDERFLOW”
4.GOTO END
5.END If
6.Element e:=q[front]
7.front:=front+1
8.Return e
9.END Retrieve

/**************C- Implementation of LINEAR Queue ****************/
The code for implementing Queue is:-LinearQueue

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define size 6

int queue[size];
int front=0,rear=-1;

void insert(int val)
{
if(rear==size-1)
printf(“queue overflow\n”);

rear++;
queue[rear]=val;
printf(“the value is inserted\n”);
}

int retrive()
{
int value;

if(front>rear)
{
//printf(“queue underflow\n”);
return -9999;
}
value= queue[front];
queue[front]=0;
front++;
return value;
}

void display()
{
int i;
for(i=0;i<=rear;i++)
{
printf(“%d\t”,queue[i]);

}
printf(“\n”);

}

void main()
{
int value,choice;
clrscr();
while(1)
{
printf(” press 1 for Insert\n press 2 for Retrive\n press 3 for diplay\n press 4 for exit\n\n”);
printf(“\n enter your choice:”);
scanf(“%d”,&choice);

switch(choice)
{
case 1:
printf(“enter the value which is to be inserted\n”);
scanf(“%d”,&value);
insert(value);
break;

case 2:
value= retrive();
if (value==-9999 || front==0)
printf(“queue underflow\n\n\n”);
else
printf(“the retrive data is %d\n”,value);

break;

case 3:
display();
break;

case 4:
exit(0);
break;

default: printf(“invalid choice\n”);

}//end of switch
}//end of while

//getch();
}

/**************C- Implementation of LINEAR Queue ****************/

Let us consider the following queue type.

type QUEUE is [

ELEMENT ITEM[SIZE]

INTEGER REAR

INTEGER FRONT

]

Let Q is a QUEUE of SIZE = 100 elements, initially Q.REAR:= -1 and Q.FRONT:=0

INSERTION OPERATION for a Linear Queue

1.START OPERATION INSERT (QUEUE S, ELEMENT e)

2.IF  Q.REAR := SIZE-1 THEN

3.DISPLAY “QUEUE OVERFLOW”

4.GOTO END

5.END IF

6.  Q.REAR := Q.REAR + 1    //INCREMENT THE REAR OF THE QUEUE BY 1

7. Q.ITEM [Q.REAR] : = e  //ASSIGN THE ELEMENT AT THE TOP POSITION OF THE QUEUE

8.END OPERATION INSERT

Retrieve operation on queue

1.START OPERATION RETRIEVE (QUEUE Q)

2.IF Q.FRONT>Q.REAR THEN

3.DISPLAY “QUEUE UNDERFLOW”

4.GOTO END

5.END IF

6.ELEMENT e:=Q.ITEM[Q.FRONT]

7.S.FRONT:=S.FRONT+1

8.RETURN e

9.END OPERATION RETRIEVE

/********C- Implementation of LINEAR Queue  Using Pointer*********/

The code for implementing Queue is:- LinearQueueUsingPointer

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define size 6

typedef struct
{
int item[size];
int rear;
int front;
}Queue;

void insert(Queue *qp,int val)
{
if(qp->rear==size-1)
printf(“queue overflow\n”);

qp->rear++;
qp->item[qp->rear]=val;
printf(“the value is inserted\n”);
}

int retrive(Queue *qp)
{
int value;

if(qp->front>qp->rear)
//printf(“queue underflow\n”);
return -9999;

value= qp->item[qp->front];
qp->item[qp->front]=0000;
qp->front++;
return value;
}

void display(Queue *qp)
{
int i;
for(i=0;i<=qp->rear;i++)
{
printf(“%d\t”,qp->item[i]);

}
printf(“\n”);

}

void main()
{
Queue q;
int value,choice;
q.rear=-1;
q.front=0;
clrscr();
while(1)
{
printf(” press 1 for Insert\n press 2 for Retrive\n press 3 for diplay\n press 4 for exit\n\n”);
printf(“\nenter your choice:”);
scanf(“%d”,&choice);

switch(choice)
{
case 1:
printf(“enter the value which is to be inserted\n”);
scanf(“%d”,&value);
insert(&q,value);
break;

case 2:
value= retrive(&q);
if (value==-9999 || q.front==0)
printf(“queue underflow\n\n\n”);
else
printf(“the retrive data is %d\n”,value);

break;

case 3:
display(&q);
break;

case 4:
exit(0);
break;

default: printf(“invalid choice\n”);

}//end of switch
}//end of while

//getch();
}

/********C- Implementation of LINEAR Queue  Using Pointer*********/

Applications:

Typical uses of queues are in simulations and operating systems.

  • Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.
  • Computer systems must often provide a “holding area” for messages between two processes, two programs, or even two systems. This holding area is usually called a “buffer” and is often implemented as a queue.

Our software queues have counterparts in real world queues. We wait in queues to buy pizza, to enter movie theaters, to drive on a turnpike, and to ride on a roller coaster. Another important application of the queue data structure is to help us simulate and analyze such real world queues.

Advertisements