Bài 7.3: Deque và các thao tác hai đầu

Chào mừng trở lại với series về Cấu trúc dữ liệu và Giải thuật! Chúng ta đã cùng nhau đi qua nhiều cấu trúc dữ liệu cơ bản và quen thuộc như Mảng, Danh sách liên kết, Stack (Ngăn xếp), và Queue (Hàng đợi). Hôm nay, chúng ta sẽ tìm hiểu một cấu trúc dữ liệu vô cùng linh hoạt và mạnh mẽ, là sự kết hợp ưu điểm của cả Stack và Queue: Deque (đọc là "deck").

Bạn đã biết Stack cho phép thêm/xoá chỉ ở một đầu (LIFO), còn Queue cho phép thêm ở cuối và xoá ở đầu (FIFO). Vậy điều gì sẽ xảy ra nếu chúng ta cần một cấu trúc dữ liệu cho phép chúng ta thêm và xoá phần tử một cách hiệu quả ở cả hai đầu? Đó chính là lúc Deque tỏa sáng.

Deque Là Gì?

Deque là viết tắt của Double-Ended Queue (Hàng đợi hai đầu). Đúng như tên gọi, nó là một biến thể của Queue, nhưng thay vì chỉ giới hạn thao tác ở hai đầu khác nhau (thêm cuối, xoá đầu), Deque cho phép chúng ta thực hiện các thao tác thêm và xoá phần tử ở cả hai đầu: đầu trước (front) và đầu sau (back).

Hãy hình dung một đường ống mà bạn có thể đưa đồ vật vào hoặc lấy đồ vật ra từ cả hai phía. Đó chính là Deque!

Sự linh hoạt này làm cho Deque trở thành một công cụ cực kỳ hữu ích trong nhiều tình huống lập trình, bởi vì nó có thể hoạt động như một Stack (thêm/xoá cùng một đầu) hoặc như một Queue (thêm một đầu, xoá đầu kia) một cách hiệu quả.

Các Thao Tác Cơ Bản Trên Deque

Với tính chất "hai đầu", Deque cung cấp các thao tác cơ bản sau:

Thêm phần tử:
- push_front(element): Thêm một phần tử vào đầu trước (front) của deque.
- push_back(element): Thêm một phần tử vào đầu sau (back) của deque.
Xoá phần tử:
- pop_front(): Xoá phần tử ở đầu trước (front) của deque.
- pop_back(): Xoá phần tử ở đầu sau (back) của deque.
Truy cập phần tử:
- front(): Truy cập (nhưng không xoá) phần tử ở đầu trước.
- back(): Truy cập (nhưng không xoá) phần tử ở đầu sau.
- element_at(index): Truy cập phần tử tại một vị trí bất kỳ theo chỉ số (index). Đây là một điểm khác biệt lớn so với danh sách liên kết truyền thống, nơi truy cập theo chỉ số thường kém hiệu quả.
Thông tin khác:
- size(): Trả về số lượng phần tử hiện có trong deque.
- empty(): Kiểm tra xem deque có rỗng hay không.

Deque Được Cài Đặt Như Thế Nào? (Khái niệm)

Làm thế nào mà Deque có thể thêm/xoá ở cả hai đầu và thậm chí là truy cập ngẫu nhiên hiệu quả?

Các cài đặt Deque chuẩn thường không dựa trên danh sách liên kết đơn thuần (vì danh sách liên kết đơn thuần kém hiệu quả cho truy cập ngẫu nhiên và pop_back). Thay vào đó, chúng thường sử dụng một cấu trúc tương tự như mảng động (dynamic array) nhưng được chia thành các khối (blocks) và được quản lý bởi một mảng con trỏ trung tâm.

Cấu trúc này cho phép:

Thêm/xoá ở hai đầu O(1): Khi thêm/xoá ở đầu, chỉ cần điều chỉnh con trỏ hoặc sử dụng các khối trống ở rìa. Khi các khối ở rìa đầy/rỗng, hệ thống sẽ cấp phát/giải phóng các khối mới.
Truy cập ngẫu nhiên O(1): Nhờ cấu trúc dựa trên mảng (dù là mảng của các khối), vị trí của phần tử có thể được tính toán nhanh chóng dựa trên chỉ số và kích thước khối.

