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 asFirst in First out (FIFO) structures. A queue has two ends, namely a front and rear. Elements are inserted fromthe rear end of the queue and retrieved from the front end of the queue.
Whenever we insert an element in the queue the value of Rear is incremented by 1. Whenever we delete an element in the queue the value of front is incremented by 1.Queues are used to buffer input devices such as the keyboard and mouse. Using a queue ensures that thekeystrokes 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. Circular Queue 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. Double Ended Queue (Deque) 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 : Input restricteddeque restricts input from one end 2. Output restricted queue:output restricted deque restricts output from one end. Priority Queue Priority queues are essentially a list of items in which each item has a priority associated with it. The prioritiesare associated depending on preference rules. Different items have different priorities accorded to them. Anitem 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 orderof 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. Printer server routines are designed using queues.