Dequeue và Priority Queue trong C++

Queue là FIFO. Hai biến thể: Dequeue (double-ended queue) và Priority Queue.

Dequeue (Hàng đợi hai đầu)

Cho phép thêm/xóa ở cả hai đầu. Có 2 cặp front/rear. C++ STL cung cấp <deque>.

Ví dụ Dequeue

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

void hienThi(deque<int> q) {
    for (auto it = q.begin(); it != q.end(); ++it)
        cout << *it << " ";
    cout << endl;
}

int main() {
    deque<int> q;
    q.push_back(10); q.push_front(20);
    q.push_back(30); q.push_front(15);
    
    cout << "Queue: "; hienThi(q);
    cout << "Kích thước: " << q.size() << endl;
    cout << "Phần tử vị trí 2: " << q.at(2) << endl;
    cout << "Phần tử đầu: " << q.front() << endl;
    cout << "Phần tử cuối: " << q.back() << endl;
    
    cout << "Xóa đầu: "; q.pop_front(); hienThi(q);
    cout << "Xóa cuối: "; q.pop_back(); hienThi(q);
    return 0;
}

Kết quả Dequeue

Queue: 15 20 10 30
Kích thước: 4
Phần tử vị trí 2: 10
Phần tử đầu: 15
Phần tử cuối: 30
Xóa đầu: 20 10 30
Xóa cuối: 20 10

Priority Queue (Hàng đợi ưu tiên)

Mỗi phần tử có ưu tiên. Xóa phần tử ưu tiên cao nhất trước. STL priority_queue dùng max-heap (giá trị lớn = ưu tiên cao).

Ví dụ Priority Queue

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

void hienThiPQ(priority_queue<int> q) {
    while (!q.empty()) {
        cout << q.top() << " ";
        q.pop();
    }
    cout << endl;
}

int main() {
    priority_queue<int> q;
    q.push(10); q.push(20); q.push(30); q.push(5); q.push(1);
    cout << "Queue: "; hienThiPQ(q);
    cout << "Kích thước: " << q.size() << endl;
    cout << "Đỉnh (max): " << q.top() << endl;
    cout << "Xóa: "; q.pop(); hienThiPQ(q);
    cout << "Xóa: "; q.pop(); hienThiPQ(q);
    return 0;
}

Kết quả Priority Queue

Queue: 30 20 10 5 1
Kích thước: 5
Đỉnh (max): 30
Xóa: 20 10 5 1
Xóa: 10 5 1