Điều này mang lại cho Deque sự cân bằng tuyệt vời: hiệu quả O(1) cho thao tác ở hai đầu (giống danh sách liên kết) và hiệu quả O(1) cho truy cập ngẫu nhiên (giống mảng/vector).

Deque Trong C++: `std::deque`

Trong Thư viện Chuẩn C++ (STL), Deque được triển khai thông qua template class std::deque trong header <deque>. Đây là một container vô cùng mạnh mẽ và linh hoạt mà bạn nên biết.

Để sử dụng std::deque, bạn chỉ cần include header <deque>:

#include <deque>

Giờ chúng ta sẽ cùng xem các thao tác cơ bản với std::deque qua các ví dụ minh họa bằng C++.

Ví dụ 1: Các Thao Tác `push` và `pop` Cơ Bản

Ví dụ này minh họa cách thêm phần tử vào cả hai đầu và sau đó xóa chúng.

#include <iostream>
#include <deque>
#include <string> // Để dùng std::string

int main() {
    // 1. Khởi tạo một deque chứa chuỗi (string)
    std::deque<std::string> myDeque;

    std::cout << "--- Ban dau ---" << std::endl;
    std::cout << "Deque rong? " << (myDeque.empty() ? "Co" : "Khong") << std::endl;
    std::cout << "Kich thuoc: " << myDeque.size() << std::endl;

    // 2. Them phan tu vao dau cuoi (back)
    std::cout << "\n--- Them vao cuoi (push_back) ---" << std::endl;
    myDeque.push_back("Apple");
    myDeque.push_back("Banana");
    std::cout << "Deque sau khi them: ";
    // Duyet qua deque (chung ta se noi them ve duyet sau)
    for (const auto& item : myDeque) {
        std::cout << item << " ";
    }
    std::cout << std::endl;
    std::cout << "Kich thuoc: " << myDeque.size() << std::endl;


    // 3. Them phan tu vao dau truoc (front)
    std::cout << "\n--- Them vao dau (push_front) ---" << std::endl;
    myDeque.push_front("Orange");
    myDeque.push_front("Grape");
     std::cout << "Deque sau khi them: ";
     for (const auto& item : myDeque) {
        std::cout << item << " ";
    }
    std::cout << std::endl;
    std::cout << "Kich thuoc: " << myDeque.size() << std::endl;
    std::cout << "Phan tu dau: " << myDeque.front() << std::endl; // Grape
    std::cout << "Phan tu cuoi: " << myDeque.back() << std::endl;   // Banana

    // 4. Xoa phan tu o dau truoc (front)
    std::cout << "\n--- Xoa phan tu dau (pop_front) ---" << std::endl;
    myDeque.pop_front(); // Xoa Grape
    std::cout << "Deque sau khi xoa dau: ";
     for (const auto& item : myDeque) {
        std::cout << item << " ";
    }
    std::cout << std::endl;
    std::cout << "Kich thuoc: " << myDeque.size() << std::endl;
    std::cout << "Phan tu dau moi: " << myDeque.front() << std::endl; // Orange

    // 5. Xoa phan tu o dau cuoi (back)
    std::cout << "\n--- Xoa phan tu cuoi (pop_back) ---" << std::endl;
    myDeque.pop_back(); // Xoa Banana
    std::cout << "Deque sau khi xoa cuoi: ";
     for (const auto& item : myDeque) {
        std::cout << item << " ";
    }
    std::cout << std::endl;
    std::cout << "Kich thuoc: " << myDeque.size() << std::endl;
    std::cout << "Phan tu cuoi moi: " << myDeque.back() << std::endl; // Apple

    return 0;
}

Giải thích code:

