Different Types of Queues and its Applications
Queues are a type of container adaptors that follow a first in, first out (FIFO) arrangement. Items are added to the back and removed from the front. Queues use a encapsulated object of deque or list as its underlying container, and have specific member functions to access its elements.
In C++, the Standard Template Library (STL) provides a std::queue container that implements a queue. However, it’s also interesting and educational to build our own queue using vector data structures. In this article, we’ll explore the implementation of a queue using a vector template in C++.
Basic operations of queue
A queue is an ordered collection of elements that supports two primary operations: enqueue and dequeue. Enqueue adds an element to the back of the queue, while dequeue removes the element from the front. Additionally, we can check if the queue is empty and access the front element without removing it.
The queue operations can be summarized as follows:
- enqueue (or push): Add an element to the rear of the queue
- dequeue (or pop): Remove the element from the front of the queue
- front: Get the value of the element at the front of the queue
- empty: Check if the queue is empty
Standard Queue:
A standard queue is a linear data structure in that follows the First-In-First-Out (FIFO) principle, where elements are inserted at the rear (tail) end and removed from the front (head) end. The standard queue provides four primary operations: enqueue, dequeue, front, and empty.
The enqueue operation adds an element to the rear end of the queue. The dequeue operation removes the element at the front end of the queue. The front operation retrieves the value of the element at the front end of the queue without removing it. The empty operation checks if the queue is empty or not.
Standard queues are widely used in programming, with applications in algorithms like breadth-first search and round-robin scheduling. They are also used in inter-process communication and message passing systems. The simplicity and efficiency of standard queues make them an essential data structure in computer science.
The standard queue, available in the Standard Template Library (STL), is a basic implementation of a queue in C++.
Here’s a simple program using standard queue in C++
#include <iostream>
#include <queue>
#include <string>
void main() {
// Creating an empty queue of string
std::queue<std::string> q;
// Adding elements to the queue
q.push("hello");
q.push("world");
q.push("!");
// Displaying the queue
std::cout << "Queue: ";
while (!q.empty()) {
std::cout << q.front() << " ";
q.pop();
}
std::cout << std::endl;
}Priority Queue:
A priority queue is a type of queue where each element has an associated priority. The priority of an element determines its order in the queue, with higher priority elements being placed at the front and lower priority elements being placed at the rear. Thus, the element with the highest priority is always at the front of the priority queue.
Priority queues are typically implemented using a heap data structure, which is a binary tree that satisfies the heap property. The heap property ensures that the priority of the parent node is higher than its children, and this property is maintained throughout the tree. This allows for efficient insertion and removal of elements in a priority queue.
Priority queues provide two main operations: insertion and removal. When an element is inserted into a priority queue, it is placed at the appropriate position based on its priority. When an element is removed from the priority queue, the highest priority element is removed from the front.
Priority queues are widely used in many computer science applications, including operating systems, networking, and database systems. They are used for tasks such as scheduling, resource allocation, and event handling.
Here’s a simple program using priority queue in C++
#include <iostream>
#include <queue>
int main() {
// Creating a priority queue of integers
std::priority_queue<int> pq;
// Adding elements to the priority queue
pq.push(5);
pq.push(2);
pq.push(10);
pq.push(1);
// Displaying the priority queue
std::cout << "Priority Queue: ";
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
std::cout << std::endl;
return 0;
}The priority queue orders elements based on a comparison function or operator. By default, it uses the < operator, which creates a max heap. The priority queue provides push to insert an element, top to access the highest priority element, and pop to remove the highest priority element.
Deque:
A deque, short for double-ended queue, is a data structure that allows insertion and removal of elements at both ends. It is similar to a queue, but unlike a queue, a deque allows insertion and removal of elements from both the front and the back. This makes it a more versatile data structure that provides efficient insertion and removal operations at both ends.
The deque provides the following operations: push_front, push_back, pop_front, pop_back, front, back, and empty. The push_front operation adds an element to the front of the deque, while the push_back operation adds an element to the back of the deque. The pop_front operation removes an element from the front of the deque, and the pop_back operation removes an element from the back of the deque. The front operation retrieves the element at the front of the deque, and the back operation retrieves the element at the back of the deque. The empty operation checks if the deque is empty or not.
Deques can be implemented using arrays, linked lists, or dynamic arrays such as vectors in C++ or ArrayLists in Java. They are widely used in programming for tasks like implementing algorithms such as breadth-first search and priority queue. They are also used in data structures like stacks and queues, as well as in simulations and games.
The ability to add and remove elements from both ends makes the deque a versatile and efficient data structure in computer science.
Here’s a simple program using deque in C++:
#include <deque>
#include <iostream>
int main() {
// Creating a deque of integers
std::deque<int> dq;
// Adding elements to the front and back of the deque
dq.push_front(1);
dq.push_back(2);
dq.push_front(3);
dq.push_back(4);
// Displaying the deque
std::cout << "Deque: ";
for (auto it = dq.begin(); it != dq.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// Removing elements from the front and back of the deque
dq.pop_front();
dq.pop_back();
// Displaying the updated deque
std::cout << "Updated Deque: ";
for (auto it = dq.begin(); it != dq.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}Circular Queue:
A circular queue, also known as a circular buffer, is a type of queue in where the last element is connected to the first element, forming a circular structure. This means that when the queue is full, new elements will overwrite the oldest elements in a circular fashion. Circular queues are often used in embedded systems and low-level programming where efficient memory usage is crucial.
A circular queue provides the following operations: enqueue, dequeue, front, rear, and empty. The enqueue operation adds an element to the rear of the queue. The dequeue operation removes the element at the front of the queue. The front operation retrieves the value of the element at the front of the queue without removing it. The rear operation retrieves the value of the element at the rear of the queue without removing it. The empty operation checks if the queue is empty or not.
Circular queues are implemented using arrays, and the circular structure is achieved by using the modulo operator to wrap the array indices around. This allows for efficient usage of memory by reusing the empty slots in the queue. Circular queues are widely used in low-level programming, such as in device drivers and operating systems, where efficient memory usage is crucial.
The ability to reuse empty slots in the queue and the efficient memory usage make circular queues an essential data structure in low-level programming.
Here’s a simple program to implement a circular queue in C++:
#include <iostream>
const int MAX_SIZE = 5;
class CircularQueue {
private:
int front, rear, size;
int arr[MAX_SIZE];
public:
CircularQueue() {}
bool is_empty() {}
bool is_full() {}
void enqueue(int val) {}
void dequeue() {}
int get_front() {}
int get_rear() {}
void display() {}
};
int main() {
CircularQueue cq;
// Omitted
std::cout << "Front of queue: " << cq.get_front() << std::endl;
std::cout << "Rear of queue: " << cq.get_rear() << std::endl;
return 0;
}Conclusion
In conclusion, queues are an essential data structure used for storing and managing information in computer science. We explored the workings of queues in detail, including their operations and implementations using STL. We discussed four types of queues: standard queue, priority queue, deque, and circular queue, and their respective applications in programming.
Standard queues are linear data structures that follow the FIFO principle and provide efficient insertion and removal operations. Priority queues are queues where elements have associated priorities, and higher priority elements are placed at the front. Deques allow insertion and removal of elements at both ends and are more versatile than standard queues. Circular queues connect the last element to the first element, forming a circular structure, and allow efficient memory usage by reusing empty slots in the queue.
