Queue
It is a non-primitive, linear data structure in which elements are added/inserted at one end (called the REAR) and elements are removed/deleted from the other end (called the FRONT). A queue is logically a FIFO (First In First Out) type of list.
e.g., Consider a line of persons at a railway reservation counter. Whenever a person enter the queue, he stands at the end of the queue (addition of the nodes to the queue).
Note Every time the person at the front of the queue deposit the fee for ticket, he leaves the queue (deleting nodes from a queue).
Queue Implementation
Queue can be implemented in two ways
- Static implementation (using arrays)
- Dynamic implementation (using pointers)
Key Points
- In static implementation, we have to declare the size of the array at design time or before the processing starts.
- Implementing queues using pointers, the main disadvantage is that a node in a linked representation occupies more memory space than a corresponding element in array representation.
Circular Queue
In a cirular queue, the first element comes just after the last element or a circular queue is one in which the insertion of a new element is done at the very first location of the queue, if the last location of queue is full and the first location is empty.
Note A circular queue overcomes the problem of unutilised space in linear, queues implemented as arrays.
We can make following assumptions for circular queue
- Front will always be pointing to the first element (as in linear queue),
- If Front = Rear, the queue will be empty.
- Each time ‘a new element is inserted into the queue, the Rear is incremented by 1. Rear = Rear + 1
- Each time, an element is deleted from the
queue, the value of Front is incremented by one.
Front = Front + 1
Double Ended Queue (DEQUE)
It is a list of elements in which insertion and deletion operations are
performed from both the ends. That is why it is called double-ended queue or DEQUE.
There are two types of DEQUE, because of the restrictions put to PeiM either the insertion or deletion only at one end.
- Input restricted DEQUE
- Output restricted DEQUE
Operations on DEQUE
There are following operations on DEQUE
- Insertion of an element at the REAR end of the queue.
- Deletion of an element from the FRONT end of the queue.
- Insertion of an element at the FRONT end of the queue.
- Deletion of an element from the REAR end of the queue.
Key Points
- For an input restricted DEQUE all of the above four operations are valid.
- For output restricted DEQUE only 1,2 and 3rd operations are valid.
Priority Queues
This type of queue enables us to retrieve data items on the basis of priority associated with them. Below are the two basic priority queue choices
Sorted Array or List It is very efficient to find and delete the smallest element. Maintaining sortedness make the insertion of new elements slow.
Binary Heaps Here, the minimum key (in min Heap) is always at the root of the heap. Binary heaps are the right choice whenever we know an upperbound on the number of items in our priority queue. Since, we must specify the array size at compile time.
Applications of Priority Queues
- Round Robin (RR) technique for processor scheduling is implemented using queues.
- All types of customer service (e . g . , railway reservation) center softwares are designed using queues.
- Printer server routines are designed using queues.