Last Updated on August 30, 2022 by Gokul Kannan
Queue
A queue is basically a linear data structure that works on the principle of FIFO (First in First out) which means an element that is enqueued first will be dequeued first. Element is enqueued from the rear end of the queue and dequeued from the front end. The insertion operation in the queue is known as enqueue and the deletion operation in the queue is known as dequeue.
The queue is used when the operations are to be performed in the manner of First in First out order just like Breadth-First Search.
For Example A ticket Queue outside a cinema hall where the person enters the queue first will get the ticket first.
Basic Operations of Queue:
-
Enqueue: This operation is used to Insert an element at the rear end of the queue.
-
Dequeue: This operation is used to remove and return an element from the front end of the queue.
-
isEmpty(): This operation is used to check whether the queue is empty or not. It returns bool value, if the queue is empty then this operation will return true else false.
-
isFull(): This operation is used to check whether the queue is full or not. It return true is the queue is full, else it will return false.
-
Peek(): This operation is used to get the value of the element from the front of the queue.
Working of queue:
- We can implement queue by using two pointers i.e. FRONT and REAR.
- FRONT is used to track the first element of the queue.
- REAR is used to track the last element of the queue.
- Initially, we’ll set the values of FRONT and REAR to -1.
Types of queues:
There are 4 types of queues:
1.Simple Queue:
A Queue is a linear data structure. Queue follows the FIFO rule i.e. First in First out. In other words we can say the element that goes in first is the element that comes out first.
For Example A ticket Queue outside a cinema hall where the person enters the queue first will get the ticket first.
In a simple queue, there are two ends, the end at which insertion operation performs is known as rear end whereas the end where deletion operation performs is known as front end.
2.Circular queue: Circular queue is a linear data structure which follows the FIFO(First in first out) property. In this, the last element is connected to the first element to make a ring, which is also known as Ring buffer.
How does the Circular queue work?
Circular queue works in the process of circular increment i.e. when we’ll increment the pointer and reach the end then pointer points to the beginning of the queue.
Operations of circular queue:
- front(): front is used to track the first element of the queue.
- rear(): rear is used to track the last element of the queue.
- Enqueue: This operation is used to Insert an element at the end of the queue.
- Dequeue: This operation is used to remove and return an element from the front of the queue.
3.Priority queue: Priority queue is an abstract data type, It is a type of queue in which each element has a priority assigned to it. The priority of the element determines the order in which elements are removed from the priority queue. In the priority queue, all the elements are arranged either in ascending order or descending order.
Priority Queue Properties:
- In the priority queue, every element has priority assigned to it.
- The element with highest priority first.
- If two elements are having the same priority then they are served according to their order in the queue.
Uses of priority queue:
- Priority queue is used in memory management.
- Priority queue is used in CPU Scheduling.
- Also used in the Traffic system.
Implementation of Priority queue:
Priority queue is implemented in the following ways:
- Using Arrays.
- Using Linked List
- Using Heap data structure
- Using Binary Search Tree
4.Deque (Double ended queue): In Deque, The insertion and deletion operations are done from both the ends i.e. either from the rear or from the front.
We can use deque as both stack and queue as it follows the insertion and deletion operations from both the ends.
We can consider deque as both because stack follows the LIFO Order in which insertion and deletion can be done from the same end and as we study in the dequeue it is possible to do both the operations from the same end.
The representation of deque:
Types of deque:
-
Input Restricted deque: As the name suggests, in input restricted deque, insertion operation can be performed at only one end whereas deletion operation can be done from both the ends.
-
Output Restricted deque: In output restricted deque, deletion operation can be performed at single end whereas insertion operation can be performed at both the ends.
Application of queues:
- Job Scheduling: The jobs which are executed by the computer are executed in a sequence manner i.e. one by one and these jobs are scheduled by queue.
- Multiprogramming: When we run multiple programs at the same time in the memory this is called multiprogramming and the memory is organized by a queue.
- Operations on data structure: Operations like Tree traversals, BFS involves the use of queue.
- Queue is also used in CPU Scheduling and in memory management.
This article tried to discuss Different Types Of Queues And Its Applications. Hope this blog helps you understand the concept. To practice problems you can check out MYCODE | Competitive Programming at Prepbytes