Deque là cấu trúc dữ liệu cho phép thêm, xóa phần tử ở cả đầu và cuối. Đây là công cụ rất mạnh để xử lý hàng đợi linh hoạt, cửa sổ trượt, truy vấn min/max đoạn liên tiếp và một số bài toán tối ưu.
Deque là viết tắt của double-ended queue, nghĩa là hàng đợi hai đầu. Các phần tử được sắp thành một dãy có đầu và cuối.
Khác với queue chỉ thêm ở cuối và lấy ở đầu, deque cho phép thêm/xóa ở cả hai phía.
Deque nằm trong thư viện chuẩn C++ và thường dùng chung với #include <bits/stdc++.h>.
#include <bits/stdc++.h>
using namespace std;
int main(){
deque<int> d;
return 0;
}| Hàm / thao tác | Ý nghĩa | Độ phức tạp |
|---|---|---|
| size() | Trả về số lượng phần tử hiện có trong deque. | O(1) |
| empty() | Trả về true nếu deque rỗng, ngược lại false. | O(1) |
| d[i], at(i) | Truy cập phần tử ở vị trí i, đánh số từ 0. | O(1) |
| push_back(x) | Thêm x vào cuối deque. | O(1) |
| push_front(x) | Thêm x vào đầu deque. | O(1) |
| pop_back() | Xóa phần tử cuối deque. | O(1) |
| pop_front() | Xóa phần tử đầu deque. | O(1) |
| front() | Lấy giá trị phần tử đầu. | O(1) |
| back() | Lấy giá trị phần tử cuối. | O(1) |
| insert(iterator,x) | Chèn x vào trước vị trí iterator. | O(n) |
| erase(l,r) | Xóa các phần tử từ iterator l đến trước iterator r. | O(n) |
| clear() | Xóa toàn bộ phần tử. | O(n) |
| swap() | Hoán đổi hai deque. | O(n) |
Đoạn chương trình sau minh họa cách thêm, xóa và truy cập phần tử trong deque.
#include <bits/stdc++.h>
using namespace std;
int main(){
deque<int> d;
for(int i = 1; i <= 5; i++)
d.push_back(i); // d = {1, 2, 3, 4, 5}
d.push_front(7); // d = {7, 1, 2, 3, 4, 5}
cout << d.size() << '\n'; // 6
cout << d.back() << '\n'; // 5
cout << d[4] << '\n'; // 4
d.insert(d.begin(), 1); // d = {1, 7, 1, 2, 3, 4, 5}
cout << d.front() << '\n';// 1
d.erase(d.begin() + 1, d.begin() + 5);
// xóa vị trí 1 đến 4, d = {1, 4, 5}
d.clear();
cout << d.empty(); // 1
return 0;
}Dùng push_front để đảo thứ tự một nhóm và push_back để giữ thứ tự nhóm còn lại.
Dùng deque lưu chỉ số ứng viên để tìm min/max trong mỗi đoạn dài k với độ phức tạp O(n).
Một số bài DP có điều kiện đoạn gần nhất có thể dùng deque để lấy giá trị tốt nhất trong cửa sổ.
Cho một dãy số. Hãy in ra tất cả các số lẻ trước, sau đó đến tất cả các số chẵn trên cùng một dòng. Các số lẻ phải ở thứ tự ngược lại so với dãy ban đầu, còn các số chẵn vẫn giữ nguyên thứ tự.
6 1 4 6 7 4 6
7 1 4 6 4 6
Cho dãy A gồm N phần tử và số nguyên dương k. Với mỗi vị trí i từ k đến N, hãy tìm giá trị nhỏ nhất trong đoạn từ i-k+1 đến i.
8 4 1 3 5 7 4 5 9 5
1 3 4 4 4
Rồng thần có thể phun lửa tối đa N lần, sát thương lần i là A[i]. Tuy nhiên, rồng không thể phun lửa K lần chí mạng liên tiếp. Hãy tính tổng sát thương lớn nhất có thể gây ra.
7 3 1 4 2 3 6 5 9
23
Cho luống hoa gồm N bông theo thứ tự, mỗi bông có độ xinh đẹp. Chọn hai khóm hoa rời nhau, mỗi khóm gồm các bông liên tiếp, sao cho trong mỗi khóm chênh lệch độ xinh đẹp giữa hai bông bất kỳ không quá K. Hãy chọn được nhiều bông nhất.
5 2 1 3 2 5 4
5
Lớp có N học sinh ngồi quanh bàn tròn. Thầy chọn một học sinh bắt đầu, sau đó đi theo chiều kim đồng hồ, mỗi bạn được hướng dẫn đúng Δ giây. Học sinh thứ i sau khi được hướng dẫn cần thêm A[i] giây để viết xong chương trình. Hãy chọn vị trí bắt đầu để thời gian tất cả hoàn thành là nhỏ nhất.
Dãy A không nhập trực tiếp mà được xác định bởi công thức: A[i] = (p * i) mod m + q.
5 3 2 1 9
18