Chúng ta khai báo một std::deque có tên myDeque để chứa các std::string.
Ban đầu, deque rỗng và kích thước là 0.
push_back("Apple") và push_back("Banana") thêm "Apple" rồi "Banana" vào cuối. Deque trở thành: ["Apple", "Banana"].
push_front("Orange") thêm "Orange" vào đầu. Deque: ["Orange", "Apple", "Banana"].
push_front("Grape") thêm "Grape" vào đầu. Deque: ["Grape", "Orange", "Apple", "Banana"].
myDeque.front() trả về phần tử đầu tiên ("Grape").
myDeque.back() trả về phần tử cuối cùng ("Banana").
pop_front() xóa phần tử đầu tiên ("Grape"). Deque: ["Orange", "Apple", "Banana"].
pop_back() xóa phần tử cuối cùng ("Banana"). Deque: ["Orange", "Apple"].
Chúng ta dùng vòng lặp range-based for để in nội dung deque (điều này hoạt động vì std::deque hỗ trợ iterator).

Ví dụ 2: Sử Dụng Deque Như Một Stack (LIFO)

Stack thêm và xoá ở cùng một đầu. Chúng ta có thể mô phỏng hành vi này bằng cách luôn sử dụng push_front và pop_front (hoặc push_back và pop_back).

#include <iostream>
#include <deque>

int main() {
    // Su dung deque nhu mot Stack (them/xoa o dau truoc)
    std::deque<int> myStackLikeDeque;

    // Them vao Stack (push)
    myStackLikeDeque.push_front(10); // Stack: [10]
    myStackLikeDeque.push_front(20); // Stack: [20, 10]
    myStackLikeDeque.push_front(30); // Stack: [30, 20, 10]

    std::cout << "--- Stack (LIFO) su dung Deque ---" << std::endl;
    std::cout << "Phan tu dau (top): " << myStackLikeDeque.front() << std::endl; // 30
    std::cout << "Kich thuoc: " << myStackLikeDeque.size() << std::endl;

    // Xoa khoi Stack (pop)
    myStackLikeDeque.pop_front(); // Xoa 30. Stack: [20, 10]
    std::cout << "Sau khi pop_front(): Phan tu dau moi: " << myStackLikeDeque.front() << std::endl; // 20

    myStackLikeDeque.pop_front(); // Xoa 20. Stack: [10]
    std::cout << "Sau khi pop_front(): Phan tu dau moi: " << myStackLikeDeque.front() << std::endl; // 10

     myStackLikeDeque.pop_front(); // Xoa 10. Stack: []
    std::cout << "Sau khi pop_front(): Kich thuoc moi: " << myStackLikeDeque.size() << std::endl;
    std::cout << "Deque rong? " << (myStackLikeDeque.empty() ? "Co" : "Khong") << std::endl;


    return 0;
}

Giải thích code:

Chúng ta dùng push_front() để "đẩy" (push) các phần tử vào "đỉnh" của stack (tưởng tượng đỉnh stack là đầu trước của deque).
Phần tử được thêm vào cuối cùng (30) nằm ở đầu trước (front()).
Chúng ta dùng pop_front() để "lấy ra" (pop) phần tử từ "đỉnh" của stack (cũng là đầu trước). Phần tử 30 bị xoá trước, sau đó đến 20, cuối cùng là 10, thể hiện đúng nguyên tắc LIFO (Last-In, First-Out).

Ví dụ 3: Sử Dụng Deque Như Một Queue (FIFO)

Queue thêm ở cuối và xoá ở đầu. Chúng ta có thể mô phỏng hành vi này bằng cách sử dụng push_back (thêm vào cuối) và pop_front (xoá ở đầu).

#include <iostream>
#include <deque>

