Queue is an abstract data structure that is similar to stacks. Unlike stacks, a queue is open at both ends. One end is always used to insert data (enqueue) and the other end to remove data (dequeue).
What is a queue?
A Queue is a FIFO (First In First Out) data structure where the element that is added first will be deleted first. The basic queue operations are enqueue (insertion) and dequeue (deletion). Enqueue is done at the front of the queue and dequeue is done at the end of the queue. The elements in a queue are arranged sequentially and hence queues are said to be linear data structures.
The practical examples of queues are
- The consumer who comes first to a shop will be served first.
- CPU task scheduling and disk scheduling.
- Waiting list of tickets in case of bus and train tickets.
- Simple Queue
- Circular Queue
- Priority Queue
- Dequeue (Double Ended Queue)
The simple queue is a normal queue where insertion takes place at the FRONT of the queue and deletion takes place at the END of the queue.
- In a circular queue, the last node is connected to the first node.
- Circular queue is also called as Ring Buffer.
- Insertion in a circular queue happens at the FRONT and deletion at the END of the queue.
- In a priority queue, the nodes will have some predefined priority.
- Insertion in a priority queue is performed in the order of arrival of the nodes.
- The node having the least priority will be the first to be removed from the priority queue.
Dequeue (Doubly Ended Queue)
In a Double Ended Queue, insertion and deletion operations can be done at both FRONT and END of the queue.
Basic operations in a queue
The most basic queue operations in data structure are the following
- enqueue() - Adds an element at the beginning of the queue. If the queue is full, then it is an overflow.
- dequeue() - Deletes an element at the end of the queue. If the queue is empty, then it is an underflow.
Check if the queue is full.
If the queue is full, then print "Queue overflow".
Else increment REAR by 1.
Assign QUEUE [ REAR ] = ELEMENT.
Check if the queue is empty.
If the queue is empty, the print "Queue underflow".
Copy the element at the front of the queue to some temporary variable, TEMP = QUEUE[ FRONT ].
Increment FRONT by 1.
Print temp and delete it.