Welcome to our exploration of queues and deques using C++. These structures are frequently used in everyday programming, managing everything from system processes to task scheduling. In this lesson, our goal is to understand and implement queues and deques in C++ using the Standard Template Library (STL). Let's dive in!

A queue, akin to waiting in line at a store, operates on the "First In, First Out" or FIFO principle. C++ provides the <queue> header, which includes the std::queue class for implementing queues. You can use the push() method to add items and the pop() method to remove them. The front() method is used to access the first item in the queue without removing it, allowing you to inspect the element that will be dequeued next.

C++
Copy to clipboard
1#include <iostream>
2#include <queue>
3
4int main() {
5    std::queue<std::string> q;
6
7    // Add items to the queue
8    q.push("Apple");
9    q.push("Banana");
10    q.push("Cherry");
11
12    // Remove an item
13    std::cout << q.front() << std::endl;  // Expects "Apple"
14    q.pop();
15
16    return 0;
17}

The dequeued item, "Apple", was the first item we inserted, demonstrating the FIFO principle of queues.

Before trying to remove items from our queue, it's wise to check if the queue is empty to avoid runtime errors when attempting to dequeue from an empty queue.

C++
Copy to clipboard
1#include <iostream>
2#include <queue>
3
4int main() {
5    std::queue<std::string> q;
6
7    // Add items to the queue
8    q.push("Item 1");
9
10    // Check if the queue is non-empty, then dequeue an item
11    if (!q.empty()) {
12        std::cout << q.front() << std::endl;  // Expects "Item 1"
13        q.pop();
14    }
15    
16    q.pop(); // Causes Segmentation fault error, since q is empty now
17
18    return 0;
19}

A deque, or "double-ended queue," allows the addition and removal of items from both ends. C++ provides the <deque> header containing the std::deque class for implementing deques. You can add items to both ends using push_back(), push_front(), and remove them using pop_back(), pop_front(). The back() method provides access to the last item in the deque, allowing you to see what element will be removed if you call pop_back().

C++
Copy to clipboard
1#include <iostream>
2#include <deque>
3
4int main() {
5    std::deque<std::string> d;
6
7    // Add items to the deque
8    d.push_back("Middle");
9    d.push_back("Right end");
10    d.push_front("Left end");
11
12    // Remove an item from the right
13    std::cout << d.back() << std::endl;  // Expects "Right end"
14    d.pop_back();
15
16    // Remove an item from the left
17    std::cout << d.front() << std::endl; // Expects "Left end"
18    d.pop_front();
19
20    return 0;
21}

In C++, the std::deque class provides flexible operations for adding and removing elements from both ends, but it doesn't offer a built-in rotation method. You can achieve rotation by using C++ algorithms, such as std::rotate(), to manually shift items within the deque.

When using std::rotate(), it is essential to understand how reverse iterators like rbegin() and rend() work. rbegin() returns a reverse iterator pointing to the last element in the deque, while rend() denotes the position before the first element. These iterators allow you to traverse the deque in reverse order.

C++
Copy to clipboard
1#include <iostream>
2#include <deque>
3#include <algorithm>
4
5int main() {
6    std::deque<std::string> d = {"Apple", "Banana", "Cherry"};
7
8    // Conceptually rotate the deque to the right by one place
9    // The element at the end moves to the beginning
10    std::rotate(d.rbegin(), d.rbegin() + 1, d.rend());
11
12    // Print the rotated deque
13    for (const auto& item : d) {
14        std::cout << item << " ";  // Expects "Cherry Apple Banana"
15    }
16
17    return 0;
18}

Here, std::rotate() is used to shift all items to the right. By moving rbegin() one step forward to the second position (rbegin() + 1), the last element ("Cherry") cycles to the front, effectively rotating the deque to the right by one position.

Congratulations on completing this detailed study of queues and deques in C++! You've learned their operating principles and how to construct and manipulate them using C++ standard libraries.

Prospectively, our goal is to comprehend additional data structures, opening a world of opportunities to express your ideas and solve complex problems with C++. Are you ready for forthcoming practice exercises to consolidate this new knowledge? Let's continue our exploration!