Deque - Double-ended Queue

📖 Giới thiệu

Deque (pronounced "deck") là viết tắt của "double-ended queue" - hàng đợi hai đầu. Cho phép thêm/xóa hiệu quả ở cả hai đầu, kết hợp ưu điểm của vector (random access) và list (insertion/deletion hiệu quả).

Ví dụ đơn giản đầu tiên

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> dq;
    
    // Thêm vào hai đầu
    dq.push_back(20);    // [20]
    dq.push_front(10);   // [10, 20]
    dq.push_back(30);    // [10, 20, 30]
    dq.push_front(5);    // [5, 10, 20, 30]
    
    // Truy cập random
    cout << "dq[1] = " << dq[1] << endl;
    
    // Hiển thị
    cout << "Deque: ";
    for (int x : dq) {
        cout << x << " ";
    }
    cout << endl;
    
    return 0;
}

🔧 Cú pháp

Khai báo Deque

#include <deque>

deque<int> empty_deque;                  // Deque rỗng
deque<int> sized_deque(5);              // 5 phần tử mặc định
deque<int> init_deque(5, 10);           // 5 phần tử, giá trị 10
deque<int> copy_deque{1, 2, 3, 4, 5};   // Khởi tạo với list

Các phương thức

// Thêm/xóa hai đầu
deque.push_front(value);     // Thêm đầu
deque.push_back(value);      // Thêm cuối
deque.pop_front();           // Xóa đầu
deque.pop_back();            // Xóa cuối

// Random access
deque[index];                // Truy cập trực tiếp
deque.at(index);            // Truy cập an toàn
deque.front();              // Phần tử đầu
deque.back();               // Phần tử cuối

// Insert/erase
deque.insert(iterator, value);
deque.erase(iterator);

💻 Ví dụ minh họa

Ví dụ 1: Sliding Window Maximum

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

class SlidingWindowMaximum {
private:
    deque<int> window_indices;  // Lưu chỉ số, không phải giá trị
    vector<int> data;
    int window_size;
    
public:
    SlidingWindowMaximum(const vector<int>& input, int k) 
        : data(input), window_size(k) {
        cout << "🪟 Khởi tạo Sliding Window với size = " << k << endl;
    }
    
    vector<int> get_all_maximums() {
        vector<int> result;
        
        for (int i = 0; i < data.size(); i++) {
            // Xóa các phần tử ngoài window
            while (!window_indices.empty() && 
                   window_indices.front() <= i - window_size) {
                window_indices.pop_front();
            }
            
            // Xóa các phần tử nhỏ hơn phần tử hiện tại
            while (!window_indices.empty() && 
                   data[window_indices.back()] <= data[i]) {
                window_indices.pop_back();
            }
            
            // Thêm phần tử hiện tại
            window_indices.push_back(i);
            
            // Nếu đã đủ window size, thêm max vào result
            if (i >= window_size - 1) {
                result.push_back(data[window_indices.front()]);
            }
        }
        
        return result;
    }
    
    void demo() {
        cout << "Dữ liệu: ";
        for (int x : data) cout << x << " ";
        cout << endl;
        
        vector<int> maximums = get_all_maximums();
        
        cout << "Maximum trong từng window " << window_size << ":" << endl;
        for (int i = 0; i < maximums.size(); i++) {
            cout << "Window [" << i << ".." << (i + window_size - 1) << "]: ";
            for (int j = i; j < i + window_size; j++) {
                cout << data[j] << " ";
            }
            cout << "→ Max = " << maximums[i] << endl;
        }
    }
};

int main() {
    cout << "=== SLIDING WINDOW MAXIMUM ===" << endl;
    
    vector<int> data = {1, 3, -1, -3, 5, 3, 6, 7};
    SlidingWindowMaximum swm(data, 3);
    swm.demo();
    
    return 0;
}

🏋️ Thực hành

Bài tập 1: Palindrome Checker

Sử dụng deque để kiểm tra palindrome hiệu quả

Bài tập 2: Undo/Redo với giới hạn

Tạo system với giới hạn số operations

Bài tập 3: Multi-level Browser History

History với nhiều tabs, forward/back cho từng tab

📋 Tóm tắt

1. Deque: Double-ended queue với random access
2. Ưu điểm: Thêm/xóa O(1) hai đầu, random access O(1)
3. Nhược điểm: Memory layout phức tạp hơn vector
4. Dùng khi: Cần thao tác hai đầu + random access

Bài tiếp theo: Set - Unique sorted elements.