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.

#include <iostream>
#include <queue>

int main() {
    std::queue<std::string> q;

    // Add items to the queue
    q.push("Apple");
    q.push("Banana");
    q.push("Cherry");

    // Remove an item
    std::cout << q.front() << std::endl;  // Expects "Apple"
    q.pop();

    return 0;
}

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.

#include <iostream>
#include <queue>

int main() {
    std::queue<std::string> q;

    // Add items to the queue
    q.push("Item 1");

    // Check if the queue is non-empty, then dequeue an item
    if (!q.empty()) {
        std::cout << q.front() << std::endl;  // Expects "Item 1"
        q.pop();
    }
    
    q.pop(); // Causes Segmentation fault error, since q is empty now

    return 0;
}

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().

#include <iostream>
#include <deque>

int main() {
    std::deque<std::string> d;

    // Add items to the deque
    d.push_back("Middle");
    d.push_back("Right end");
    d.push_front("Left end");

    // Remove an item from the right
    std::cout << d.back() << std::endl;  // Expects "Right end"
    d.pop_back();

    // Remove an item from the left
    std::cout << d.front() << std::endl; // Expects "Left end"
    d.pop_front();

    return 0;
}