- There are several types of queues that are commonly used in computer science and various applications.
What Is A Queue?
- Queue is the data structure that is similar to the queue in the real world. A queue is a data structure in which whatever comes first will go out first, and it follows the FIFO (First-In-First-Out) policy.
- Queue can also be defined as the list or collection in which the insertion is done from one end known as the rear end or the tail of the queue, whereas the deletion is done from another end known as the front end or the head of the queue.
- Simple Queue or Linear Queue
- Circular Queue
- Priority Queue
- Double Ended Queue (or Deque)
Simple Queue or Linear Queue
- A simple queue, also known as a linear queue, is the most basic type of queue. It follows the First In First Out (FIFO) principle, where the element that is inserted first is the one that is deleted first.
- In a linear queue, the elements are inserted at the rear and deleted from the front.
Enqueue:
- Inserting an element at the rear of the queue.
Dequeue:
- Deleting an element from the front of the queue.
Peek:
- Viewing the element at the front of the queue without removing it.
isEmpty:
- Checking if the queue is empty.
isFull:
- Checking if the queue is full.
- Simple queues are often implemented using arrays or linked lists. Arrays are used when the size of the queue is fixed, and linked lists are used when the size of the queue is not fixed.
Circular Queue
- A circular queue is a linear data structure that follows the FIFO (First In First Out) principle. It is similar to the simple queue, with the difference that a circular queue is implemented as a circular data structure.
- This means that the last element is connected to the first element, forming a circle. This allows the queue to use the available space more efficiently.
Enqueue:
- Adding an element to the rear of the queue.
Dequeue:
- Removing an element from the front of the queue.
Front:
- Getting the front element of the queue without removing it.
Rear:
- Getting the rear element of the queue without removing it.
isEmpty:
- Checking if the queue is empty.
isFull:
- Checking if the queue is full.
- Circular queues are often implemented using arrays, and the modulus operator is used to ensure the circular behavior.
- They are used in situations where a fixed size queue is required, and there is a need to efficiently utilize the available space. Examples include the implementation of CPU scheduling, memory management, and traffic management systems.
Priority Queue
- A priority queue is a type of abstract data structure that operates similar to a regular queue but with a notable distinction: each element has a “priority” associated with it. In a priority queue, elements are served based on their priority.
- Elements with higher priority are served before elements with lower priority, regardless of the order in which they were added. If two elements have the same priority, they are served according to their order of arrival.
Array:
- Elements are stored in an array, and the queue is ordered based on priority.
Linked List:
- Elements are linked together with pointers, and the queue is ordered based on priority.
Heap:
- This is one of the most common and efficient ways to implement a priority queue. The heap data structure maintains the highest (or lowest) priority element at the root.
Insertion:
- Adding an element to the queue with a specified priority.
Deletion:
- Removing the element with the highest priority from the queue.
Peek:
- Viewing the element with the highest priority without removing it.
isEmpty:
- Checking if the priority queue is empty.
- Priority queues are widely used in various applications, including task scheduling, shortest path algorithms, data compression, and more, where ordering and serving elements based on their priority are critical.
- They provide a way to manage tasks efficiently by ensuring that the most important tasks are handled first.
Ways to Implement The Queue
There are two ways of implementing the Queue:
- Implementation using array: The sequential allocation in a Queue can be implemented using an array. For more details, click on the below link: https://www.javatpoint.com/array-representation-of-queue
- Implementation using array: The sequential allocation in a Queue can be implemented using an array. For more details, click on the below link: https://www.javatpoint.com/array-representation-of-queue
