🧮 Bài giảng: Cấu trúc dữ liệu DEQUE (Double-Ended Queue)

Deque là Queue mở rộng: thay vì chỉ thao tác ở cuối (enqueue) và đầu (dequeue), deque cho phép thao tác ở cả hai đầu.

💡 Deque = kết hợp sức mạnh của cả Stack (LIFO) và Queue (FIFO).

I. Deque là gì?

push_front(x) — thêm vào đầu
push_back(x) — thêm vào cuối
pop_front() — xoá đầu
pop_back() — xoá cuối
front() — xem đầu
back() — xem cuối

II. Minh hoạ trực quan

III. Cú pháp deque trong C++

#include 
using namespace std;

int main() {
    deque dq;

    dq.push_front(3);  // [3]
    dq.push_back(5);   // [3, 5]
    dq.push_front(2);  // [2, 3, 5]

    cout << dq.front(); // 2
    cout << dq.back();  // 5
}

IV. Mô phỏng Deque (có highlight code)

🔧 Thao tác

💡 Bấm nút để xem mô phỏng + highlight code.

💻 Code

deque dq;                 // tạo deque
int x = input;                   // đọc
dq.push_front(x);               // thêm đầu
int x = input;                   // đọc
dq.push_back(x);                // thêm cuối
if(!dq.empty())                // kiểm tra
dq.pop_front();               // xoá đầu
if(!dq.empty())                // kiểm tra
dq.pop_back();                // xoá cuối
dq.front(); dq.back();        // xem 2 đầu

📊 Deque

V. Khi nào dùng Deque?

Deque không phải để “học cho biết”, mà là công cụ giải quyết nhóm bài toán rất đặc thù. Một học sinh giỏi phải nhận ra deque ngay khi đọc đề: bài này có cửa sổ trượt? có hai đầu? có loại bỏ những phần tử không optimal? Nếu có → chắc chắn cần dùng Deque.

🔍 Các tín hiệu mạnh nhận biết bài toán dùng Deque

1) Bài toán cửa sổ trượt (Sliding Window)
➡ Xuất hiện từ khóa: “trong mỗi đoạn dài k…”, “cửa sổ trượt kích thước k”, “đoạn con cố định k”.
👉 Deque giúp duy trì phần tử tối ưu và loại bỏ phần tử quá cũ trong O(1).

2) Bài toán hai đầu (trái/phải)
➡ Đề có cụm: “chọn phần tử trái hoặc phải”, “hai người chơi chọn đầu nào có lợi hơn”.
👉 Deque mô phỏng đúng bản chất thao tác hai đầu.

3) Loại bỏ phần tử không còn hữu dụng (Monotonic Deque)
➡ Đề yêu cầu: “giữ lại phần tử tốt nhất”, “loại bỏ phần tử kém tối ưu”.
👉 Dùng pop_back để duy trì tính đơn điệu.

4) Mô phỏng thực tế có hai phía vào/ra
➡ Ví dụ: xe vào/ra từ hai cổng, xử lý khách từ cả hai đầu.
👉 Deque mô phỏng chính xác hành vi này.

5) Thuật toán 0-1 BFS
➡ Đồ thị có cạnh trọng số chỉ 0 hoặc 1.
👉 Cạnh trọng số 0: push_front, trọng số 1: push_back. Giải nhanh hơn Dijkstra.

VI. Bài tập luyện tập – đầy đủ theo phân dạng

Dưới đây là hệ thống bài tập cho học sinh từ mức độ cơ bản → nâng cao, mỗi bài đều có nhận dạng đề & giải thích tại sao phải dùng deque.

📘 Nhóm 1 — Bài cơ bản về Deque

1️⃣ Bài 1: Mô phỏng deque với các thao tác cơ bản

Nhận dạng: Đề xã xuất hiện các thao tác push_front, push_back, pop_front, pop_back → bắt buộc dùng deque.

#include 
using namespace std;

int main() {
    int n; cin >> n;
    deque dq;
    while(n--) {
        string s; cin >> s;
        if(s=="push_front"){int x; cin >> x; dq.push_front(x);}
        else if(s=="push_back"){int x; cin >> x; dq.push_back(x);}
        else if(s=="pop_front" && !dq.empty()) dq.pop_front();
        else if(s=="pop_back" && !dq.empty()) dq.pop_back();
    }
    for(int x : dq) cout << x << " ";
}

