Как устроена queue?

Как устроена queue

Queue (очередь) — это одна из фундаментальных структур данных, используемая в программировании. В C++ STL очередь реализована в виде адаптера контейнера, работающего по принципу FIFO (First In First Out) — первый добавленный элемент удаляется первым.

Базовые принципы FIFO

Очередь работает как реальная очередь в магазине: кто пришёл первый, тот и выходит первым.

Добавление (enqueue)      Удаление (dequeue)
в конец (rear)            из начала (front)
       ↓                        ↓
    [1][2][3][4][5]   →    [3][4][5]
         ↑                        ↑
      front                     front

Структура std::queue

std::queue — это шаблонный адаптер, обычно построенный на основе std::deque (double-ended queue):

#include <queue>

// Стандартное использование
std::queue<int> q;

// Можно использовать разные базовые контейнеры
std::queue<int, std::vector<int>> q_vector;     // На основе vector
std::queue<int, std::list<int>> q_list;         // На основе list
std::queue<int, std::deque<int>> q_deque;       // На основе deque (по умолчанию)

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

std::queue<int> q;

// push() — добавить элемент в конец
q.push(10);
q.push(20);
q.push(30);

// front() — получить первый элемент
int first = q.front();  // 10

// back() — получить последний элемент
int last = q.back();    // 30

// pop() — удалить первый элемент
q.pop();                // Теперь первый = 20

// empty() — проверка пустоты
if (q.empty()) {
    std::cout << "Очередь пуста\n";
}

// size() — количество элементов
std::cout << q.size();  // 2

Внутреннее устройство

По умолчанию queue построена на основе deque, что обеспечивает эффективность:

Вутреннее представление (std::deque):
┌─────────────────────────────────────┐
│ [buf1] [buf2] [buf3] [buf4] [buf5] │
│  1-64  65-128 129-192 193-256 ...  │
│   ↑                         ↑       │
 │ front_ptr                back_ptr  │
└─────────────────────────────────────┘

Временная сложность

• push() — O(1) амортизированная константа
• pop() — O(1) амортизированная константа
• front() — O(1)
• back() — O(1)
• empty() — O(1)
• size() — O(1)

Практические примеры

Пример 1: Обработка задач в очереди

std::queue<std::string> tasks;

tasks.push("Load data");
tasks.push("Process");
tasks.push("Save");

while (!tasks.empty()) {
    std::string task = tasks.front();
    std::cout << "Executing: " << task << "\n";
    tasks.pop();
}

Пример 2: Моделирование системы обслуживания

struct Customer {
    int id;
    std::string name;
};

std::queue<Customer> service_queue;

service_queue.push({1, "Alice"});
service_queue.push({2, "Bob"});
service_queue.push({3, "Charlie"});

while (!service_queue.empty()) {
    Customer current = service_queue.front();
    std::cout << "Serving: " << current.name << "\n";
    service_queue.pop();
}

Пример 3: Обход дерева в ширину (BFS)

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

void bfs(TreeNode* root) {
    std::queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        
        std::cout << node->val << " ";
        
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

Сравнение с другими структурами

Приоритетная очередь (Priority Queue)

Зачастую нужна очередь с приоритетами:

std::priority_queue<int> pq;  // Max-heap по умолчанию

pq.push(10);
pq.push(5);
pq.push(20);

while (!pq.empty()) {
    std::cout << pq.top() << " ";  // 20, 10, 5
    pq.pop();
}

// Min-heap
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(10);
min_pq.push(5);
min_pq.push(20);

while (!min_pq.empty()) {
    std::cout << min_pq.top() << " ";  // 5, 10, 20
    min_pq.pop();
}

Циклическая очередь

В низкоуровневом программировании часто используется циклическая очередь с фиксированным размером:

template<typename T, size_t Size>
class CircularQueue {
private:
    std::array<T, Size> buffer;
    size_t front_idx = 0;
    size_t back_idx = 0;
    size_t count = 0;
    
public:
    void push(const T& value) {
        if (count == Size) return;  // Очередь полна
        buffer[back_idx] = value;
        back_idx = (back_idx + 1) % Size;
        count++;
    }
    
    T pop() {
        if (count == 0) throw std::runtime_error("Empty queue");
        T value = buffer[front_idx];
        front_idx = (front_idx + 1) % Size;
        count--;
        return value;
    }
    
    bool empty() const { return count == 0; }
};

Потокобезопасная очередь

Для многопоточных приложений:

template<typename T>
class ThreadSafeQueue {
private:
    mutable std::mutex mutex;
    std::queue<T> data_queue;
    std::condition_variable cond;
    
public:
    void push(T value) {
        std::lock_guard<std::mutex> lk(mutex);
        data_queue.push(std::move(value));
        cond.notify_one();
    }
    
    void wait_and_pop(T& value) {
        std::unique_lock<std::mutex> lk(mutex);
        cond.wait(lk, [this] { return !data_queue.empty(); });
        value = std::move(data_queue.front());
        data_queue.pop();
    }
};

Практические применения

1. Обработка задач — системы обработки заданий
2. Буферизация — обмен данными между потоками
3. BFS (поиск в ширину) — обход графов
4. Message queues — системы сообщений
5. Принтеры и сетевые пакеты — реальное чередование обслуживания

Вывод

Queue — это простая и мощная структура данных, реализующая принцип FIFO. В C++ STL это адаптер, обычно построенный на основе deque, обеспечивающий O(1) для всех основных операций. Queue широко используется в системах обработки задач, графических алгоритмах и многопоточном программировании.