int main() {
    // Su dung deque nhu mot Queue (them cuoi, xoa dau)
    std::deque<double> myQueueLikeDeque;

    // Them vao Queue (enqueue)
    myQueueLikeDeque.push_back(1.1); // Queue: [1.1]
    myQueueLikeDeque.push_back(2.2); // Queue: [1.1, 2.2]
    myQueueLikeDeque.push_back(3.3); // Queue: [1.1, 2.2, 3.3]

    std::cout << "--- Queue (FIFO) su dung Deque ---" << std::endl;
    std::cout << "Phan tu dau (front): " << myQueueLikeDeque.front() << std::endl; // 1.1
    std::cout << "Phan tu cuoi (back): " << myQueueLikeDeque.back() << std::endl;   // 3.3
    std::cout << "Kich thuoc: " << myQueueLikeDeque.size() << std::endl;

    // Xoa khoi Queue (dequeue)
    myQueueLikeDeque.pop_front(); // Xoa 1.1. Queue: [2.2, 3.3]
    std::cout << "Sau khi pop_front(): Phan tu dau moi: " << myQueueLikeDeque.front() << std::endl; // 2.2

    myQueueLikeDeque.pop_front(); // Xoa 2.2. Queue: [3.3]
    std::cout << "Sau khi pop_front(): Phan tu dau moi: " << myQueueLikeDeque.front() << std::endl; // 3.3

    myQueueLikeDeque.pop_front(); // Xoa 3.3. Queue: []
    std::cout << "Sau khi pop_front(): Kich thuoc moi: " << myQueueLikeDeque.size() << std::endl;
    std::cout << "Deque rong? " << (myQueueLikeDeque.empty() ? "Co" : "Khong") << std::endl;


    return 0;
}

Giải thích code:

Chúng ta dùng push_back() để "xếp hàng" (enqueue) các phần tử vào cuối queue.
Phần tử được thêm vào đầu tiên (1.1) nằm ở đầu trước (front()).
Chúng ta dùng pop_front() để "phục vụ" (dequeue) các phần tử từ đầu queue. Phần tử 1.1 bị xoá trước, sau đó đến 2.2, cuối cùng là 3.3, thể hiện đúng nguyên tắc FIFO (First-In, First-Out).

Ví dụ 4: Truy Cập Phần Tử Bất Kỳ và `at()` vs `[]`

std::deque cho phép truy cập phần tử bằng chỉ số, tương tự như std::vector. Bạn có thể sử dụng operator[] hoặc phương thức at(). Sự khác biệt chính là at() sẽ ném ra exception nếu chỉ số không hợp lệ, trong khi [] gây ra hành vi không xác định.

#include <iostream>
#include <deque>
#include <stdexcept> // De bat exception

int main() {
    std::deque<int> numbers = {10, 20, 30, 40, 50};

    std::cout << "--- Truy cap phan tu ---" << std::endl;

    // Truy cap dung chi so bang operator[]
    std::cout << "Phan tu tai chi so 0: " << numbers[0] << std::endl; // 10
    std::cout << "Phan tu tai chi so 2: " << numbers[2] << std::endl; // 30
    std::cout << "Phan tu tai chi so 4: " << numbers[4] << std::endl; // 50

    // Truy cap dung chi so bang at()
    std::cout << "Phan tu tai chi so 0 (dung at()): " << numbers.at(0) << std::endl; // 10
    std::cout << "Phan tu tai chi so 2 (dung at()): " << numbers.at(2) << std::endl; // 30

    // Minh hoa khi truy cap chi so khong hop le
    std::cout << "\n--- Minh hoa truy cap chi so khong hop le ---" << std::endl;
    try {
        // Thao tac nay se an toan neu dung at(), se nem exception
        // Neu dung numbers[10], se gay loi runtime kho doan
        std::cout << "Truy cap tai chi so 10 (dung at()): " << numbers.at(10) << std::endl;
    } catch (const std::out_of_range& e) {
        std::cerr << "Loi: Truy cap vuot qua gioi han (std::out_of_range): " << e.what() << std::endl;
    }

     try {
        // Thao tac nay se an toan neu dung at(), se nem exception
        // Neu dung numbers[-1], se gay loi runtime kho doan
        std::cout << "Truy cap tai chi so -1 (dung at()): " << numbers.at(-1) << std::endl; // Chi so am cung khong hop le
    } catch (const std::out_of_range& e) {
        std::cerr << "Loi: Truy cap vuot qua gioi han (std::out_of_range): " << e.what() << std::endl;
    }


    return 0;
}

Giải thích code:

