Bài giảng được soạn lại theo kiểu trực quan: hiểu cơ chế FIFO, biết các hàm thành viên, viết được chương trình mô phỏng hàng đợi và áp dụng vào BFS.
Queue hay hàng đợi là cấu trúc dữ liệu lưu trữ các phần tử theo cơ chế FIFO: First In, First Out, nghĩa là phần tử vào trước sẽ được lấy ra trước.
Ví dụ thực tế: xếp hàng mua vé, xếp hàng khám bệnh, hàng đợi in tài liệu.
Trong C++, queue thuộc thư viện chuẩn STL. Có thể dùng bằng cách khai báo:
#include <bits/stdc++.h> using namespace std; queue<int> q; queue<string> dsTen;
Giả sử lần lượt đưa vào queue các số 1, 2, 3, 4, 5. Khi lấy ra, thứ tự nhận được cũng là 1, 2, 3, 4, 5.
| Hàm | Ý nghĩa | Độ phức tạp | Ví dụ |
|---|---|---|---|
| size() | Trả về số lượng phần tử hiện có trong queue. | O(1) | q.size() |
| empty() | Trả về true nếu queue rỗng, ngược lại false. | O(1) | q.empty() |
| push(x) | Đẩy phần tử x vào cuối hàng đợi. | O(1) | q.push(5) |
| pop() | Loại bỏ phần tử ở đầu hàng đợi. | O(1) | q.pop() |
| front() | Truy cập phần tử ở đầu hàng đợi. | O(1) | q.front() |
| back() | Truy cập phần tử ở cuối hàng đợi. | O(1) | q.back() |
| swap(q2) | Hoán đổi nội dung của hai queue cùng kiểu. | O(n) | q.swap(q2) |
#include <bits/stdc++.h> using namespace std; int main(){ queue<int> q; for(int i = 1; i <= 5; i++){ q.push(i); } cout << q.front() << "\n"; // 1 cout << q.back() << "\n"; // 5 q.pop(); cout << q.front() << "\n"; // 2 }
Queue không duyệt bằng chỉ số. Muốn in toàn bộ, ta lấy dần phần tử đầu rồi xóa đi.
while(!q.empty()){ cout << q.front() << " "; q.pop(); }
int x = q.front();
q.pop();
q.push(x);Đây là thao tác dùng trong bài CHUYENDOI: chuyển phần tử đầu tiên về cuối hàng đợi.
Dùng queue để mô phỏng người đến trước được xử lý trước: mua vé, khám bệnh, xử lý yêu cầu.
Queue là cấu trúc dữ liệu cốt lõi của thuật toán BFS để tìm đường đi ngắn nhất theo số cạnh trên đồ thị không trọng số.
Dùng queue để sinh dần các trạng thái theo từng lớp, ví dụ tìm số may mắn nhỏ nhất chia hết cho K.
queue<int> q; vector<int> dist(n + 1, -1); q.push(s); dist[s] = 0; while(!q.empty()){ int u = q.front(); q.pop(); for(int v : adj[u]){ if(dist[v] == -1){ dist[v] = dist[u] + 1; q.push(v); } } }
Sói có một dãy số. Mỗi lần chuyển đổi, phần tử đầu tiên của dãy được đưa về cuối dãy. Sau K lần chuyển đổi, hãy in ra dãy số mới.
5 3 1 2 3 4 5
4 5 1 2 3
Có N người xếp hàng. Người có chiều cao ≤ K được miễn phí và rời hàng. Người có chiều cao > K bị đưa về cuối hàng. Nhân viên kiểm tra M lần. Hãy đếm số lần mỗi người được kiểm tra.
6 3 7 1 4 6 2 3 5
1 2 1 1 1 1
Cho đồ thị vô hướng gồm N thành phố và M con đường. Tìm số cạnh ít nhất để đi từ S đến T. Nếu không có đường đi, in -1.
5 5 1 4 1 2 2 3 3 5 5 4 2 4
2
Ban đầu có N con bò. Nếu một nhóm có thể chia thành hai nhóm sao cho chênh lệch đúng bằng K thì tiếp tục chia. Nếu không chia được thì nhóm dừng lại. Hỏi cuối cùng có bao nhiêu nhóm bò?
6 2
3
Tìm số nhỏ nhất chỉ gồm các chữ số 6 và 8, có không quá 200 chữ số, chia hết cho K. Nếu không tồn tại, in -1.
43
86