A queue is a FIFO (First-In, First-Out) data structure in which the element that is inserted first is the first one to be taken out. The elements in a queue are added at one end called the REAR and removed from the other end called the FRONT. Queues can be implemented by using either arrays or linked lists.
This makes queue as FIFO(First in First Out) data structure, which means that element inserted first will be removed first.
Operations on Queue
Queues can be easily represented using linear arrays as show in the above figure.
In the above figure initially FRONT =0 and REAR =4, after adding a new element with value 36, REAR would be incremented by 1 and the value would be stored at the position pointed by REAR.
Here, FRONT = 0 and REAR = 5. Every time a new element has to be added, we repeat the same procedure.
If we want to delete an element from the queue, then the value of FRONT will be incremented. Deletions are done from only this end of the queue.
After deleting first element(12) from queue, FRONT=1.
However, before inserting an element in a queue, we must check for overflow conditions. An overflow will occur when we try to insert an element into a queue that is already full. When REAR = MAX – 1, where MAX is the size of the queue, we have an overflow condition. Note that we have written MAX – 1 because the index starts from 0.
Similarly, before deleting an element from a queue, we must check for underflow conditions. An underflow condition occurs when we try to delete an element from a queue that is already empty. If FRONT = –1 and REAR = –1, it means there is no element in the queue.
Applications of Queue
- Queue is useful in CPU scheduling, Disk Scheduling. When multiple processes require CPU at the same time, various CPU scheduling algorithms are used which are implemented using Queue data structure.
- When data is transferred asynchronously between two processes.Queue is used for synchronization. Examples : IO Buffers, pipes, file IO, etc.
- In real life scenario, Call Center phone systems uses Queues to hold people calling them in an order, until a service representative is free.
- Jobs to a network printer is enqueued so that the earlier a job is submitted the earlier it will be printed.
- Breadth first searches use queues. Queues also have applications in graph theory.
Algorithm of Queue insertion and deletion
Algorithm for ENQUEUE operation
Step 1: IF REAR = MAX-1
Write OVERFLOW
Goto step 4
[END OF IF]
Step 2: IF FRONT=-1 and REAR=-1
SET FRONT = REAR =
ELSE
SET REAR = REAR+1
[END OF IF]
Step 3: SET QUEUE[REAR] = NUM
Step 4: EXITIn the above algorithm to insert an element in a queue.
- In Step 1, we first check for the overflow condition.
- In Step 2, we check if the queue is empty. In case the queue is empty, then both FRONT and REAR are set to zero, so that the new value can be stored at the 0th location. Otherwise, if the queue already has some values, then REAR is incremented so that it points to the next location in the array.
- In Step 3, the value is stored in the queue at the location pointed by REAR
Algorithm for DEQUEUE operation
Step 1: IF FRONT = -1 OR FRONT > REAR
Write UNDERFLOW
ELSE
SET FRONT = FRONT+1
[END OF IF]
Step 2: EXITIn the above algorithm to delete an element from the queue
- In Step 1, we check for underflow condition. An underflow occurs if FRONT = –1 or FRONT > REAR. However, if queue has some values, then FRONT is incremented so that it now points to the next value in the queue.
Queue program in C
#include <stdio.h>
#include <conio.h>
#define MAX 10 // Changing this value will change length of array
int queue[MAX];
int front = -1, rear = -1;
void insert(void);
int delete_element(void);
int peek(void);
void display(void);
int main() {
int option, val;
do {
printf("\n\n ***** MAIN MENU *****");
printf("\n 1. Insert an element");
printf("\n 2. Delete an element");
printf("\n 3. Peek");
printf("\n 4. Display the queue");
printf("\n 5. EXIT");
printf("\n Enter your option : ");
scanf("%d", & option);
switch (option) {
case 1:
insert();
break;
case 2:
val = delete_element();
if (val != -1)
printf("\n The number deleted is : %d", val);
break;
case 3:
val = peek();
if (val != -1)
printf("\n The first value in queue is : %d", val);
break;
case 4:
display();
break;
}
} while (option != 5);
getch();
return 0;
}
void insert() {
int num;
printf("\n Enter the number to be inserted in the queue : ");
scanf("%d", & num);
if (rear == MAX - 1)
printf("\n OVERFLOW");
else if (front == -1 && rear == -1)
front = rear = 0;
else
rear++;
queue[rear] = num;
}
int delete_element() {
int val;
if (front == -1 || front > rear) {
printf("\n UNDERFLOW");
return -1;
} else {
val = queue[front];
front++;
if (front > rear)
front = rear = -1;
return val;
}
}
int peek() {
if (front == -1 || front > rear) {
printf("\n QUEUE IS EMPTY");
return -1;
} else {
return queue[front];
}
}
void display() {
int i;
printf("\n");
if (front == -1 || front > rear)
printf("\n QUEUE IS EMPTY");
else {
for (i = front; i <= rear; i++)
printf("\t %d", queue[i]);
}
}Here is the output of the above program when executed online
***** MAIN MENU *****
1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 1
Enter the number to be inserted in the queue : 22
***** MAIN MENU *****
1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 1
Enter the number to be inserted in the queue : 33
***** MAIN MENU *****
1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 1
Enter the number to be inserted in the queue : 02
***** MAIN MENU *****
1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 4
22 33 2
***** MAIN MENU *****
1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 3
The first value in queue is : 22
***** MAIN MENU *****
1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 2
The number deleted is : 22
***** MAIN MENU *****
1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 4
33 2
***** MAIN MENU *****
1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 3
The first value in queue is : 33
***** MAIN MENU *****
1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 5
You may also like:
Stack Program in C (Concept, Algorithm & C program example)
Buy us a coffee
Become a Patron