Queue in C++
FREE
Introduction
Suppose you want to order food in a fast-food chain restaurant. You see a queue of people and you join the queue where the last person of the queue is standing. A person standing before you in the queue will also reach the counter before you. So you can place your order only when you reach the front of the queue.
Queues in C++ work similarly.
A queue is a linear data structure that follows FIFO(First in First Out) technique. This means the element pushed first into the queue will also be the first element to come out of it.
There are many variations of queue present in C++ such as deque, priority queue, double-ended priority queue. It has many interesting applications in operating systems, networking, etc.
Syntax
The syntax of declaring a queue in C++ is:
The header file required to use queue in C++ is:
Example
Output
Queue Methods in C++
| Method | Description | Time Complexity |
|---|---|---|
| empty() | Returns whether the queue is empty. It returns true if the queue is empty; otherwise, false. | O(1) |
| size() | Returns the size of the queue. | O(1) |
| swap() | Exchange the contents of two queues. The queues must be of the same data type, although sizes may differ. | O(1) |
| emplace() | Insert a new element into the queue container. The new element is added to the end of the queue. | O(1) |
| front() | Returns a reference to the first element of the queue. | O(1) |
| back() | Returns a reference to the last element of the queue. | O(1) |
| push(g) | Adds the element 'g' at the end of the queue. | O(1) |
| pop() | Deletes the first element of the queue. | O(1) |
Example Showing Important STL Queue Functions
Output
C++ Queue Operations
There are two basic operations in queue: enqueue and dequeue.
- Enqueue: When we add an element to a queue, it is said to be an enqueue operation. If the queue is full, we cannot add more elements to it. Such a condition is called an overflow condition. We use the push function to perform an enqueue operation in a queue. Syntax
Time Complexity - O(1)
-
Dequeue: When we remove an element from a queue, it is said to be a dequeue operation. If the queue is already empty, i.e., there are no elements in the queue, we cannot remove elements from it. Such a condition is called an underflow condition. We use the pop function to perform a dequeue operation in the queue. Syntax
Time Complexity - O(1)
Note: Since a queue works on the FIFO technique, the element that was pushed in first will pop out first as well, i.e., the relative order of elements in a dequeue operation is the same as the enqueue operation
Application of Queue
Queue in C++ has several real-life use cases, a few of them are listed below.
- It is used as a waiting list when a resource is shared among multiple processes, e.g., CPU scheduling, and disk scheduling.
- It is used to handle interrupts in operating systems.
- It is used in semaphores, spooling in printers, and FIFO scheduling.
- It is used in networking systems where data is transferred asynchronously, e.g., IO buffers, files IO, etc.
- It is used in routers and switches as well as in mailing lists.
- It is used for maintaining playlists in music applications.
Introduction to Priority Queue
Priority queues are a special type of queues in which the elements are ordered on the basis of their priority. They are of two types.
-
Max-priority queue: The first element in the queue is the greatest of all elements. All the elements are in non-increasing order. It is implemented using max-heap. By default, C++ creates a max-priority queue.
-
Min-priority queue: The first element in the queue is the smallest of all elements. All the elements are in non-decreasing order. It is implemented using min-heap.
All the methods such as push(), pop(), empty(), size(), swap(), emplace() described above can be applied on priority queues as well.
Note
Syntax of Priority Queue
The syntax of the priority queue(max-heap) is:
The syntax of the priority queue(min-heap) is:
Note: It is present in the queue header file in the C++ Standard Template Library.
Conclusion
- A queue in C++ is a linear data structure that is based on the FIFO(First In First Out) principle.
- An enqueue operation(insertion) is performed at the end of the queue.
- A dequeue operation(deletion) is performed from the front of the queue.
- All three operations insertion, deletion, and access have O(1) time complexity.
- Priority queues are a special type of queues in which the elements are ordered on the basis of their priority.
- A stack is a linear data structure that is based on the LIFO(Last In First Out) principle.
- Queues are used forCPUscheduling, handling interrupts, semaphores, networking systems, etc.