Как устроена очередь (queue) в C++?

Очередь (queue) в C++ — это контейнер-адаптер из STL, работающий по принципу FIFO (First In, First Out). Реализована как обертка над другими контейнерами, по умолчанию используется deque.

Основные операции:

• push() — добавление элемента в конец очереди (enqueue).
• pop() — удаление элемента из начала очереди (dequeue).
• front() — доступ к первому элементу (тому, который будет извлечен следующим).
• back() — доступ к последнему добавленному элементу.
• empty() — проверка на пустоту.
• size() — получение количества элементов.

Пример использования std::queue:

#include <iostream>
#include <queue>

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

    // Добавление элементов
    q.push(10); // Очередь: [10]
    q.push(20); // Очередь: [10, 20]
    q.push(30); // Очередь: [10, 20, 30]

    std::cout << "Первый элемент (front): " << q.front() << std::endl; // 10
    std::cout << "Последний элемент (back): " << q.back() << std::endl; // 30

    // Удаление элементов
    q.pop(); // Удаляем 10
    std::cout << "После pop(), front: " << q.front() << std::endl; // 20

    std::cout << "Размер очереди: " << q.size() << std::endl; // 2

    // Очистка очереди
    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    // Вывод: 20 30

    return 0;
}

Особенности реализации:

1. Базовый контейнер: Можно указать при создании:

   std::queue<int, std::list<int>> q_list;     // На основе list
   std::queue<int, std::deque<int>> q_deque;   // На основе deque (по умолчанию)
   // std::queue<int, std::vector<int>> q_vec; // Ошибка: vector не имеет pop_front()

2. Ограничения:
   • Нет прямого доступа к элементам кроме первого и последнего
   • Нет итераторов
   • Для обхода очереди нужно последовательно извлекать элементы
3. Временная сложность: Все операции O(1) при использовании deque или list в качестве базового контейнера.

Типичные сценарии использования:

• Обработка задач в порядке поступления
• Реализация BFS (поиска в ширину) для графов
• Буферизация данных в producer-consumer паттернах
• Обработка сообщений в системах очередей

Ручная реализация на связном списке:

template<typename T>
class ListQueue {
private:
    struct Node {
        T data;
        Node* next;
        Node(T val) : data(val), next(nullptr) {}
    };

    Node* frontNode;
    Node* rearNode;
    int count;

public:
    ListQueue() : frontNode(nullptr), rearNode(nullptr), count(0) {}

    ~ListQueue() {
        while (!isEmpty()) {
            dequeue();
        }
    }

    void enqueue(T value) {
        Node* newNode = new Node(value);
        if (isEmpty()) {
            frontNode = rearNode = newNode;
        } else {
            rearNode->next = newNode;
            rearNode = newNode;
        }
        count++;
    }

    T dequeue() {
        if (isEmpty()) throw std::runtime_error("Queue is empty");

        Node* temp = frontNode;
        T value = temp->data;
        frontNode = frontNode->next;

        if (frontNode == nullptr) {
            rearNode = nullptr;
        }

        delete temp;
        count--;
        return value;
    }

    T front() const {
        if (isEmpty()) throw std::runtime_error("Queue is empty");
        return frontNode->data;
    }

    bool isEmpty() const { return frontNode == nullptr; }
    int size() const { return count; }
};