Introduction to Queue Data Structure in C: Implementation, Operations and Algorithm
The queue is a linear data structure used in various applications in computer science. Like people standing in line to get a specific service, the various processes will wait in the queue for their turn to get service. In computer science, this is called First In First Out (FIFO). In most cases, the first customer in the queue is the first to be served.
 |
The Queue is a collection of elements, or items, for which the following operations are defined:
- createQueue(Q) : creates an empty queue Q;
- isEmpty(Q): is a boolean type predicate that returns ``true'' if Q exists and is empty, and returns ``false'' otherwise;
- addQueue(Q,item): adds the given item to the queue Q; and
- deleteQueue (Q, item): delete an item from the queue Q;
- next(Q) removes the least recently added item that remains in the queue Q, and returns it as the value of the function;
- isEmpty (createQueue(Q)) : is always true, and
- Queues deleteQueue(createQueue(Q)) : error
Implementation of Queue
In physical analogy for the queue at the booking counter. the customer adds to the rear(END) of the line and attends the services from the front of the line booking counter. It is unlike Stack in C customer is added at the rear(END) and delete from the front.Link a Stack, Queue also holds data elements of the same type. We usually graphically display a Queue horizontally
The rule followed in Queue is that element added at the rear and come off of the front of the Queue. we can that after the removal of the first element 'a' from the front. the Queue shift the front pointer position to the next element i.e. 'b'
Algorithm for the addition of an element to the queue
Step 1: Create a new element to be added
Step 2: If the queue is empty, then go to step 3, else go to step 4
Step 3: Make the front point and rear point this element
Step 4: Add the element at the end of the queue and shift the rear pointer to the newly added element.
Algorithm for deletion of an element from the queue
Step 1: Check for queue empty condition. If empty, then go to step 2, else go to step 3
Step 2: Message "Queue Empty"
Step 3: Delete the element from the front of the queue. If it is the last element of the queue then perform step 'a' else 'b'
a) make front and rear point null
b) shift the front pointer ahead to point to the next element in that queue
Code for Array implementation of a Queue
#include "stdio.h"
#define QUEUE_LEN 10
struct queue
{
int element[QUEUE_LEN];
int front,rear,choice,x,y;
};
struct queue q;
int main()
{
int i=1;
void add(struct queue*,int);
void shown(struct queue*);
void delete(struct queue*);
int choice,x;
do
{
printf("enter 1 for add \nenter 2 for remove element front the queue\nenter 3 for exit\n");
printf("Enter your choice");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the element to be added\n");
scanf("%d",&x);
add(&q,x);
break;
case 2:
delete(&q);
break;
case 3:
return 0;
break;
case 4:
shown(&q);
break;
}
}while(i=1);
}
void add(struct queue *q,int y)
{
if(q->rear<QUEUE_LEN)
{
q->element[q->rear]=y;
printf("%d is added\n",y);
++q->rear;
}
else
printf("Queue overflow");
}
void shown(struct queue *q){
int r=0;
int s;
do{
s=q->element[r];
printf("%d \n",s);
r=r+1;
}while(r<q->rear);
}
void delete(struct queue *q)
{
int x;
if (q->front>=q->rear)
printf("Queue empty\n");
else
{
x=q->element[q->front];
q->front++;
printf("%d is deleted\n",x);
}
}
