A queue is a linear data structure that acts like a real-life queue. It has two sides: Front and Rear, and follows the FIFO (First In and First Out) order for insertion and removal.
Types of Queue Data Structure
Queues can be categorized into Linear Queues, Circular Queue, Priority Queues, and Double Ended Queues (or Deque)
Linear Queue
A linear queue is a simple form of a Queue that mimics real-life queues. It restricts the insertion to the rear side and deletion to the front side.
- Enqueue and Dequeue are the basic operations of the queue data structure. Enqueue inserts the elements on the rear side while the Dequeue removes them from the front side. So, the linear queues work First In and First Out (FIFO).
- So, they are specifically used in applications that process the data in FIFO order.
- Learn about Linear Queues
- Implement Linear Queue using Array with Example
- Implement Linear Queue using Linked List with Example
Circular Queue
A circular queue is an extended version of a linear Queue. The last element is connected back to the first element. Like a linear queue, It follows the First In and First Out (FIFO) order.
- Circular queues support Enqueue and Dequeue operations as well for insertion and deletion.
- In addition, array memory is effectively utilized in circular queues. Linear queues are considered Full when the rear position is reached the last index. As a result, the empty spaces on the front side are left unutilized. However, in a circular queue, they are utilized as the Rear can circle to the beginning.
- So, the circular queue is used in applications that prefer array implementation for FIFO operations. Furthermore, it is suitable for circular/looping operations.
- Learn about Circular Queues
- Implement Circular Queue using Array with Example
- Implement Circular Queue using Linked List with Example
Priority Queue
Priority Queue is a linear data structure that has the priority associated with each element. The elements are served in the order of highest to lowest priority. So it does not obey the FIFO order.
- An enqueue operation inserts the element into the queue, while Dequeue removes the high-priority element first.
- Priority Queue is used in applications that perform operations based on priority.
- Learn about Priority Queues
- Implement Priority Queue using Array with Example
- Implement Priority Queue using Linked List with Example
Double Ended Queue (Deque)
Double Ended Queue is a linear data structure that allows insertion and deletion on both sides. So, it is a combination of both Stack and Queue data structures.
- Supported operations of Deque are InsertFront, InsertRear, DeleteFront, and DeleteRear.
- Deques are used to perform both LIFO and FIFO operations with the same data.
- Learn about Double Ended Queues
- Implement Deque using Circular Array with Example
- Implement Deque using Linked List with Example
Operations and Time complexity of Queue
These are the basic queue operations and their time/space complexity.
| Operation | Description | Time Complexity | Space Complexity |
| Enqueue | Inserts an element on the rear side of the queue | O(1) | O(n) |
| Dequeue | Removes the element from the front side. | O(1) | O(n) |
| Peek | Returns the front element without removing | O(1) | O(n) |
| IsFull | Check if the queue is full | O(1) | O(n) |
| IsEmpty | Check if the queue is empty | O(1) | O(n) |
Note: The time complexity does not apply to Priority Queues. See Time Complexity of Priority Queues here.
Advantages and Disadvantages of Queue
Advantages of Queue
- Queues provide the ability to serve the data in a specific order. In particular, the First In and First Out (FIFO) order.
- Faster insertion and deletion with O(1) time.
Disadvantages Queue
- Searching for an element from the queue is slower and takes O(n) time.
- Also, it is limited by the capacity when you choose to implement the queue with an array.
Application of Queue Data Structure
When to use Queue Data Structure
Queues are useful for frequent insert and delete operations in the FIFO order. Avoid using them if you need to perform frequent searches.
- Linear Queues can be used for operations with the First In and First Out (FIFO) order.
- Alternatively, use Circular Queues when you want to implement the queue using an array. This helps to utilize the memory effectively. In addition, Circular Queues are effective for circular/looping operations.
- Prefer Priority Queues when you want to process the data based on the order of priority.
- Finally, a Deque is the best choice for applications that require both FIFO and LIFO operations with the same data.
Real-time Applications of Queue
- Resource sharing operations such as disk scheduling. Disk operations can be queued and run on a FIFO order.
- Asynchronous transfers like IO buffers, Pipes using a linear queue. A sender can enqueue the input data on the front side while the receiver dequeue from another end.
- Traffic system to switch on the traffic lights in a circular fashion based on the time slot.
- CPU Scheduling based on priority. A priority queue can hold the sorted list of tasks and serve the high-priority first.
- Steal job scheduling algorithm in a multiprocessor system. Each processor has work items in a separate deque. But, another processor can steal a job from the rear side when free. Thus, optimizing the execution time.
Queue Data Structure FAQ
Difference between Stack and Queue
The following are the differences between Queue and Stack.
| Stack | Queue |
| Stacks work in Last In First Out (LIFO) order | In contrast, Queues work in First In and First Out (FIFO) order |
| The stack has only one side called the Top. | But the queue has two sides: Front and Rear. |
| Suitable for reversing and backtracking operations such as backward navigation and undo/redo features. | Suitable for sequential operations such as job scheduling and asynchronous data transfers. |