Queue

Queue is work on the principal of First-In-First-Out (FIFO), it means first entered item remove first. Queue have two end front and rear, from front you can insert element and from rear you can delete element.

download-1

The process to add an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.

Queue Representation

screenshot_29

Basic Operations

Queue operations may involve initializing or defining the queue, utilizing it and then completing erasing it from memory. Here we shall try to understand basic operations associated with queues −

  • enqueue() − add (store) an item to the queue.

  • dequeue() − remove (access) an item from the queue.

Enqueue Operation

As queue maintains two data pointers, front and rear, its operations are comparatively more difficult to implement than Queue.

screenshot_30

Algorithm for Enqueue

  •  1 − Check if queue is full.

  •  2 − If queue is full, produce overflow error and exit.

  • 3 − If queue is not full, increment rear pointer to point next empty space.

  • 4 − Add data element to the queue location, where rear is pointing.

  •  5 − return success.

Example for Enqueue

screenshot_31

Dequeue Operation

Accessing data from queue is a process of two tasks − access the data where front is pointing and remove the data after access.

screenshot_32

Algorithm for dequeue

  •  1 − Check if queue is empty.

  •  2 − If queue is empty, produce underflow error and exit.

  •  3 − If queue is not empty, access data where front is pointing.

  •  4 − Increment front pointer to point next available data element.

  •  5 − return success.

Example for Dequeue

screenshot_33

Program for Queue

#include
#include

void insert();
void del();
void display();

struct circ
{
int cqueue[5];
};

struct circ cque;
int rear=0,front=-1;

void main()
{
while(1)
{
int num;
clrscr();
printf(“1.Insertionn2.Deletionn3.Displayn0.Exitn”);
printf(“nnSelect Option : “);
scanf(“%d”,&num);
switch(num)
{
case 1:
insert();
break;
case 2:
del();
break;
case 3:
display();
break;
case 0:
exit(0);
break;
default:
printf(“nnInvalid Option “);
}
getch();
}
}

void insert()
{
int item;
printf(“Element : “);
scanf(“%d”,&item);
if(front==(rear+1)%3)
{
printf(“Queue is Full”);
return;
}
if(front==-1)
{
rear=front=0;
}
else
{
rear=(rear+1)%3;
}
cque.cqueue[rear]=item;
printf(“Successfully Insert”);
}

void del()
{
int num;
if(front==-1)
{
printf(“Queue Empty”);
return;
}
else
{
num=cque.cqueue[front];
printf(“Deleted item : %d”,num);
}
if(front==rear)
{
front=-1;
}
else
front=(front+1)%3;
}

void display()
{
int i;
if(front==-1)
{
printf(“Queue Empty”);
return;
}
else
{
printf(“nnItems : “);
for(i=front;i<=rear;i++)
{
printf(” %d”,cque.cqueue[i]);
}
}
}

Output

screenshot_34

Applications of Queue

Queue, as the name suggests is used whenever we need to have any group of objects in an order in which the first one coming in, also gets out first while the others wait for there turn, like in the following scenarios :

  1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.

  2. In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until a service representative is free.

  3. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive, First come first served.