Container adapters là một mẫu thiết kế cho phép chuyển đổi giao diện hiện có thành giao diện mà người dùng mong muốn, tương tự như việc sử dụng các ổ cắm đa năng.

Bài viết này tập trung vào việc giới thiệu về Stack, Queue và priority_queue, tất cả đều là container adapters.

2. Stack

2.1 Tổng Quan Về Stack

Stack là cấu trúc dữ liệu dạng ngăn xếp, tuân theo nguyên tắc "LIFO" (Last In First Out), tương tự như một chai nước.

2.2 Các Phương Thức Thường Gặp Trong Stack

2.3 Bài Tập Ví Dụ: Stack Tìm Giá Trị Nhỏ Nhất

Đề bài yêu cầu tạo một stack đặc biệt có thể trả về giá trị nhỏ nhất trong stack với độ phức tạp O(1).

Lời giải bao gồm việc duy trì hai stack: một stack chính và một stack phụ để lưu trữ các giá trị nhỏ nhất.

class StackNhoNhat {
public:
    void themPhanTu(int giaTri) {
        _stackChinh.push(giaTri);
        if (_stackPhu.empty() || giaTri <= _stackPhu.top()) {
            _stackPhu.push(giaTri);
        }
    }
    void xoaPhanTu() {
        if (!_stackChinh.empty() && _stackChinh.top() == _stackPhu.top()) {
            _stackPhu.pop();
        }
        _stackChinh.pop();
    }
    int layGiaTriNhoNhat() {
        return _stackPhu.top();
    }
private:
    stack<int> _stackChinh;
    stack<int> _stackPhu;
};

2.4 Bài Tập Ví Dụ: Kiểm Tra Thứ Tự Đẩy và Lấy Ra Của Stack

Đề bài yêu cầu kiểm tra xem một chuỗi lấy ra có hợp lệ với chuỗi đẩy vào hay không.

class KiemTraThuTu {
public:
    bool kiemTra(vector<int>& dayVao, vector<int>& layRa) {
        stack<int> stackTam;
        size_t viTriLayRa = 0;
        for (const auto& phanTu : dayVao) {
            stackTam.push(phanTu);
            while (!stackTam.empty() && stackTam.top() == layRa[viTriLayRa]) {
                ++viTriLayRa;
                stackTam.pop();
            }
        }
        return stackTam.empty();
    }
};

3. Queue

3.1 Giới Thiệu Về Queue

Queue là một container adapter tuân theo nguyên tắc "FIFO" (First In First Out).

3.2 Các Phương Thức Thường Gặp Trong Queue