Queue & Priority Queue

In this tutorial, we will explore the concepts of queues and priority queues in C++. Queues are fundamental data structures used to manage collections of elements where the first element added is the first one to be removed (FIFO - First-In-First-Out). Priority queues, on the other hand, allow us to manage elements with priorities, ensuring that the highest (or lowest) priority element is always processed first. Both these concepts are crucial in various applications such as scheduling algorithms and task management systems.

Introduction

Queues and priority queues are essential data structures in computer science. They help in organizing tasks or items in a specific order to ensure efficient processing. Understanding how to implement and use them effectively can greatly enhance the performance of your programs.

In this tutorial, we will cover:

• FIFO Queue: Basic operations like push, pop, front, and back.
• Priority Queue: Concepts of min-heaps and max-heaps, and their implementation using the STL.

FIFO Queue

A FIFO queue is a linear data structure where elements are added at one end (rear) and removed from the other end (front). The C++ Standard Template Library (STL) provides a queue container that implements this behavior.

Basic Operations

• push: Adds an element to the rear of the queue.
• pop: Removes the front element from the queue.
• front: Returns the front element without removing it.
• back: Returns the rear element without removing it.
• empty: Checks if the queue is empty.
• size: Returns the number of elements in the queue.

Example Code

Let's see how to use a FIFO queue with some basic operations:

1#include <iostream>
2#include <queue>
3 
4int main() {
5  std::queue<int> q;
6 
7  // Adding elements to the queue
8  q.push(10);
9  q.push(20);
10  q.push(30);
11 
12  // Displaying front and back elements
13  std::cout << "Front element: " << q.front() << std::endl;
14  std::cout << "Back element: " << q.back() << std::endl;
15 
16  // Removing elements from the queue
17  while (!q.empty()) {
18      std::cout << "Popping element: " << q.front() << std::endl;
19      q.pop();
20  }
21 
22  return 0;
23}

Front element: 10
Back element: 30
Popping element: 10
Popping element: 20
Popping element: 30

Explanation

In the example above, we create a queue of integers and perform several operations:

• We add three elements (10, 20, 30) to the queue using push.
• We retrieve and display the front and back elements using front and back.
• We remove all elements from the queue using a loop that continues until the queue is empty, displaying each removed element.

Priority Queue

A priority queue is an extension of a regular queue where each element has a priority associated with it. The element with the highest (or lowest) priority is processed first. In C++, the STL provides a priority_queue container to implement this behavior.

Types of Heaps

Priority queues can be implemented using two types of heaps:

• Max-Heap: The largest element is always at the root.
• Min-Heap: The smallest element is always at the root.

By default, C++'s priority_queue implements a max-heap. However, you can customize it to implement a min-heap by specifying a custom comparator.

Basic Operations

• push: Adds an element to the priority queue.
• pop: Removes the top (highest priority) element from the priority queue.
• top: Returns the top element without removing it.
• empty: Checks if the priority queue is empty.
• size: Returns the number of elements in the priority queue.

Example Code

Let's see how to use a priority queue with both max-heap and min-heap implementations:

Max-Heap Priority Queue

1#include <iostream>
2#include <queue>
3 
4int main() {
5  std::priority_queue<int> pq;
6 
7  // Adding elements to the priority queue
8  pq.push(10);
9  pq.push(20);
10  pq.push(30);
11 
12  // Displaying top element and removing it
13  while (!pq.empty()) {
14      std::cout << "Popping element: " << pq.top() << std::endl;
15      pq.pop();
16  }
17 
18  return 0;
19}

Popping element: 30
Popping element: 20
Popping element: 10

Min-Heap Priority Queue

To implement a min-heap, we need to specify a custom comparator:

1#include <iostream>
2#include <queue>
3 
4int main() {
5  // Custom comparator for min-heap
6  auto cmp = [](int left, int right) { return left > right; };
7  std::priority_queue<int, std::vector<int>, decltype(cmp)> pq(cmp);
8 
9  // Adding elements to the priority queue
10  pq.push(10);
11  pq.push(20);
12  pq.push(30);
13 
14  // Displaying top element and removing it
15  while (!pq.empty()) {
16      std::cout << "Popping element: " << pq.top() << std::endl;
17      pq.pop();
18  }
19 
20  return 0;
21}

Popping element: 10
Popping element: 20
Popping element: 30

Explanation

In the max-heap example, we add three elements (10, 20, 30) to the priority queue. The largest element (30) is always at the top, and it gets popped first.

In the min-heap example, we use a custom comparator to make the priority queue behave as a min-heap. The smallest element (10) is always at the top, and it gets popped first.

Practical Example

Let's create a practical example that combines both FIFO queues and priority queues. We'll simulate a task scheduling system where tasks are processed based on their priorities.

1#include <iostream>
2#include <queue>
3 
4struct Task {
5  int id;
6  int priority;
7 
8  bool operator<(const Task& other) const {
9      return priority < other.priority; // Max-heap
10  }
11};
12 
13int main() {
14  std::priority_queue<Task> taskQueue;
15 
16  // Adding tasks to the queue
17  taskQueue.push({1, 3});
18  taskQueue.push({2, 1});
19  taskQueue.push({3, 4});
20 
21  // Processing tasks based on priority
22  while (!taskQueue.empty()) {
23      Task currentTask = taskQueue.top();
24      std::cout << "Processing task with ID: " << currentTask.id << ", Priority: " << currentTask.priority << std::endl;
25      taskQueue.pop();
26  }
27 
28  return 0;
29}

Processing task with ID: 3, Priority: 4
Processing task with ID: 1, Priority: 3
Processing task with ID: 2, Priority: 1

Explanation

In this example, we define a Task structure with an id and a priority. We overload the < operator to make the priority queue behave as a max-heap based on the priority. Tasks are added to the queue, and they are processed in order of their priorities.

Summary

What's Next?

In the next tutorial, we will explore the Map and Multimap containers in C++. These containers allow us to store key-value pairs and manage them efficiently. Understanding maps is crucial for applications that require fast lookups and associations between keys and values.

Stay tuned!