Cấu Trúc Dữ Liệu Hàng Đợi (Queue, Deque) & Monotonic Deque

1. Bản chất cấu trúc dữ liệu hàng đợi (queue & deque)

1.1. Hàng đợi chuẩn (queue — FIFO)

Hàng đợi hoạt động theo nguyên lý FIFO (First In, First Out — Vào trước, Ra trước):

• Phần tử được thêm vào ở đuôi (push), và được lấy ra ở đầu (pop).
• Đây là cấu trúc dữ liệu nền tảng của thuật toán Tìm kiếm theo chiều rộng (BFS).

1.2. Hàng đợi hai đầu (double-ended queue — Deque)

std::deque cho phép thực hiện thêm và xóa phần tử ở CẢ HAI ĐẦU với độ phức tạp tối ưu $\mathcal{O}(1)$:

• push_front(), pop_front(): Thao tác ở đầu hàng đợi.
• push_back(), pop_back(): Thao tác ở đuôi hàng đợi.

2. Kỹ thuật deque cửa sổ trượt min/max $\mathcal{O}(N)$ (Sliding Window Monotonic Deque)

2.1. Bản chất bài toán

• Cho mảng $A$ gồm $N$ phần tử và số $K$. Cần tìm giá trị nhỏ nhất (hoặc lớn nhất) trong mọi cửa sổ trượt độ dài $K$: $[i-K+1 \dots i]$ ($K \le i \le N$).
• Cách dùng Multiset / Priority Queue: Mất $\mathcal{O}(N \log K)$.
• Cách dùng Monotonic Deque: Đạt thời gian tối ưu tuyệt đối $\mathcal{O}(N)$ tuyến tính!

2.2. Bất biến 3 bước duy trì min cửa sổ

Tại mỗi vị trí $i$ khi phần tử $A[i]$ bước vào:

1. Loại bỏ phần tử hết hạn (Out of Window): Nếu phần tử ở đầu dq.front() < i - K + 1 $\implies$ dq.pop_front().
2. Duy trì tính đơn điệu tăng: Trong khi !dq.empty() và $A[\text{dq.back()}] \ge A[i] \implies$ dq.pop_back() (vì $A[i]$ vừa nhỏ hơn vừa tồn tại lâu hơn các phần tử ở đuôi).
3. Thêm phần tử mới và lấy đáp án: dq.push_back(i). Khi $i \ge K-1$, giá trị nhỏ nhất của cửa sổ hiện tại chính là $A[\text{dq.front()}]$.

3. Ứng dụng nền tảng: Tìm đường đi ngắn nhất bằng queue (BFS nhập môn)

• Trên đồ thị không có trọng số (hoặc đồ thị lưới di chuyển 4 hướng có chi phí mỗi bước bằng 1), thuật toán BFS sử dụng Queue luôn đảm bảo:

Lần đầu tiên một đỉnh $v$ được lấy ra khỏi Queue, khoảng cách $dist[v]$ chắc chắn là khoảng cách ngắn nhất từ đỉnh nguồn $S$.

4. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Bẫy gọi q.front() khi Queue rỗng: * Tương tự Stack, gọi q.front() hoặc q.pop() khi q.empty() == true gây Segmentation Fault.
2. Bẫy lưu giá trị thay vì lưu chỉ số trong Monotonic Deque: * Nếu chỉ lưu giá trị $A[i]$, ta không thể kiểm tra xem phần tử ở đầu dq.front() đã vượt ra khỏi phạm vi cửa sổ $i - K + 1$ hay chưa. * Quy tắc bắt buộc: Luôn lưu chỉ số $i$ vào trong Deque!
3. Bẫy quên đánh dấu visited ngay khi push vào Queue trong BFS: * Nếu chờ đến khi pop mới đánh dấu visited[u] = true, một đỉnh có thể bị đẩy vào Queue hàng chục lần từ các đỉnh lân cận $\implies$ Bùng nổ bộ nhớ và thời gian (TLE/MLE). * Quy tắc sống còn: Bắt buộc gán visited[v] = true ngay tại thời điểm q.push(v).

5. Mẫu cài đặt chuẩn thi đấu (competitive templates)

Mẫu 1: Min trên mọi cửa sổ trượt độ dài k bằng Monotonic Deque $\mathcal{O}(N)$

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    if (!(cin >> n >> k)) return 0;

    if (n <= 0 || k <= 0 || k > n) return 0;

    vector<long long> a(n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];

    }

    deque<int> dq; // Lưu chỉ số, duy trì A[dq[i]] tăng dần

    vector<long long> result;

    for (int i = 0; i < n; ++i) {
        // 1. Xóa phần tử quá hạn cửa sổ
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // 2. Duy trì tính đơn điệu tăng
        while (!dq.empty() && a[dq.back()] >= a[i]) {
            dq.pop_back();
        }

        // 3. Thêm phần tử hiện tại
        dq.push_back(i);

        // 4. Ghi nhận kết quả khi cửa sổ đủ kích thước k
        if (i >= k - 1) {
            result.push_back(a[dq.front()]);
        }
    }

    for (int i = 0; i < (int)result.size(); ++i) {
        cout << result[i] << (i + 1 == (int)result.size() ? "" : " ");
    }
    cout << "\n";

    return 0;
}

Mẫu 2: BFS tìm bước đi ngắn nhất từ 1 đến n

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    if (n <= 0) return 0;

    vector<vector<int>> adj(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> dist(n + 1, -1);

    queue<int> q;

    // Khởi tạo gốc 1
    dist[1] = 0;
    q.push(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (dist[v] == -1) { // Chưa thăm
                dist[v] = dist[u] + 1;
                q.push(v); // Đánh dấu ngay khi push
            }
        }
    }

    cout << dist[n] << "\n";
    return 0;
}