deque (Double-Ended Queue) là hàng đợi hai đầu, cho phép chèn/xóa ở cả đầu và cuối với độ phức tạp O(1). Phần tử lưu trữ trong các khối bộ nhớ cố định, hỗ trợ truy cập ngẫu nhiên nhanh.
Các hàm chính
- d.push_front(val) – Thêm vào đầu.
- d.push_back(val) – Thêm vào cuối.
- d.pop_front() – Xóa đầu.
- d.pop_back() – Xóa cuối.
- d.front() / d.back() – Truy cập đầu/cuối.
- d.size() – Số phần tử.
Ví dụ mã: Menu Deque
#include <iostream>
#include <deque>
#include <string>
#include <cstdlib>
using namespace std;
int main() {
deque<int> d;
deque<int>::iterator it;
int c, item;
while (true) {
cout << "1. Kích thước\n2. Thêm cuối\n3. Thêm đầu\n4. Xóa cuối\n5. Xóa đầu\n";
cout << "6. Xem đầu\n7. Xem cuối\n8. Hiển thị\n9. Thoát\n";
cout << "Chọn: "; cin >> c;
switch (c) {
case 1: cout << "Kích thước: " << d.size() << endl; break;
case 2: cout << "Giá trị: "; cin >> item; d.push_back(item); break;
case 3: cout << "Giá trị: "; cin >> item; d.push_front(item); break;
case 4: if (!d.empty()) { item = d.back(); d.pop_back(); cout << item << " đã xóa\n"; } else cout << "Rỗng!\n"; break;
case 5: if (!d.empty()) { item = d.front(); d.pop_front(); cout << item << " đã xóa\n"; } else cout << "Rỗng!\n"; break;
case 6: if (!d.empty()) cout << "Đầu: " << d.front() << endl; else cout << "Rỗng!\n"; break;
case 7: if (!d.empty()) cout << "Cuối: " << d.back() << endl; else cout << "Rỗng!\n"; break;
case 8: cout << "Deque: "; for (it = d.begin(); it != d.end(); ++it) cout << *it << " "; cout << endl; break;
case 9: return 0;
default: cout << "Sai!\n";
}
}
return 0;
}
Kết quả mẫu
Chọn: 1 Kích thước: 0 Chọn: 2 Giá trị: 1 Chọn: 3 Giá trị: 2 Chọn: 6 Đầu: 2 Chọn: 7 Cuối: 1 Chọn: 8 Deque: 2 1 Chọn: 4 1 đã xóa Chọn: 5 2 đã xóa Chọn: 8 Deque: (rỗng) Chọn: 9