Queue in Data Structure

A queue is a non-primitive linear data structure. A queue allows elements to be retrieved in the same order they were inserted. Queues are often referred to as FIFO (First In First Out). A queue has two ends, namely a front and rear. Elements are inserted from the rear end and retrieved from the front end of the queue.

Queues are used to buffer input devices such as the keyboard and mouse. Using a queue ensures that the keystrokes are processed in the order in which they were input. The below assumptions are made:

1. Front will be pointing to the first element
2. Each time a new element is inserted into the queue the rear is incremented by 1.
3. Each time an element is deleted from the queue value of front is incremented by 1.

A circular queue is the same as a queue but the front and rear ends of a queue are joined together to form a circular ring. A circular queue overcomes the problem of unutilized space in linear queue implemented as arrays. A circular queue also has a front and rear to keep the track of elements deleted and inserted.

A Deque is a special form of queue, which allows insertion and deletion of elements from both the ends.

There are two types of deque:

1. Input restricted queue: Restricts input from one end
2. Output restricted queue: Restricts output from one end.

Priority queues are essentially a list of items in which each item has a priority associated with it. The priorities are associated depending on preference rules. Different items have different priorities. An item having higher priority is given greater importance than one with a lower priority. Various items are inserted into a priority queue in an arbitrary order. They are taken out from the queue in order of their priorities.Priority queues are generally used by operating systems to manage various resources such as printers and processors.

Priority queues solve the problem of collisions that might occur due to the use of shared resources.

Application of Queue:

1. Round-Robin technique for processor scheduling is implemented using queues.
2. All types of customer services (like railway ticket reservation) center software's are designed using queues to store customers information.
3. Printer-Server routines are designed using queues.