Simple Queue A linear list which permits deletion to be performed at one end of the list and insertion at the other end is called queue. The information in such a list is processed FIFO (first in first out) of FCFS (first come first served) pattern. Front is the end of queue from that deletion is to be performed. Rear is the end of queue at which new element is to be inserted. The process to add an element into queue is called Enqueue. The process of removal of an element from queue is called Dequeue. The familiar and traditional example of a queue is Checkout line at Supermarket Cash Register where the first person in line is usually the first to be checkedout (Simple Queue) Circular Queue A more suitable method of representing simple queue which prevents an excessive use of memory is to arrange the elements Q[1], Q[2]….,Q[n] in a circular fashion with Q[1] following Q[n], this is called circular queue. In a standard queue data structure re-buffering problem occurs for each dequeue operation. To solve this problem by joining the front and rear ends of a queue to make the queue as a circular queue. Circular queue is a linear data structure. It follows FIFO principle. In circular queue the last node is connected back to the first node to make a circle. Circular linked list fallow the First In First Out principle. Elements are added at the rear end and the elements are deleted at front end of the queue. Both the front and the rear pointers points to the beginning of the array. It is also called as “Ring buffer”. (Circular Queue) Dequeue A dequeue (double ended queue) is a linear list in which insertion and deletion are performed from the either end of the structure. There are two variations of Dqueue Input restricted dqueue- allows insertion at only one end Output restricted dqueue- allows deletion from only one end Such a structure can be represented by following fig. Priority Queue A queue in which we are able to insert remove items from any position based on some property (such as priority of the task to be processed) is often referred as priority queue. Below fig. represent a priority queue of jobs waiting to use a computer. Priorities of 1, 2, 3 have been attached with jobs of real time, online and batch respectively. Therefore if a job is initiated with priority i,it is inserted immediately at the end of list of other jobs with priorities i. Here jobs are always removed from the front of queue
