thuattoan.dev

Level 2 · Cấu trúc dữ liệu

Queue

FIFO, deque, ứng dụng trong BFS.

Độ khó: Dễ Visualizer tương tác5 bài luyện tập

Ý tưởng chính

Queue tuân theo nguyên tắc First-In-First-Out (FIFO), là cấu trúc bắt buộc để cài đặt BFS đúng thứ tự.

Hình dung

Hàng người chờ mua trà sữa: ai đến trước được phục vụ trước, người mới luôn đứng vào cuối hàng.

Cách hoạt động

  1. 1

    enqueue(x): thêm x vào cuối hàng.

  2. 2

    dequeue(): lấy phần tử ở đầu hàng ra.

  3. 3

    Cài đặt bằng mảng vòng: dùng head (đầu) và tail (vị trí ghi tiếp); khi chạm cuối mảng thì quay về 0.

  4. 4

    Deque (hàng đợi hai đầu) cho phép thêm/lấy ở cả đầu lẫn cuối.

Độ phức tạp

enqueue, dequeue đều O(1).

Khi nào dùng

Xử lý theo thứ tự đến trước — đặc biệt là BFS. Deque dùng cho cửa sổ trượt (min/max trong k phần tử gần nhất) và BFS 0-1.

Lỗi hay gặp

  • Dùng vector/list rồi xoá phần tử đầu (erase(begin), list.pop(0)) — mỗi lần tốn O(n).
  • Mảng vòng: quên lấy % CAP khi tăng head/tail.

Liên hệ thực tế

Ứng dụng thực tế

Kỹ thuật này xuất hiện ở đâu ngoài đời — để bạn có sẵn một hình ảnh cụ thể khi học.

  • Hàng đợi in, hàng đợi xử lý đơn

    Lệnh in gửi trước in trước, đơn hàng đặt trước được xử lý trước — đúng nguyên tắc FIFO.

  • Message queue giữa các dịch vụ

    Hệ thống backend dùng RabbitMQ, Amazon SQS… để một dịch vụ gửi việc và dịch vụ khác lần lượt xử lý.

  • Bộ đệm vòng (ring buffer)

    Bộ đệm âm thanh, bàn phím, card mạng dùng mảng vòng với head/tail như trong visualizer, không cần cấp phát thêm bộ nhớ.

  • Deque: cửa sổ dữ liệu gần nhất

    Theo dõi giá thấp/cao nhất của cổ phiếu trong N phút gần nhất, hay giữ N mục vừa xem gần đây.

Xem thuật toán chạy

Minh hoạ từng bước

Chạy tự động hoặc đi từng bước; theo dõi hình minh hoạ, lời giải thích, giá trị biến và dòng code tương ứng cùng lúc.

Tự làm

Luyện tập trên Codeforces

Sắp xếp từ dễ đến khó theo rating, mỗi bài kèm tóm tắt đề. Bí thì mở gợi ý — có 3 mức, từ hướng suy nghĩ tới gần lời giải.

  • Rating 1300

    Queue Sort(mở Codeforces trong tab mới)

    Cho mảng a. Mỗi thao tác lấy phần tử đầu đưa về cuối, rồi đổi chỗ nó với phần tử đứng trước chừng nào nó nhỏ hơn hẳn phần tử đó. Tìm số thao tác ít nhất để mảng không giảm, hoặc −1.

    Test mẫu & giải thích
    Input
    5
5
6 4 1 2 5
7
4 5 3 7 8 6 2
6
4 3 1 2 6 4
4
5 2 4 2
3
2 2 3
    Output
    2
6
-1
-1
0

    1. Test 1

      Xét test đầu a = [6,4,1,2,5]. Thao tác 1: đưa 6 xuống cuối được [4,1,2,5,6], rồi so 6 với phần tử liền trước là 5 — vì 6 không nhỏ hơn 5 nên dừng, mảng thành [4,1,2,5,6]. Thao tác 2: đưa 4 xuống cuối được [1,2,5,6,4], rồi cho 4 nổi ngược lên: 4<6 nên đổi chỗ thành [1,2,5,4,6], tiếp tục 4<5 nên đổi chỗ thành [1,2,4,5,6], đến khi so với 2 thì 4 không nhỏ hơn 2 nên dừng. Sau đúng 2 thao tác mảng đã không giảm nên đáp án là 2.

    2. Test 2

      Với test cuối [2,2,3] đã sẵn không giảm (2≤2≤3) nên không cần thao tác nào, đáp án 0.

  • Rating 1500

    Queue(mở Codeforces trong tab mới)

    Có n sinh viên xếp hàng; mỗi người ghi lại ID người đứng ngay trước và ngay sau mình (0 nếu không có). Các cặp ghi chép được cho theo thứ tự bất kỳ — khôi phục thứ tự hàng.

    Test mẫu & giải thích
    Input
    4
