Queue is a linear data structure like stack and linked list. It follows FIFO (First-in, First-out) or LILO (Last-in, Last-out) policy. It has two main operations - enqueue (insert element; can only be inserted at the rear of a queue) and dequeue (remove element; can only be removed from the front of a queue).
I have four USB storage devices each containing some data that I need to copy to hard drive. As an USB port can read data from a single device at a time, so I have organized them in a queue such that each device is served one after the other. Now as queue basically follows “First Come, First Serve” rule, therefore the device with index 0 being the first device to be placed in the queue must be served first and the last placed device with index 3 must be served at the last. This is how queue follows FIFO policy.
Like stack, queue can also be implemented by array and linked list.
Simple array implementation of queue #
#include<stdio.h>
#define MAX 5
typedef struct queue
{
int arr[MAX];
int rear, front;
}queue;
queue q;
void enqueue(int data);
void dequeue(void);
void display(void);
int main(void)
{
int data, choice;
q.front=q.rear=-1;
do
{
printf("\n\n1. Enqueue.\n2. Dequeue.\n3. Display.\n4. Exit.");
printf("\nEnter your choice: ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("\nEnter data: ");
scanf("%d", &data);
enqueue(data);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
return 0;
default:
printf("\nInvalid choice.");
}
}while(1);
}
void enqueue(int data)
{
if(q.front==-1)
q.front=0;
if(q.rear==MAX-1)
printf("\nQueue is Full.");
else
{
q.rear++;
q.arr[q.rear]=data;
printf("\nData inserted.");
}
}
void dequeue(void)
{
if(q.front==-1)
printf("\nQueue is empty.");
else
{
q.front=q.front+1;
printf("\nDeleted value is %d", q.arr[q.front-1]);
}
}
void display(void)
{
int i;
if(q.front==-1)
printf("\nQueue is empty.");
else
{
printf("\nQueue Elements:\n");
for(i=q.front;i<=q.rear;i++)
printf(" %d", q.arr[i]);
}
}
We have used array in simple and usual manner to implement queue but it might not be the efficient. We can’t insert elements into rooms of array where deletion operation took place earlier, therefore memory gets wasted. To learn in details, watch this. So, it would be better to use array in a circular manner where first and last elements are contiguous.
Circular array implementation of queue #
#include<stdio.h>
#define MAX 5
typedef struct queue
{
int arr[MAX];
int front, rear;
}queue;
queue cq;
void enqueue(int data);
void dequeue(void);
void display(void);
int main(void)
{
int data, choice;
cq.front=cq.rear=-1;
do
{
printf("\n\n1. Enqueue.\n2. Dequeue.\n3. Display.\n4. Exit.");
printf("\nEnter your choice: ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("\nEnter data: ");
scanf("%d", &data);
enqueue(data);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
return 0;
default:
printf("\nInvalid choice.");
}
}while(1);
}
void enqueue(int data)
{
if((cq.rear+1)%MAX==cq.front)
{
printf("\nQueue is Full.");
return;
}
else if(cq.front==-1) //if empty
cq.front=cq.rear=0;
else
cq.rear=(cq.rear+1)%MAX;
cq.arr[cq.rear]=data;
printf("\nData inserted.");
}
void dequeue(void)
{
int temp;
temp=cq.arr[cq.front];
if(cq.front==-1)
{
printf("\nQueue is empty.");
return;
}
else if(cq.front==cq.rear)
cq.front=cq.rear=-1;
else
cq.front=(cq.front+1)%MAX;
printf("\nDeleted value is %d", temp);
}
void display(void)
{
int i, element_count, index;
if(cq.front==-1)
{
printf("\nQueue is empty.");
return;
}
else
{
printf("\nQueue Elements:\n");
element_count=(cq.rear+MAX-cq.front)%MAX;
for(i=0;i<=element_count;i++)
{
index=(cq.front+i)%MAX;
printf(" %d", cq.arr[index]);
}
}
}