Queue is a very simple, but useful Linear Data Structure in Computer Science. Like Stacks, it is also a Abstract Data Structure. But it is open from both the ends, not like in stacks where deletion and addition takes place form the same end. It is the most common Data structure, where elements are inserted from one end known as REAR end and removed from the other end which is the FRONT end, this is known as FIFO( First In First Out ) property.
In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed.
Visualising Queue !
As the name suggests, it is similar to a queue of people, let us take the example of COVID-19 scenario only. In the markets, people have to stand in queues at shops, in order to wait for their turn to buy the items. The person who comes first would be the first to buy the items and leave for home, similar is the case with the queues in Computer Science - Data Structures.
* The only difference between Queue and Stacks is in removing the elements. In Stacks, we delete the last element of the stack, whereas in queues, we delete the first element of the queue.
Types of Queue
- Simple Queue - Here addition of elements take place from the REAR end and the deletion occurs on the FRONT end.
- Circular Queue - It is concept-wise somewhat like Linked List, but unlike Linked list its last element points towards the first element making a link. It is also called Ring Buffer. Its main advantage is that it helps in memory utilisation.
- Priority Queue - It is a special type of queue where each element in the queue is associated with a unique property, and the elements are arranged on the basis of that property. Like in school, the teachers made us stand roll number wise during assemblies or any such occassions. That was a live demonstration of Priority Queue.
- The Double-ended queue - Double ended queue is a more generalised form of queue data structure which allows insertion and removal of elements from both the ends, i.e , front and back.
* Our main focus would be on Simple Queue.
Operations on Queue
The same operations that were carried out on Stacks are also carried out here, just the name of the operation differs.
- Enqueue - The process of adding elements in the Queue. It occurs from the REAR end. If the Queue gets completely filled, then that is known as OVERFLOW condition.
- Dequeue - The process of removing/deleting the elements from the Queue, but here, the element which was inserted at the first would be removed first, remember the example of COVID-19 scenario, mentioned above. It occurs at the FRONT end. If the Queue gets emptied then that condition is called UNDERFLOW.
- IsFull - To check whether the Queue is full.
- IsEmpty - To check whether the Queue is empty.
Implementing Queues
Like Stacks, Queues are also implemented by either Arrays or Linked Lists. But in this tutorial, we are concerned about Implementation with Arrays.
Program - Array Implementation of Queue
#include <stdio.h>
#define SIZE 10
int front=-1, rear=-1;
int array[SIZE];
void enqueue(int item)
{
if (rear == SIZE) //checking is the Queue full or not
return;
if(front == -1 && rear == -1){
front++;
rear++;
}
else
rear++;
array[rear] = item;
printf("%d enqueued to queue.\n",item);
}
int dequeue()
{
if (front > rear)
{
printf("Queue is Empty.\n");
return -1;
}
int item = array[front];
front++;
printf("%d dequeued from queue.\n",item);
return item;
}
int main()
{
printf("Front = %d, Rear = %d\n",front,rear);
enqueue(10);
printf("Front = %d, Rear = %d\n",front,rear);
enqueue(20);
printf("Front = %d, Rear = %d\n",front,rear);
enqueue(30);
printf("Front = %d, Rear = %d\n",front,rear);
enqueue(40);
printf("Front = %d, Rear = %d\n",front,rear);
dequeue();
printf("Front = %d, Rear = %d\n",front,rear);
dequeue();
printf("Front = %d, Rear = %d\n",front,rear);
dequeue();
printf("Front = %d, Rear = %d\n",front,rear);
dequeue();
printf("Front = %d, Rear = %d\n",front,rear);
dequeue();
printf("Front = %d, Rear = %d\n",front,rear);
enqueue(50);
printf("Front = %d, Rear = %d\n",front,rear);
}
OUTPUT
Front = -1, Rear = -1
10 enqueued to queue.
Front = 0, Rear = 0
20 enqueued to queue.
Front = 0, Rear = 1
30 enqueued to queue.
Front = 0, Rear = 2
40 enqueued to queue.
Front = 0, Rear = 3
10 dequeued from queue.
Front = 1, Rear = 3
20 dequeued from queue.
Front = 2, Rear = 3
30 dequeued from queue.
Front = 3, Rear = 3
40 dequeued from queue.
Front = 4, Rear = 3
Queue is Empty.
Front = 4, Rear = 3
50 enqueued to queue.
Front = 4, Rear = 4
* Here the main play is around 2 variables namely REAR and FRONT, REAR represents the last element of Queue, whereas FRONT represents the First element of Queue. We made 2 functions in the program enqueue(to perform insertion operation) and dequeue(to perform deletion operation).
* Time complexity in Enqueue and Dequeue operations is O(1), whereas Space complexity is O(N), where N is the size of Queue.
Applications of Queue
- 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.
- Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
- Most programming language have in built data structures to support common use cases and queue is one of them (stacks, linked lists, trees among others).
Advantages of using Queues
- Makes the program Fast, having a time complexity of O(1).
- Queues are very flexible, meaning they can have any data type, even we can have a Queue of Queues.
- The queue takes less space than most of the non-linear data structures.
Dis-advantages of using Queues
- Adding or deleting elements from the middle of the queue is complex as well as many of the queues are implemented using pointers, so in that respect, many programmers have the notion that they are difficult to create, maintain, and manipulate.
- The queue is not readily searchable. You have to start from the end and might have to maintain another queue. So if you have some data, which later on you would want to be searchable, then don’t even think about using a queue.
- Problems in Dequeue Operation, on deleting a element from the Queue, the Pointer increments by one step, thus, decreasing the original size of Queue, due to this, we cannot add more values, as this would lead to OVERFLOW condition.