92 31
0 7
31 0
7 141
    Output
    92 7 31 141

    Bốn dòng ghi nhận (prev,next) là: (92,31), (0,7), (31,0), (7,141), nhưng dòng nào ứng với sinh viên nào phải suy ra. Dòng (0,7) có prev=0 nên chủ của nó là người đầu hàng — giá trị 92 là ID của người này vì 92 chỉ xuất hiện ở vị trí prev của dòng khác mà không hề xuất hiện ở vị trí next nào, tức không ai đứng trước 92; next=7 cho biết người đứng ngay sau là sinh viên 7. Dòng (92,31) có prev=92 khớp với người vừa tìm nên đây là dòng của sinh viên 7, và next=31 cho biết người kế tiếp là 31. Dòng (7,141) có prev=7 nên là dòng của sinh viên 31, next=141 cho người cuối cùng; dòng còn lại (31,0) khớp làm dòng của 141 với next=0 xác nhận đây là cuối hàng. Ghép lại ta được thứ tự 92 7 31 141 đúng như output.

  • Rating 1600

    Customer Service(mở Codeforces trong tab mới)

    Có n hàng đợi, ban đầu rỗng, và n thời điểm. Ở thời điểm j, hàng i thêm a_{i,j} khách, rồi bạn chọn đúng một hàng để phục vụ hết (về 0); mỗi hàng được chọn đúng một lần. Tối đa hoá MEX của số khách còn lại ở các hàng.

    Test mẫu & giải thích
    Input
    4
2
1 2
2 1
2
10 10
10 10
3
2 3 3
4 4 1
2 1 1
4
4 2 2 17
1 9 3 1
5 5 5 11
1 2 1 1
    Output
    2
1
3
3

    Ở test đầu n=2, hàng 1 nhận (1,2) và hàng 2 nhận (2,1) qua 2 thời điểm; ta cần chọn thứ tự phục vụ (mỗi hàng đúng 1 lần) sao cho MEX của số khách còn lại là lớn nhất. Nếu phục vụ hàng 2 trước: tại t=1 hàng1 có 1 khách, hàng2 có 2 khách rồi bị phục vụ về 0; tại t=2 hàng1 nhận thêm 2 thành 3 khách rồi bị phục vụ về 0, hàng2 nhận thêm 1 thành 1 khách và không bị phục vụ nữa. Kết quả còn lại là {hàng1=0, hàng2=1}, MEX của {0,1} là 2, khớp đáp án. Phương án ngược lại (phục vụ hàng1 trước) chỉ cho {0,2} với MEX=1 nên kém hơn.

  • Rating 1700

    Processing Queries(mở Codeforces trong tab mới)

    Server xử lý từng truy vấn một, hàng chờ chứa tối đa b truy vấn. Truy vấn i đến lúc t_i và cần d_i thời gian: server rảnh thì xử lý ngay, hàng chờ còn chỗ thì vào chờ, không thì bị từ chối. In thời điểm hoàn thành từng truy vấn hoặc −1.

    Test mẫu & giải thích
    Input
    5 1
2 9
4 8
10 9
15 2
19 1
    Output
    11 19 -1 21 22

    1. Test 1

      Với b=1 và 5 truy vấn, truy vấn 1 đến t=2 lúc server rảnh nên xử lý ngay, xong lúc 2+9=11.

    2. Test 2

      Truy vấn 2 đến t=4 khi server đang bận và hàng chờ còn trống (0<1) nên vào chờ. Lúc 11 server rảnh, lấy truy vấn 2 ra xử lý, xong lúc 11+8=19.

    3. Test 3

      Truy vấn 3 đến t=10 khi hàng chờ đã có truy vấn 2 (đầy) nên bị từ chối, in -1.

    4. Test 4

      Truy vấn 4 đến t=15 lúc server bận nhưng hàng chờ trống nên được xếp hàng. Lúc 19 server rảnh xử lý truy vấn 4, xong lúc 19+2=21.

    5. Test 5

      Truy vấn 5 đến t=19 nhưng server đã bận với truy vấn 4 nên phải chờ, rồi được xử lý lúc 21, xong lúc 21+1=22 — khớp dãy kết quả 11 19 -1 21 22.

  • Rating 2300

    Queue in the Train(mở Codeforces trong tab mới)

    Tàu có n ghế, hành khách i muốn đi lấy nước lúc t_i, mỗi lần mất p phút và chỉ một người ở bình nước. Hành khách chỉ rời ghế nếu mọi ghế bên trái đều đang có người; người có chỉ số nhỏ hơn được ưu tiên. In thời điểm mỗi hành khách lấy xong nước.

    Test mẫu & giải thích
    Input
    5 314
0 310 942 628 0
    Output
    314 628 1256 942 1570

    1. Test 1

      Với p=314, ghế 1 và 5 muốn đi lúc t=0 nhưng chỉ ghế 1 được đi ngay vì bên trái nó không có ghế nào (rỗng), lấy nước xong lúc 0+314=314; ghế 5 phải chờ vì ghế 1 đang trống (không thoả điều kiện mọi ghế bên trái có người).

    2. Test 2

      Ghế 2 muốn đi lúc t=310 nhưng ghế 1 khi đó vẫn trống nên cũng phải chờ đến khi ghế 1 trở về lúc 314. Lúc 314, cả ghế 2 và ghế 5 đều đủ điều kiện (ghế bên trái đã có người) nhưng ghế 2 có chỉ số nhỏ hơn nên được ưu tiên, đi và xong lúc 314+314=628.

    3. Test 3

      Quá trình lặp lại tương tự: ghế 4 (muốn lúc 628) và ghế 5 cùng đủ điều kiện lúc 628 nhưng ghế 4 được ưu tiên, xong lúc 942.

    4. Test 4

      Sau đó ghế 3 (muốn lúc 942) ưu tiên hơn ghế 5, xong lúc 1256.

    5. Test 5

      Cuối cùng ghế 5 mới được đi lúc 1256, xong lúc 1256+314=1570 — khớp thứ tự output 314 628 1256 942 1570.