Chúng ta khởi tạo deque numbers với một số giá trị.
Sử dụng numbers[index] và numbers.at(index) đều cho phép bạn lấy giá trị tại vị trí index (bắt đầu từ 0).
Phần try-catch minh họa điểm khác biệt giữa at() và []. Khi cố gắng truy cập chỉ số 10 (trong khi kích thước chỉ có 5, chỉ số hợp lệ từ 0 đến 4), numbers.at(10) sẽ phát hiện lỗi và ném ra exception std::out_of_range. Nếu bạn dùng numbers[10], chương trình có thể không báo lỗi ngay lập tức nhưng kết quả truy cập sẽ là dữ liệu rác hoặc gây crash chương trình, rất khó để debug.
Tương tự, truy cập chỉ số âm -1 với at() cũng sẽ ném exception.

Lời khuyên: Trong code thực tế, nên ưu tiên dùng .at() khi bạn không chắc chắn chỉ số có hợp lệ hay không, để chương trình có thể bắt lỗi một cách an toàn. Sử dụng [] khi bạn biết chắc chắn chỉ số là hợp lệ, vì nó có thể nhanh hơn một chút do bỏ qua bước kiểm tra biên.

Khi Nào Nên Sử Dụng Deque?

Deque là lựa chọn tuyệt vời khi bạn cần:

Thêm/xoá phần tử hiệu quả ở cả hai đầu: Đây là điểm mạnh nhất của nó. Nếu bạn thường xuyên thêm/xoá ở cả front và back, deque hiệu quả hơn nhiều so với std::vector (thêm/xoá ở front tốn O(n)) hoặc std::list (truy cập ngẫu nhiên tốn O(n)).
Kết hợp hành vi của Stack và Queue: Nếu một phần của chương trình cần stack và phần khác cần queue, thay vì dùng hai cấu trúc dữ liệu riêng biệt, bạn có thể dùng một deque duy nhất.
Truy cập ngẫu nhiên theo chỉ số: Deque cung cấp O(1) cho truy cập ngẫu nhiên, điều mà std::list không thể làm hiệu quả.
Không biết trước số lượng thao tác thêm/xoá ở hai đầu: Deque tự động quản lý bộ nhớ và các khối dữ liệu để đảm bảo hiệu suất O(1) cho các thao tác ở rìa.

So Sánh Ngắn Gọn Với Các Container Khác Trong C++ STL

std::vector: Tốt nhất cho truy cập ngẫu nhiên và thêm/xoá ở cuối (O(1) amortized). Thêm/xoá ở đầu hoặc giữa rất chậm (O(n)) vì phải di chuyển toàn bộ phần tử còn lại.
std::list: Tốt nhất cho thêm/xoá ở bất kỳ đâu trong danh sách (O(1)) nếu bạn đã có iterator trỏ đến vị trí đó. Rất tệ cho truy cập ngẫu nhiên (O(n)).
std::deque: Cân bằng giữa vector và list. Tốt cho thêm/xoá ở hai đầu (O(1)) và tốt cho truy cập ngẫu nhiên (O(1)). Thêm/xoá ở giữa vẫn chậm (O(n)).

Chọn std::deque khi bạn cần hiệu suất cao ở cả hai đầu và vẫn muốn khả năng truy cập theo chỉ số.

Bài tập ví dụ:

Nhảy Cao

Trong một buổi tập luyện, FullHouse Dev gặp một vận động viên nhảy cao đầy tham vọng. Vận động viên này có sở thích đặc biệt là nhảy từ tòa nhà này sang tòa nhà khác, nhưng chỉ nhảy lên những tòa nhà cao hơn và dừng lại khi không còn tòa nhà cao hơn nào. Năng lượng cần thiết cho mỗi hành trình được tính bằng phép XOR của độ cao tất cả các tòa nhà mà vận động viên nhảy qua.

Bài toán

Tìm năng lượng tối đa cần thiết nếu vận động viên có thể bắt đầu hành trình từ bất kỳ tòa nhà nào.

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên \(n\) - số lượng tòa nhà.
Dòng thứ hai chứa \(n\) số nguyên, biểu thị độ cao của các tòa nhà.

OUTPUT FORMAT:

Một số nguyên duy nhất là năng lượng tối đa cần thiết cho bất kỳ hành trình nào.

Ràng buộc:

