Queue : An Overview 

Queue is a linear data structure that works on FIFO (First-In-First-Out) basis. The element inserted to the data structure will be the first element to be removed from it. We cannot add or remove random elements from this data structure. It is an ADT (Abstract Type Data Structure). This data structure has two ends viz. Front and Rear. Data added to the queue from the last called REAR. Data removed from the beginning end called FRONT.

Let us consider an example of a queue for movie ticket. Here, the first person in the line will get the ticket first and leave the line first and the last person will stay at the last of the line likewise, in this data structure, the element at the first will deleted first and the element that we want to insert will be added at the end of this linear data structure.

The process of inserting an element to the queueDataStructure is called Enqueue and the process of removing/deleting an element from the queueDataStructure is called Dequeue.

Types of Queue

There are four types of queue:

• Simple queue

It is the normal queue we have discussed here in this article.

• Priority queue

It contains data items which have some preset priority. While removing an element from a priority queue, the data item with the highest priority is removed first. Here, insertion is performed in the order of arrival and deletion is performed based on the priority.

• Circular queue

Here, front and rear are connected to make a circle. It stores elements in circular way and perform operations on FIFO basis. It contains a collection of data which allows insertion of data at the end of the queue and deletion of data at the beginning of the queue.

• Double-ended queue/ Deque

Here, insert and delete operation can be occur at both ends that is front and rear of the queue.

Basic Operations in a Queue

We can perform several basic operations in this linear data structures:

enqueue()

Adding an element to this data structure via its real end. We have to check whether the queue is already full or it has space to insert element. If it can add more element, increase rear pointer by one and insert the element.

int enqueue(int data) {
if(isfull())
return 0;
rear = rear + 1;
queue[rear] = data;
return 1;
}

dequeue()

Removing an element from this data structure. Data is removed from its front end. We have to check whether the queue is empty or it has some element to remove. If it is not empty, increase front pointer by one and remove the element at the front.

int dequeue() {
if(isempty())
return 0;
int data = queue[front];
front = front + 1;
return data;
}

isFull()

This method is used to check the status of data structure. If the rear pointer reach to the maximum size of the array that means the data structure has no space to insert more element. In such a situation, we cannot add more elements to the queue.

int isfull() {
if(rear == MAXSIZE - 1)
return 1;
else
return 0;
}

isEmpty()

it is used to check the status of the queue. It checks whether the data structure has initialized or it’s empty yet. If the front pointer represents 0, the queue is empty.

int isempty() {
if(front < 0 || front > rear)
return 1;
else
return 0;
}

Peek()

This is used to see the element at the front end of the queue.

int peek() {
return queue[front];
}

Working of a queue | How queue works?

Queue has two ends: front and rear. It is a linear data structure that can insert data from one end and remove from the other only. We also know its working is based on FIFO. FIFO is abbreviation of First In First Out.

At first it is checked whether a queue is initialized or not. At the time of initialization we set both front and rear pointers to -1 that represents it has no elements. Whenever an element is supposed to be added, it is mandatory to check whether it’s full or not. If it’s not full, increase the value of rear by 1 and enqueue the element. Whenever an element is supposed to remove, it is always necessary to check for isEmpty condition. If it is not empty, increase the value of front by 1 and dequeue an element.

Queue Implementation (C programming)

#include<stdio.h>

#include<conio.h> 

#define MAX 50

int queue_array[MAX];

int rear = - 1;

int front = - 1;

Public void insert()

{

int add_item;

if (rear == MAX - 1)

printf("Overflow \n");

else

{

if (front == - 1)

/*If it is initially empty */

front = 0;

printf("Inset the element : ");

scanf("%d", &add_item);

rear = rear + 1;

queue_array[rear] = add_item;

}

} 

Public void delete()

{

if (front == - 1 || front > rear)

{

printf("Underflow \n");

return ;

}

else

{

printf("Element deleted from DS is : %d\n", queue_array[front]);

front = front + 1;

}

}

Public void display()

{

int i;

if (front == - 1)

printf(" Empty \n");

else

{

printf(" Data Items : \n");

for (i = front; i <= rear; i++)

printf("%d ", queue_array[i]);

printf("\n");

}

}

public static void main()

{

int ch;

while (1)

{

printf("1.Insert an element \n");

printf("2.Delete an element \n");

printf("3.Display all elements \n");

printf("4.Quit \n");

printf("Enter your choice : ");

scanf("%d", &ch);

switch (ch)

{

case 1:

insert();

break;

case 2:

delete();

break;

case 3:

display();

break;

case 4:

exit(1);

default:

printf("Wrong choice \n");

}

}

}

Applications of queue

It is a simple data structure. We can implement it in different programming languages such as C, C++, C#, Java etc. with ease. It is quite easy to implement but still effective and applicable in real world scenarios. It is very much useful in the following cases:

• Serving requests on a single shared resource, like a printer, CPU task scheduling 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.
• Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive i.e. First come first served.

This data structure can be used whenever we need to manage any group of objects in an order in which the first one coming in, also gets out first while the others wait for their turn.

 

 

Was this article helpful? We would love to hear from you. Must share your views in the comment section below. For more interesting and informative updates, keep visiting our Tech Blogs.