Queues A queue is a first-in, first-out (FIFO) data structure in which the element that is inserted first is the first one to ... 08:05

Queues

• A queue is a first-in, first-out (FIFO) data structure in which the element that is inserted first is the first one to be taken out. The elements in a queue are added at one end called the rear and removed from the other end called the front.

Every queue has front and rear variables that point to the position from where deletions and insertions can be done, respectively.

Types of queues

1.    Linear Queue	2.    Circular Queue
A linear queue is like a straight line in which all elements or instructions stand one behind the other.	A circular queue has a circular structure. The last element of this queue is connected with the first element, thus completing the circle.
Insertion and deletion happens at front and rear at fixed positions	Insertion and deletions happens at front and rear at variable positions
It is not as efficient as Circular queue.	It is more essential than Linear Queue

3.   







     3. Deque

• A deque is a list in which the elements can be inserted or deleted at either end. It is also known as a head-tail linked list because elements can be added to or removed from either the front (head) or the back (tail) end. In a deque, two pointers are maintained, LEFT and RIGHT, which point to either end of the deque.

There are two variants of a double-ended queue. They include:-

Input restricted deque

In this dequeue, insertions can be done only at one of the ends, while deletions can be done from both ends.

Output restricted deque

In this dequeue, deletions can be done only at one of the ends, while insertions can be done on both ends.

       4. Priority Queue

• A priority queue is a data structure in which each element is assigned a priority. The priority of the element will be used to determine the order in which the elements will be processed. The general rules of processing the elements of a priority queue are

1. ·   An element with higher priority is processed before an element with a lower priority.
2.    Two elements with the same priority are processed on a first-come-first-served (FCFS) basis.

A priority queue can be thought of as a modified queue in which when an element has to be removed from the queue, the one with the highest-priority is retrieved first. The priority of the element can be set based on various factors.

Priority queues are widely used in operating systems to execute the highest priority process first. The priority of the process may be set based on the CPU time it requires to get executed completely.

Applications of Queues

• Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
• Queues are used to transfer data asynchronously (data not necessarily received at same rate as sent) between two processes (IO buffers), e.g., pipes, file IO, sockets.
• Queues are used as buffers on MP3 players and portable CD players, iPod playlist.
• Queues are used in Playlist for jukebox to add songs to the end, play from the front of the list.
• Queues are used in operating system for handling interrupts.