\(1 \leq n \leq 10^5\)
\(1 \leq height_i \leq 10^9\)

Ví dụ

INPUT

5
1 2 3 8 6

OUTPUT

Gi��i thích

Nếu bắt đầu từ tòa nhà 1, năng lượng cần thiết là 1 ^ 2 ^ 3 ^ 8 = 8
Nếu bắt đầu từ tòa nhà 2, năng lượng cần thiết là 2 ^ 3 ^ 8 = 9
Nếu bắt đầu từ tòa nhà 3, năng lượng cần thiết là 3 ^ 8 = 11
Tương tự, từ tòa nhà 8 và 6, năng lượng cần thiết lần lượt là 8 và 6
Năng lượng tối đa cần thiết cho hành trình là từ tòa nhà 3 với giá trị 11
Vì vậy đáp án là 11. Đây là hướng dẫn giải bài toán "Nhảy Cao" một cách ngắn gọn:

Phân tích hành trình: Từ mỗi tòa nhà, vận động viên nhảy đến tòa nhà tiếp theo bên phải mà cao hơn. Hành trình dừng lại khi không có tòa nhà nào như vậy ở bên phải. Điều này định nghĩa một chuỗi các tòa nhà duy nhất cho mỗi điểm bắt đầu.
Xác định "tòa nhà nhảy tiếp theo": Đối với mỗi tòa nhà i, ta cần tìm chỉ số j nhỏ nhất sao cho j > i và height[j] > height[i]. Nếu không tồn tại j như vậy, hành trình kết thúc tại i. Việc tìm "phần tử lớn hơn tiếp theo bên phải" này là một bài toán kinh điển có thể giải hiệu quả.
Sử dụng Stack để tìm "tòa nhà nhảy tiếp theo": Duyệt qua các tòa nhà từ phải sang trái (từ n-1 về 0). Sử dụng một stack để lưu trữ các chỉ số của các tòa nhà theo thứ tự chiều cao giảm dần. Khi xét tòa nhà i:
- Bỏ ra khỏi stack tất cả các chỉ số k mà height[k] <= height[i]. Các tòa nhà này không thể là đích nhảy tiếp theo từ i (hoặc bất kỳ tòa nhà nào bên trái i mà cao hơn i).
- Nếu stack không rỗng sau khi bỏ các phần tử, đỉnh stack chính là chỉ số của tòa nhà đầu tiên bên phải i mà cao hơn height[i]. Lưu chỉ số này (ví dụ vào mảng next_higher[i]).
- Nếu stack rỗng, không có tòa nhà nào bên phải i cao hơn nó. Lưu một giá trị đặc biệt (ví dụ -1) vào next_higher[i].
- Cuối cùng, đẩy chỉ số i vào stack.
- Bước này mất thời gian O(N).
Tính năng lượng cho mỗi điểm bắt đầu (Quy hoạch động/Đệ quy có nhớ):
- Gọi Energy[i] là năng lượng thu được khi bắt đầu từ tòa nhà i.
- Nếu next_higher[i] là giá trị đặc biệt (-1), thì Energy[i] = height[i].
- Nếu next_higher[i] = j (j != -1), thì Energy[i] = height[i] ^ Energy[j].
- Ta có thể tính Energy[i] cho tất cả i bằng cách duyệt từ phải sang trái (từ n-1 về 0), đảm bảo khi tính Energy[i] thì Energy[next_higher[i]] (nếu có) đã được tính rồi.
- Bước này mất thời gian O(N).
Tìm năng lượng tối đa: Sau khi tính được Energy[i] cho tất cả các tòa nhà i từ 0 đến n-1, kết quả là giá trị lớn nhất trong mảng Energy. Bước này mất thời gian O(N).
Tổng kết:
- Sử dụng Stack để tiền xử lý, tìm next_higher cho mỗi tòa nhà (O(N)).
- Sử dụng mảng/đệ quy có nhớ (tính từ phải sang trái) để tính năng lượng Energy[i] cho mỗi điểm bắt đầu (O(N)).
- Tìm giá trị lớn nhất trong mảng Energy (O(N)).
- Độ phức tạp tổng thể: O(N).

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.