2️⃣ Bài 2: Đảo ngược dãy bằng deque

Nhận dạng: Đảo dãy = đẩy phần tử vào đầu → dùng push_front.

Ý tưởng: Đọc từng số a → push_front(a).

📗 Nhóm 2 — Hai đầu (Game / Greedy)

3️⃣ Bài 3: Hai người lấy số — chọn trái hoặc phải

Nhận dạng: Từ khóa: “chọn trái hoặc phải”, “chọn đầu có giá trị lớn”. Đây là dạng bài kinh điển → hàng đợi 2 đầu.

// Người A luôn lấy số lớn hơn ở hai đầu
#include 
using namespace std;

int main() {
    int n; cin >> n;
    deque dq(n);
    for(int i=0;i> dq[i];

    long long A = 0;
    while(!dq.empty()) {
        if(dq.front() > dq.back())
            A += dq.front(), dq.pop_front();
        else
            A += dq.back(), dq.pop_back();
    }
    cout << A;
}

4️⃣ Bài 4: Kiểm tra chuỗi palindrome

Nhận dạng: So sánh đầu – cuối ⇒ pop_front/pop_back.

📙 Nhóm 3 — Sliding Window (dạng quan trọng nhất)

5️⃣ Bài 5: Tìm max trong mỗi đoạn dài k – O(n)

Nhận dạng: Có cụm từ “mỗi đoạn dài k” → dạng cửa sổ trượt.

Lý do: Deque loại bỏ phần tử quá cũ bằng pop_front và loại bỏ phần tử kém optimal bằng pop_back.

#include 
using namespace std;

int main(){
    int n,k; cin >> n >> k;
    vector a(n);
    for(int &x:a) cin >> x;

    deque dq;
    for(int i=0;i= k-1)
            cout << a[dq.front()] << " ";
    }
}

6️⃣ Bài 6: Tìm min trong mỗi đoạn dài k

Nhận dạng: Giống bài tìm max, nhưng thay điều kiện so sánh.

7️⃣ Bài 7: Đếm số phần tử ≥ X trong mỗi đoạn k

Nhận dạng: Cửa sổ trượt + cần loại bỏ phần tử cũ.

Ý tưởng: Duy trì deque chứa chỉ số phần tử ≥ X.

🐓 Nhóm 4 — Monotonic Deque nâng cao (Greedy / DP)

8️⃣ Bài 8: Giữ dãy đơn điệu để tối ưu hoá

Nhận dạng: Đề yêu cầu loại bỏ phần tử “kém optimal” → pop_back.

Ý tưởng: Tạo deque tăng dần hoặc giảm dần.

🐔 Nhóm 5 — Mô phỏng thực tế

9️⃣ Bài 9: Trạm thu phí hai đầu

Nhận dạng: Xe vào/ra từ trái hoặc phải → đúng bản chất deque.

🐉 Nhóm 6 — 0–1 BFS (chuyên đề HSG – quan trọng)

🔟 Bài 10: 0–1 BFS tìm đường đi ngắn nhất

Nhận dạng: Đề có trọng số là 0 hoặc 1 → tuyệt đối phải dùng deque.

if(w == 0) dq.push_front(v);
else dq.push_back(v);

Ưu điểm: Chạy O(V+E), nhanh hơn Dijkstra rất nhiều.

1️⃣1️⃣ Bài 11: Robot di chuyển trong lưới – phí 0 hoặc 1

Nhận dạng: “Bấm nút không tốn phí, di chuyển tốn 1” → đúng mẫu 0-1 BFS.

VII. Tổng kết

Deque mạnh nhất trong bài cửa sổ trượt và mô phỏng hai đầu.
Monotonic deque giải quyết nhiều bài greedy/DP trong O(n).
0–1 BFS là dạng nâng cao, rất quan trọng trong HSG.

🎯 Nắm chắc các dạng bài trên nghĩa là bạn đã khai thác tối đa sức mạnh của deque.