A queue is defined as a special type of data structure where elements are inserted from one end and elements are deleted from other end.
The end from where the elements are inserted is called rear end (r) and the end from where elements are deleted called front end (f). In a queue always elements are inserted from the rear end and elements are deleted from the front end.
Queue is a linear list for which all insertions are made at the end of the list; all deletions (and usually all accesses) are made at the other end. So queue is also called First in First out (FIFO) data.
Different types of queues
- Ordinary queue
- Double ended queue
- Circular queue
- Priority queue
1. Ordinary queue
This queue operates on the first come first serve basis. Items will be inserted from one end and they are deleted at the other end in the same order in which they are inserted. A queue can be represented by using an array by using an array as shown in the figure.
The operations that can be performed on these queues are
- Insert an item at the rear end
- Delete an item from the front end
- Display the contents of the queue
Disadvantage of Ordinary queue
In an ordinary queue, as an item is inserted, the rear end identified by r is incremented by 1. Once r reaches QUEUE_SIZE-1, we say queue is full. Note that even if some elements are deleted from queue, because the rear end identified by r is still equal to QUEUE_SIZE-1, so item cannot be inserted into the queue.
2. Double ended queue (Deque)
Another type of queue called double ended queue also called Deque. Deque is a special type of data structure in which insertions and deletions will be done either at the front end or at the rear end of the queue. The operations can be performed on Deques are
- Insert an item from front end
- Insert an item from rear end
- Delete an item from front end
- Delete and item from rear end
- Display the contents of queue
3. Circular queue
In an ordinary queue, as an item is inserted, the rear end identified by r is incremented by 1. Once r reaches QUEUE_SIZE-1, we say queue is full. Note that even if some elements are deleted from queue, because the rear end identified by r is still equal to QUEUE_SIZE-1 item cannot be inserted. But this disadvantage is overcome using circular queue. In circular queue an item can be published circularly. This can be achieved using the statement r = (r+1)%QUEUE_SIZE
The operations can be performed on circular queue are.
- Insert an item from rear end
- Delete an item from front end
- Display queue contents
4. Priority queue
Such a queue where a job is processed based on the priority is called a priority queue