🚍 Bài giảng: Cấu trúc dữ liệu Queue (Hàng đợi)

Đề: Có n thao tác “E x” (enqueue x) và “D” (dequeue). Sau khi thực hiện, in các phần tử còn lại trong queue.

Ý tưởng: Dùng queue<int>, đọc từng thao tác, thực hiện tương ứng.

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n; cin>>n; queue<int> q;
  while(n--){
    char c; cin>>c;
    if(c=='E'){int x;cin>>x;q.push(x);}
    else if(c=='D' && !q.empty()) q.pop();
  }
  while(!q.empty()){cout<<q.front()<<' ';q.pop();}
}

Ví dụ:
Input: 5
E 3
E 5
D
E 2
E 1 Output: 5 2 1

Đề: Cho đồ thị vô hướng n đỉnh m cạnh. In thứ tự duyệt BFS bắt đầu từ đỉnh 1.

Ý tưởng: Dùng queue lưu các đỉnh đang chờ duyệt; khi lấy ra thì duyệt toàn bộ đỉnh kề chưa thăm.

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m;cin>>n>>m;
  vector<vector<int>> g(n+1);
  for(int i=0,u,v;i<m;i++){cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}
  vector<int> vis(n+1);
  queue<int> q;
  q.push(1); vis[1]=1;
  while(!q.empty()){
    int u=q.front(); q.pop(); cout<<u<<' ';
    for(int v:g[u]) if(!vis[v]){ vis[v]=1; q.push(v); }
  }
}

Kết quả: Thứ tự duyệt theo tầng (1 → các hàng xóm → hàng xóm của hàng xóm...)

Đề: Cho ma trận n x m gồm các ô 0 (đi được) và 1 (tường). Tìm khoảng cách ngắn nhất từ ô (1,1) đến (n,m), di chuyển 4 hướng.

Ý tưởng: Dùng thuật toán loang (BFS): bắt đầu từ (1,1), mỗi bước lan sang 4 ô lân cận hợp lệ, lưu khoảng cách bằng queue.

#include <bits/stdc++.h>
using namespace std;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int main(){
  int n,m;cin>>n>>m;
  vector<string> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  vector<vector<int>> d(n, vector<int>(m,-1));
  queue<pair<int,int>> q;
  if(a[0][0]=='0'){ q.push({0,0}); d[0][0]=0; }
  while(!q.empty()){
    auto [x,y]=q.front(); q.pop();
    for(int k=0;k<4;k++){
      int nx=x+dx[k], ny=y+dy[k];
      if(nx<0||ny<0||nx>=n||ny>=m) continue;
      if(a[nx][ny]=='1'||d[nx][ny]!=-1) continue;
      d[nx][ny]=d[x][y]+1;
      q.push({nx,ny});
    }
  }
  cout<<d[n-1][m-1];
}

Ví dụ:
Input:
4 4
0001
1100
0010
0000
Output: 6

Giải thích: BFS giúp tìm đường ngắn nhất vì mỗi ô được thăm lần đầu tiên bằng đường đi ngắn nhất.

Đề: Cho lưới n×m gồm các ô: 0 – chưa nhiễm, 1 – nhiễm virus ban đầu. Mỗi phút, virus lan sang 4 hướng. Tính thời gian lan đến toàn bộ ô có thể.

Ý tưởng: Dùng BFS đa nguồn: ban đầu enqueue tất cả ô có virus (1), sau đó lan đồng thời.

#include <bits/stdc++.h>
using namespace std;
int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};
int main(){
  int n,m;cin>>n>>m;
  vector<vector<int>> a(n, vector<int>(m));
  queue<pair<int,int>> q;
  for(int i=0;i<n;i++) for(int j=0;j<m;j++){
    cin>>a[i][j];
    if(a[i][j]==1) q.push({i,j});
  }
  int t=-1;
  while(!q.empty()){
    int sz=q.size(); t++;
    while(sz--){
      auto [x,y]=q.front(); q.pop();
      for(int k=0;k<4;k++){
        int nx=x+dx[k], ny=y+dy[k];
        if(nx<0||ny<0||nx>=n||ny>=m) continue;
        if(a[nx][ny]!=0) continue;
        a[nx][ny]=1; q.push({nx,ny});
      }
    }
  }
  cout<<t;
}

Giải thích: Duyệt từng “lớp” lan truyền trong queue. Mỗi vòng while tương ứng một phút lan toàn mạng.

Đề: Cho ma trận có các điểm xuất phát (S) và điểm đích (T). Tính khoảng cách ngắn nhất từ bất kỳ S đến bất kỳ T.

Ý tưởng: - Đưa tất cả điểm S vào queue ban đầu (multi-source BFS). - Lan loang đến khi gặp ô T đầu tiên → dừng lại.

#include <bits/stdc++.h>
using namespace std;
int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};
int main(){
  int n,m;cin>>n>>m;
  vector<string> a(n); for(auto &s:a) cin>>s;
  queue<pair<int,int>> q; vector<vector<int>> d(n,vector<int>(m,-1));
  for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(a[i][j]=='S'){q.push({i,j}); d[i][j]=0;}
  while(!q.empty()){
    auto [x,y]=q.front(); q.pop();
    if(a[x][y]=='T'){ cout<<d[x][y]; return 0; }
    for(int k=0;k<4;k++){
      int nx=x+dx[k], ny=y+dy[k];
      if(nx<0||ny<0||nx>=n||ny>=m) continue;
      if(a[nx][ny]=='#'||d[nx][ny]!=-1) continue;
      d[nx][ny]=d[x][y]+1; q.push({nx,ny});
    }
  }
  cout<<-1;
}

Ứng dụng: Các bài như “Tìm khoảng cách từ nhiều ngọn lửa đến người”, “Thoát khỏi mê cung”, “Lũ lụt lan dần”,... đều dùng dạng này.