Queue in Data Structure
The queue is a linear list in which we can insert data from one end and delete data from another end.
let's understand it with a simple example, let's say we have a line of people at the shop waiting for their turn at the counter. so the person who enters first in the line will out first after taking the things. and the person who enters last will out last after taking the things. so we can say that a person that will enter first will out first. and these are the features of the queue.
What is Queue - Definition
A queue is a linear list that follows the First-In-First-Out (FIFO) system in which the insertions of new elements can take place at one end on the list called the rear part of the stack and deletions of the queue can take place only at the other end called the front of the stack.
Operations on queue
- Insert an element at the end of a queue.
- Delete an element from the front of the queue.
Note - Before deleting an element from the front of the queue we need to access that element first. and if the queue is empty means there are no elements available in the queue then it is not possible to delete the element from the queue. and if the queue is full means there is no space available for inserting a new element then it is not possible to add a new element into the queue.
Representation of queue in memory
Just like a stack we can also represent or implement the queue using the linear array or linear linked list.
Applications of queue
There are some places or application that uses the queue to resolve their issues that are following.
There are many algorithms that use the queue to solve problems inefficient way.
Printers also use the queue to solve the blocking problem. let's say we command the printer to print 2 pages then both will come in a queue to the printer and then the job that comes first will print first.
In real life, every line is a queue. for example ticket counter lines, bus stop lines, railway station lines, etc.
Types of queues
- Linear queue
- Circular queue
- Double-ended queue
- Multi queue
- Priority queue
To implement a linear queue we need to define two variables called front which holds the index of the first element and rear which hold the last element of the queue and an array to hold the elements of the queue.
whenever we want to add an element to the queue we need to increase the rear part of the queue and whenever we want to delete an element from the queue we need to increase the front part of the queue.
To implement a circular queue we need to treat the array as a circular array rather than a linear array. and always need to consider that the first element of the array is immediately following the last element. so if we want to add a new item and the queue is full and if the first element of the queue is empty then we can insert the next element to the first position of the queue.
De queue is a kind of queue in which we can insert or delete data from both ends but not from the middle.
Using one array or one linked list we can maintain two queues. this type of array or linked list is called multi-queue. we can start one queue from the front end and the second queue from the last end.
A priority queue is a queue in which each element has a priority assigned to it. so when any operation is applied to the queue it will process using the priority base.
The operations that are based on priority
An element that has high priority is processed first before any element of lower priority.
If two elements have the same priority then both are processed according to the order. if the first element is added first then it will be processed first.
On a priority base, the shortest job is given higher priority than a longer job.
If an operation is important then other than it will process first.
Implementing a priority queue
We can represent or implement a priority queue using -
- Using a Linear linked list
- Using heap
Implementing using a Linear linked list
To implement a queue using the linked list we need to declare three fields for each node info, pr and link. info will hold the value of the element and pr will hold the priority of the element and the link will hold the address of the element.
Implementing using Heap
If the priority for the lower number in the queue is highest then we can represent it using the min-heap. and if a priority queue has the highest priority number then it can be represented using a max heap.