Bài 7.2. Queue và các bài toán xử lý hàng đợi

Chào mừng trở lại với series blog về Cấu trúc dữ liệu và Giải thuật! Sau khi khám phá sức mạnh của Stack (Ngăn xếp) với nguyên tắc LIFO (Last-In, First-Out), hôm nay chúng ta sẽ làm quen với một người anh em thân thiết nhưng hoạt động theo nguyên tắc hoàn toàn khác biệt và cũng không kém phần quan trọng: Queue (Hàng đợi).

Nếu bạn đã từng xếp hàng ở siêu thị, chờ lấy vé xem phim, hay đơn giản là chờ đến lượt để rửa xe, thì bạn đã trực tiếp trải nghiệm nguyên lý của Queue rồi đấy! Queue mô phỏng chính xác những tình huống "xếp hàng" trong thế giới thực.

Queue là gì? Nguyên tắc Hoạt động "FIFO"

Queue, hay còn gọi là Hàng đợi, là một cấu trúc dữ liệu tuyến tính hoạt động theo nguyên tắc FIFO - First-In, First-Out. Điều này có nghĩa là phần tử được thêm vào trước sẽ được loại bỏ ra trước.

Hãy hình dung một hàng người đang chờ:

Người đến đầu tiên sẽ là người được phục vụ đầu tiên.
Người đến cuối cùng sẽ là người được phục vụ cuối cùng.

Queue có hai đầu chính:

Front (hoặc Head): Đầu nơi các phần tử được lấy ra (served).
Back (hoặc Rear, Tail): Đầu nơi các phần tử được thêm vào (enqueued).

Không giống như Stack chỉ thao tác ở một đầu (top), Queue yêu cầu thao tác ở cả hai đầu để duy trì nguyên tắc FIFO.

Các Thao tác Cơ bản của Queue

Mọi cấu trúc dữ liệu đều có những thao tác cốt lõi để làm việc với nó. Với Queue, chúng ta có các thao tác chính sau:

enqueue(item): Thêm một phần tử (item) vào cuối hàng đợi (tại vị trí back).
dequeue(): Loại bỏ phần tử ở đầu hàng đợi (tại vị trí front) và trả về giá trị của nó. Nếu hàng đợi rỗng, thao tác này thường gây ra lỗi hoặc trả về giá trị đặc biệt báo hiệu không thành công.
front() (hoặc peek()): Truy cập giá trị của phần tử ở đầu hàng đợi (tại vị trí front) mà không loại bỏ nó. Tương tự dequeue, nếu hàng đợi rỗng, thao tác này có thể gây lỗi.
isEmpty(): Kiểm tra xem hàng đợi có rỗng hay không. Trả về true nếu rỗng, false nếu không rỗng.
size(): Trả về số lượng phần tử hiện có trong hàng đợi.

Ví dụ về luồng hoạt động:

Queue rỗng: []
enqueue(10): Thêm 10 vào cuối. Queue: [10] (front=10, back=10)
enqueue(20): Thêm 20 vào cuối. Queue: [10, 20] (front=10, back=20)
enqueue(30): Thêm 30 vào cuối. Queue: [10, 20, 30] (front=10, back=30)
front(): Xem phần tử đầu tiên -> trả về 10. Queue vẫn là: [10, 20, 30]
dequeue(): Lấy phần tử đầu tiên ra. Queue: [20, 30] (front=20, back=30)
dequeue(): Lấy phần tử đầu tiên ra. Queue: [30] (front=30, back=30)
isEmpty(): Kiểm tra -> trả về false.
dequeue(): Lấy phần tử đầu tiên ra. Queue: []
isEmpty(): Kiểm tra -> trả về true.
dequeue(): Lấy phần tử ra khi rỗng -> Lỗi (hoặc hành vi không xác định).

Triển khai Queue bằng C++

Trong C++, chúng ta có nhiều cách để triển khai Queue. Phổ biến nhất là sử dụng container có sẵn trong Thư viện Chuẩn (STL) hoặc tự xây dựng từ đầu bằng mảng hoặc danh sách liên kết.

Cách 1: Sử dụng `std::queue` trong STL (Cách nên dùng!)

Đây là cách đơn giản nhất và hiệu quả nhất trong hầu hết các trường hợp thực tế. std::queue là một adapter container, nghĩa là nó không tự quản lý dữ liệu mà sử dụng một container cơ bản (mặc định là std::deque, hoặc bạn có thể chỉ định std::list) và cung cấp giao diện Queue (FIFO).

Ưu điểm:

Dễ sử dụng.
Đã được tối ưu hóa và kiểm thử kỹ lưỡng.
An toàn và đáng tin cậy.

Nhược điểm:

Bạn không thấy "bên trong" nó hoạt động như thế nào (có thể không tốt cho việc học cơ bản, nhưng lại tốt cho việc sử dụng thực tế).

Hãy xem một ví dụ sử dụng std::queue:

#include <iostream>
#include <queue> // Bao gồm thư viện queue

int main() {
    // 1. Khai báo một hàng đợi chứa số nguyên
    std::queue<int> myQueue;

    // 2. Thêm phần tử vào hàng đợi (enqueue)
    std::cout << "--- Thao tac Enqueue ---" << std::endl;
    myQueue.push(10);
    std::cout << "Them 10. Kich thuoc hien tai: " << myQueue.size() << std::endl;
    myQueue.push(20);
    std::cout << "Them 20. Kich thuoc hien tai: " << myQueue.size() << std::endl;
    myQueue.push(30);
    std::cout << "Them 30. Kich thuoc hien tai: " << myQueue.size() << std::endl;

    // 3. Xem phan tu o dau hang doi (front/peek)
    if (!myQueue.empty()) {
        std::cout << "\nPhan tu o dau hang doi: " << myQueue.front() << std::endl;
        // std::queue cung cap back() de xem phan tu cuoi
        std::cout << "Phan tu o cuoi hang doi: " << myQueue.back() << std::endl;
    }

    // 4. Kiem tra hang doi co rong khong (isEmpty)
    std::cout << "\nHang doi co rong khong? " << (myQueue.empty() ? "Co" : "Khong") << std::endl;

    // 5. Lay kich thuoc (size)
    std::cout << "Kich thuoc hang doi: " << myQueue.size() << std::endl;

    // 6. Loai bo phan tu khoi hang doi (dequeue)
    std::cout << "\n--- Thao tac Dequeue ---" << std::endl;
    while (!myQueue.empty()) {
        int item = myQueue.front(); // Lay gia tri phan tu dau tien
        myQueue.pop();              // Loai bo phan tu dau tien
        std::cout << "Lay ra phan tu: " << item << ". Kich thuoc con lai: " << myQueue.size() << std::endl;
    }

    // 7. Kiem tra lai sau khi lay het
    std::cout << "\nHang doi co rong khong sau khi lay het? " << (myQueue.empty() ? "Co" : "Khong") << std::endl;

    // Thu lay phan tu khi hang doi rong (se gay ra loi runtime neu khong kiem tra empty())
    // if (!myQueue.empty()) {
    //     myQueue.front(); // DANG CHU Y: Dong nay se loi neu hang doi rong
    // }

    return 0;
}

Giải thích code std::queue:

#include <queue>: Dòng này cần thiết để sử dụng lớp std::queue.
std::queue<int> myQueue;: Khai báo một đối tượng myQueue kiểu std::queue chuyên chứa các phần tử kiểu int.
myQueue.push(value);: Tương ứng với thao tác enqueue. Thêm value vào cuối hàng đợi.
myQueue.front();: Tương ứng với thao tác front()/peek(). Trả về tham chiếu đến phần tử đầu tiên mà không xóa.
myQueue.back();: Trả về tham chiếu đến phần tử cuối cùng mà không xóa.
myQueue.pop();: Tương ứng với thao tác dequeue. Xóa phần tử đầu tiên khỏi hàng đợi. Lưu ý: pop() chỉ xóa, không trả về giá trị. Do đó, bạn thường phải gọi front() trước khi gọi pop() nếu muốn lấy giá trị đó ra.
myQueue.empty();: Tương ứng với isEmpty(). Trả về true nếu hàng đợi không có phần tử nào.
myQueue.size();: Tương ứng với size(). Trả về số lượng phần tử.

Sử dụng std::queue là cách chuẩn mực trong C++ để làm việc với hàng đợi.

Cách 2: Tự xây dựng Queue bằng Danh sách Liên kết (Linked List)

Tự xây dựng giúp chúng ta hiểu rõ cơ chế hoạt động bên trong của Queue và cách nó duy trì nguyên tắc FIFO. Danh sách liên kết là lựa chọn tự nhiên và hiệu quả cho việc triển khai Queue, vì nó cho phép thêm vào cuối và xóa ở đầu với độ phức tạp thời gian là O(1).

Chúng ta cần:

Một cấu trúc Node chứa dữ liệu và con trỏ tới node tiếp theo.
Một lớp Queue chứa con trỏ tới node đầu (front) và node cuối (rear), cùng với kích thước.

#include <iostream>

// Dinh nghia cau truc mot Node trong danh sach lien ket
struct Node {
    int data;
    Node* next;

    // Constructor
    Node(int val) : data(val), next(nullptr) {}
};

// Dinh nghia lop Queue su dung danh sach lien ket
class MyQueue {
private:
    Node* frontPtr; // Con tro toi phan tu dau tien
    Node* rearPtr;  // Con tro toi phan tu cuoi cung
    int currentSize; // Bien luu tru kich thuoc hien tai

public:
    // Constructor
    MyQueue() : frontPtr(nullptr), rearPtr(nullptr), currentSize(0) {}

    // Destructor: Giai phong bo nho khi doi tuong Queue bi huy
    ~MyQueue() {
        while (!isEmpty()) {
            dequeue(); // Goi dequeue de xoa tung node
        }
    }

    // Thao tac: Kiem tra Queue co rong khong
    bool isEmpty() const {
        return frontPtr == nullptr; // Hoac return currentSize == 0;
    }

    // Thao tac: Lay kich thuoc cua Queue
    int size() const {
        return currentSize;
    }

    // Thao tac: Them phan tu vao cuoi Queue (enqueue)
    void enqueue(int item) {
        Node* newNode = new Node(item); // Tao mot node moi

        if (isEmpty()) {
            // Neu Queue rong, node moi la ca front va rear
            frontPtr = newNode;
            rearPtr = newNode;
        } else {
            // Neu Queue khong rong, them node moi sau rear va cap nhat rear
            rearPtr->next = newNode;
            rearPtr = newNode;
        }
        currentSize++; // Tang kich thuoc
        std::cout << "Da them " << item << " vao Queue." << std::endl;
    }

    // Thao tac: Loai bo phan tu o dau Queue (dequeue)
    // Tra ve true neu thanh cong, false neu Queue rong
    bool dequeue() {
        if (isEmpty()) {
            std::cout << "Loi: Queue rong, khong the lay phan tu." << std::endl;
            return false; // Khong the dequeue khi rong
        }

        Node* temp = frontPtr; // Luu lai node dau tien de xoa sau
        int value = temp->data; // Lay gia tri truoc khi xoa

        frontPtr = frontPtr->next; // Cap nhat front tro toi node tiep theo
        if (frontPtr == nullptr) {
            // Neu sau khi xoa, Queue tro nen rong
            rearPtr = nullptr; // rear cung tro thanh nullptr
        }

        delete temp; // Giai phong bo nho cua node vua xoa
        currentSize--; // Giam kich thuoc
        std::cout << "Da lay ra phan tu " << value << " khoi Queue." << std::endl;
        return true; // Dequeue thanh cong
    }

    // Thao tac: Xem phan tu o dau Queue (front/peek)
    // Tra ve gia tri phan tu, hoac nem exception/tra ve gia tri mac dinh neu rong
    int front() const {
        if (isEmpty()) {
            std::cerr << "Loi: Queue rong, khong co phan tu o dau." << std::endl;
            // Trong ung dung thuc te nen nem exception
            // return mot gia tri mac dinh hoac ket thuc chuong trinh de don gian trong vi du
            exit(EXIT_FAILURE); // Thoat chuong trinh
        }
        return frontPtr->data; // Tra ve gia tri cua node dau tien
    }

    // Hien thi noi dung Queue (chi de minh hoa, khong phai thao tac co ban)
    void display() const {
        if (isEmpty()) {
            std::cout << "Queue hien tai: []" << std::endl;
            return;
        }
        std::cout << "Queue hien tai (Front -> Rear): [";
        Node* current = frontPtr;
        while (current != nullptr) {
            std::cout << current->data << (current->next != nullptr ? ", " : "");
            current = current->next;
        }
        std::cout << "]" << std::endl;
    }
};

int main() {
    MyQueue myCustomQueue;

    std::cout << "--- Su dung Queue tu xay dung ---" << std::endl;

    myCustomQueue.enqueue(100);
    myCustomQueue.enqueue(200);
    myCustomQueue.enqueue(300);

    myCustomQueue.display(); // Hien thi: [100, 200, 300]
    std::cout << "Kich thuoc Queue: " << myCustomQueue.size() << std::endl;
    std::cout << "Phan tu o dau Queue: " << myCustomQueue.front() << std::endl;

    myCustomQueue.dequeue(); // Lay ra 100
    myCustomQueue.display(); // Hien thi: [200, 300]

    myCustomQueue.enqueue(400); // Them 400
    myCustomQueue.display(); // Hien thi: [200, 300, 400]

    myCustomQueue.dequeue(); // Lay ra 200
    myCustomQueue.dequeue(); // Lay ra 300

    myCustomQueue.display(); // Hien thi: [400]
    std::cout << "Kich thuoc Queue: " << myCustomQueue.size() << std::endl;

    myCustomQueue.dequeue(); // Lay ra 400
    myCustomQueue.display(); // Hien thi: []

    myCustomQueue.dequeue(); // Thu lay ra khi Queue rong

    std::cout << "Queue co rong khong? " << (myCustomQueue.isEmpty() ? "Co" : "Khong") << std::endl;

    return 0;
}

Giải thích code tự xây dựng Queue bằng Linked List:

struct Node: Định nghĩa cấu trúc cơ bản cho một phần tử trong danh sách liên kết, chứa data và con trỏ next trỏ tới node kế tiếp.
class MyQueue: Lớp đại diện cho hàng đợi.
- frontPtr, rearPtr: Hai con trỏ quan trọng nhất, luôn trỏ đến node đầu và node cuối của danh sách liên kết tương ứng.
- currentSize: Theo dõi số lượng phần tử để trả lời nhanh cho thao tác size().
- Constructor: Khởi tạo hàng đợi rỗng bằng cách đặt frontPtr và rearPtr về nullptr và currentSize về 0.
- Destructor (~MyQueue()): Quan trọng để giải phóng toàn bộ bộ nhớ đã cấp phát cho các node khi đối tượng MyQueue bị hủy. Vòng lặp while (!isEmpty()) { dequeue(); } thực hiện việc này một cách an toàn.
- isEmpty(): Đơn giản kiểm tra xem frontPtr có phải là nullptr không.
- size(): Trả về giá trị của currentSize.
- enqueue(int item):
  - Tạo một newNode mới với dữ liệu item.
  - Nếu hàng đợi đang rỗng, node mới này vừa là frontPtr vừa là rearPtr.
  - Nếu không rỗng, node mới được thêm vào sau node mà rearPtr đang trỏ tới (rearPtr->next = newNode;). Sau đó, rearPtr được cập nhật để trỏ tới node mới này (rearPtr = newNode;).
  - Tăng currentSize.
- dequeue():
  - Kiểm tra xem hàng đợi có rỗng không. Nếu có thì báo lỗi và thoát hoặc trả về false.
  - Lưu lại con trỏ frontPtr hiện tại vào biến temp.
  - Lấy giá trị dữ liệu từ temp->data.
  - Cập nhật frontPtr lên node tiếp theo (frontPtr = frontPtr->next;).
  - Kiểm tra xem sau khi cập nhật, frontPtr có trở thành nullptr không (nghĩa là hàng đợi đã hết phần tử). Nếu có, đặt rearPtr về nullptr để Queue hoàn toàn rỗng.
  - Giải phóng bộ nhớ của node cũ (mà temp đang trỏ tới) bằng delete temp;.
  - Giảm currentSize.
  - Trả về true (hoặc giá trị dữ liệu đã lấy ra nếu thiết kế hàm khác đi).
- front():
  - Kiểm tra hàng đợi rỗng.
  - Trả về giá trị của node mà frontPtr đang trỏ tới (frontPtr->data). Không thay đổi con trỏ hay xóa node.
- display(): Hàm hỗ trợ để in ra nội dung Queue, giúp dễ dàng kiểm tra.

Cách tự xây dựng này giúp bạn nắm vững cách con trỏ hoạt động để quản lý cấu trúc dữ liệu Queue. Tuy nhiên, trong thực tế, std::queue là lựa chọn tối ưu hơn về mặt kỹ thuật và độ tin cậy.

Các Bài Toán Xử lý Hàng đợi và Ứng dụng của Queue

Queue không chỉ là một khái niệm trừu tượng, nó là trái tim của rất nhiều hệ thống và giải thuật trong khoa học máy tính. Nguyên tắc FIFO của nó rất phù hợp để xử lý các tác vụ theo thứ tự đến trước xử lý trước.

Dưới đây là một số ứng dụng và bài toán tiêu biểu sử dụng Queue:

Hệ điều hành:
- Hàng đợi tiến trình (Process Scheduling): Các tiến trình chờ được CPU xử lý thường được xếp vào hàng đợi.
- Hàng đợi I/O: Các yêu cầu đọc/ghi dữ liệu từ thiết bị ngoại vi (ổ đĩa, máy in) được đưa vào hàng đợi để xử lý theo thứ tự.
- Hàng đợi tin nhắn (Message Queues): Dùng trong giao tiếp giữa các tiến trình hoặc giữa các hệ thống phân tán.
Mạng máy tính:
- Bộ đệm (Buffer): Dữ liệu được gửi qua mạng thường được lưu tạm trong các bộ đệm là Queue để xử lý theo thứ tự nhận được.
Mô phỏng:
- Mô phỏng các hệ thống xếp hàng trong thế giới thực như ngân hàng, trạm thu phí, hệ thống gọi điện thoại...
In ấn:
- Hàng đợi in (Print Queue): Các tài liệu gửi đến máy in được đưa vào hàng đợi và in ra lần lượt.
Các thuật toán:
- Thuật toán Tìm kiếm theo Chiều rộng (BFS - Breadth-First Search): Đây là một trong những ứng dụng kinh điển nhất của Queue trong giải thuật. BFS dùng Queue để duyệt qua các đỉnh của đồ thị (hoặc trạng thái trong bài toán) theo từng "lớp" hoặc "mức", đảm bảo rằng tất cả các đỉnh ở mức k được thăm trước khi chuyển sang mức k+1.

Hãy đi sâu hơn vào BFS để thấy rõ sức mạnh của Queue!

Bài toán kinh điển: Tìm kiếm theo Chiều rộng (BFS)

BFS là một thuật toán để duyệt hoặc tìm kiếm trên cây hoặc đồ thị. Nó bắt đầu từ một đỉnh nguồn và khám phá tất cả các đỉnh hàng xóm ở mức hiện tại trước khi chuyển sang mức tiếp theo. Điều này hoàn toàn phù hợp với nguyên tắc FIFO của Queue!

Ý tưởng của BFS sử dụng Queue:

Bắt đầu từ đỉnh nguồn S.
Đưa đỉnh nguồn S vào Queue và đánh dấu nó đã được thăm.
Trong khi Queue không rỗng: a. Lấy một đỉnh u ra khỏi Queue (dequeue). b. "Xử lý" đỉnh u (ví dụ: in tên đỉnh, kiểm tra điều kiện tìm kiếm...). c. Tìm tất cả các đỉnh v là hàng xóm của u. d. Nếu đỉnh v chưa được thăm:
```
*   Đánh dấu `v` đã được thăm.
*   Thêm `v` vào cuối Queue (enqueue).
```

Bằng cách này, Queue luôn chứa các đỉnh ở "biên giới" của quá trình duyệt: những đỉnh đã được thăm nhưng hàng xóm của chúng chưa được khám phá. Khi dequeue một đỉnh, ta khám phá hàng xóm của nó và thêm chúng vào cuối hàng đợi, đảm bảo chúng sẽ được thăm sau tất cả các đỉnh cùng mức hoặc mức thấp hơn đã có trong hàng đợi.

Hãy xem ví dụ code C++ cho thuật toán BFS trên một đồ thị đơn giản sử dụng std::queue:

#include <iostream>
#include <vector>
#include <queue>
#include <vector> // Can cho std::vector
#include <map>    // Can cho std::map (hoac unordered_map)

// Minh hoa do thi bang Danh sach ke (Adjacency List)
// vector<vector<int>> adj: adj[i] la danh sach cac dinh ke voi dinh i
// map<int, vector<int>> adj: Anh xa so dinh toi danh sach cac dinh ke (linh hoat hon voi ten dinh bat ky)

void bfs(const std::map<int, std::vector<int>>& adj, int startNode) {
    // Kiem tra do thi co rong khong hoac startNode co hop le khong
    if (adj.empty() || adj.find(startNode) == adj.end()) {
        std::cout << "Do thi rong hoac dinh bat dau khong ton tai." << std::endl;
        return;
    }

    // 1. Khai bao Queue chua cac dinh can tham
    std::queue<int> q;

    // 2. Khai bao tap hop (hoac mang boolean) de luu cac dinh da tham
    // map<int, bool> visited; // Su dung map neu ten dinh khong tuan tu tu 0
    std::map<int, bool> visited; // Su dung map de linh hoat hon

    // Khoi tao tat ca cac dinh la chua tham
    for (auto const& [node, neighbors] : adj) {
        visited[node] = false;
        for (int neighbor : neighbors) {
             visited[neighbor] = false; // Dam bao ca cac dinh chi duoc ket noi den cung co trong visited
        }
    }
    // Dam bao dinh bat dau co trong visited
    if (visited.find(startNode) == visited.end()){
        visited[startNode] = false;
    }


    // 3. Dua dinh bat dau vao Queue va danh dau da tham
    q.push(startNode);
    visited[startNode] = true;

    std::cout << "Thu tu duyet BFS (tu dinh " << startNode << "): ";

    // 4. Vong lap chinh cua BFS
    while (!q.empty()) {
        // a. Lay dinh o dau Queue ra
        int currentNode = q.front();
        q.pop();

        // b. Xu ly dinh hien tai (vi du: in ra)
        std::cout << currentNode << " ";

        // c. Duyet qua tat ca cac dinh ke cua dinh hien tai
        // Dung adj.at(currentNode) de truy cap an toan hon
        const std::vector<int>& neighbors = adj.at(currentNode); // Lay danh sach ke

        for (int neighbor : neighbors) {
            // d. Neu dinh ke chua duoc tham
            if (!visited[neighbor]) {
                // Danh dau da tham
                visited[neighbor] = true;
                // Them vao cuoi Queue
                q.push(neighbor);
            }
        }
    }
    std::cout << std::endl;
}

int main() {
    // Minh hoa mot do thi don gian
    // Dinh tu 0 den 6
    std::map<int, std::vector<int>> graph;
    graph[0] = {1, 2};
    graph[1] = {0, 3, 4};
    graph[2] = {0, 5};
    graph[3] = {1, 6};
    graph[4] = {1};
    graph[5] = {2};
    graph[6] = {3};

    // Goi ham BFS tu dinh 0
    bfs(graph, 0); // Output mong doi: 0 1 2 3 4 5 6 (hoac thu tu ke khac tuy code)

    std::cout << std::endl;

    // Minh hoa mot do thi khac
     std::map<int, std::vector<int>> graph2;
    graph2[1] = {2, 3};
    graph2[2] = {1, 4, 5};
    graph2[3] = {1, 6};
    graph2[4] = {2};
    graph2[5] = {2};
    graph2[6] = {3};

    // Goi ham BFS tu dinh 1
    bfs(graph2, 1); // Output mong doi: 1 2 3 4 5 6 (hoac thu tu ke khac tuy code)

     std::cout << std::endl;

    // Minh hoa do thi co 2 thanh phan lien thong (BFS chi tham 1 thanh phan)
    std::map<int, std::vector<int>> graph3;
    graph3[1] = {2};
    graph3[2] = {1};
    graph3[3] = {4};
    graph3[4] = {3};

    bfs(graph3, 1); // Output: 1 2
    bfs(graph3, 3); // Output: 3 4 (Neu goi rieng)

    return 0;
}

Giải thích code BFS:

std::map<int, std::vector<int>> adj;: Chúng ta sử dụng std::map để biểu diễn đồ thị dưới dạng danh sách kề (adjacency list). Key là tên đỉnh, value là std::vector chứa danh sách các đỉnh kề với nó. map được dùng thay vì vector<vector<int>> để linh hoạt hơn với tên đỉnh không bắt đầu từ 0.
void bfs(const std::map<int, std::vector<int>>& adj, int startNode): Hàm bfs nhận đồ thị và đỉnh bắt đầu làm đầu vào.
std::queue<int> q;: Khai báo một hàng đợi std::queue để lưu trữ các đỉnh cần thăm theo thứ tự FIFO.
std::map<int, bool> visited;: Sử dụng một std::map (hoặc std::unordered_map để hiệu quả hơn với key số nguyên ngẫu nhiên) để theo dõi các đỉnh đã được thăm hay chưa. Điều này giúp tránh việc thăm lại một đỉnh nhiều lần và tránh vòng lặp vô hạn. Chúng ta khởi tạo tất cả là false.
Bước 1: Khởi tạo:
- q.push(startNode);: Đưa đỉnh bắt đầu vào hàng đợi.
- visited[startNode] = true;: Đánh dấu đỉnh bắt đầu là đã thăm.
Bước 2: Vòng lặp duyệt:
- while (!q.empty()): Vòng lặp tiếp tục cho đến khi hàng đợi rỗng (tức là không còn đỉnh nào để khám phá).
- int currentNode = q.front(); q.pop();: Lấy đỉnh đầu tiên ra khỏi hàng đợi. Đây chính là bước sử dụng nguyên tắc FIFO của Queue. Đỉnh được lấy ra là đỉnh đã ở trong hàng đợi lâu nhất.
- std::cout << currentNode << " ";: "Xử lý" đỉnh hiện tại (ở đây chỉ đơn giản là in ra).
- const std::vector<int>& neighbors = adj.at(currentNode);: Lấy danh sách các đỉnh kề với currentNode. adj.at() được dùng để an toàn, nó sẽ ném exception nếu currentNode không có trong map (mặc dù kiểm tra ban đầu đã xử lý trường hợp đồ thị rỗng hoặc đỉnh bắt đầu không hợp lệ).
- Duyệt hàng xóm: Vòng lặp for (int neighbor : neighbors) đi qua từng đỉnh kề neighbor của currentNode.
- if (!visited[neighbor]): Kiểm tra xem đỉnh kề này đã được thăm chưa. Nếu chưa:
  - visited[neighbor] = true;: Đánh dấu nó là đã thăm.
  - q.push(neighbor);: Quan trọng: Thêm đỉnh kề này vào cuối hàng đợi. Điều này đảm bảo rằng neighbor sẽ được xử lý sau tất cả các đỉnh hiện có trong hàng đợi (những đỉnh cùng mức hoặc mức gần hơn so với neighbor).
Quá trình này lặp lại cho đến khi Queue rỗng, đảm bảo rằng tất cả các đỉnh reachable (có thể đến được) từ startNode sẽ được thăm theo thứ tự "từng lớp" một.

Bài tập ví dụ:

Quái Vật Sát Thủ

Trong một buổi thực hành, FullHouse Dev đang phát triển một tựa game chiến thuật. Họ cần xây dựng một hệ thống mô phỏng trận chiến, nơi các quái vật với sức mạnh khác nhau sẽ xuất hiện và tương tác với nhau. Đây là một thử thách thú vị để kiểm tra khả năng xử lý logic game của nhóm.

Bài toán

Cho một mảng biểu thị sức mạnh của \(n\) quái vật. Ban đầu chiến trường trống rỗng, mỗi phút thứ \(i\), con quái vật thứ \(i\) sẽ tham gia chiến trường và tiêu diệt tất cả quái vật có sức mạnh nhỏ hơn hoặc bằng sức mạnh của nó. Nhiệm vụ của FullHouse Dev là tìm ra số lượng quái vật còn sống trên chiến trường sau mỗi phút thứ \(i\).

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
Dòng đầu tiên của mỗi test case chứa số nguyên \(n\) - số lượng quái vật
Dòng thứ hai của mỗi test case chứa \(n\) số nguyên - sức mạnh của \(n\) quái vật

OUTPUT FORMAT:

Với mỗi test case, in ra \(n\) số nguyên biểu thị số lượng quái vật còn sống sau phút thứ \(i\)

Ràng buộc:

Khuyến nghị sử dụng Fast I/O cho bài toán này
Quái vật sẽ trở thành một phần của chiến trường sau khi kết thúc đợt tấn công

Ví dụ

INPUT

3
5
3 0 3 4 1
5
5 4 3 2 1
7
1 2 3 3 4 4 0

OUTPUT

1 2 1 1 2
1 2 3 4 5
1 1 1 1 1 1 2

Giải thích

Ở test case đầu tiên, sức mạnh của các quái vật là \([3,0,3,4,1]\):

Phút 1: Quái vật đầu tiên (sức mạnh 3) xuất hiện. Không có quái vật nào trên chiến trường. Sau phút 1, quái vật còn sống là \([3]\).
Phút 2: Quái vật thứ hai (sức mạnh 0) xuất hiện. Không có quái vật nào bị tiêu diệt vì sức mạnh 0 không thể tiêu diệt ai. Quái vật còn sống là \([3,0]\).
Phút 3: Quái vật thứ ba (sức mạnh 3) xuất hiện. Nó tiêu diệt quái vật có sức mạnh 0 và quái vật có sức mạnh 3 đầu tiên. Quái vật còn sống là \([3]\).
Phút 4: Quái vật thứ tư (sức mạnh 4) xuất hiện. Nó tiêu diệt quái vật có sức mạnh 3. Quái vật còn sống là \([4]\).
Phút 5: Quái vật thứ năm (sức mạnh 1) xuất hiện. Không có quái vật nào bị tiêu diệt. Quái vật còn sống là \([4,1]\). Chào bạn, đây là hướng dẫn giải bài "Quái Vật Sát Thủ" tập trung vào cấu trúc dữ liệu và thuật toán phù hợp, không cung cấp code hoàn chỉnh.

1. Phân tích bài toán:

Bài toán mô phỏng một quá trình diễn ra theo thời gian (từng phút).
Mỗi phút, một quái vật mới tham gia chiến trường.
Quái vật mới này tấn công và loại bỏ các quái vật đang tồn tại trên chiến trường có sức mạnh nhỏ hơn hoặc bằng nó.
Sau khi tấn công xong, quái vật mới gia nhập nhóm quái vật còn sống.
Ta cần biết số lượng quái vật còn sống sau mỗi phút.
Điểm mấu chốt là quái vật mới giết tất cả quái vật hiện có mà yếu hơn hoặc bằng nó. Thứ tự xuất hiện của các quái vật hiện có có thể quan trọng, đặc biệt với quái vật cùng sức mạnh.

2. Lựa chọn cấu trúc dữ liệu:

Chúng ta cần lưu trữ tập hợp các quái vật đang sống trên chiến trường.
Khi quái vật mới đến, ta cần dễ dàng kiểm tra các quái vật đang sống và loại bỏ những con thỏa mãn điều kiện.
Lưu ý: Khi một quái vật mới P_new đến, nó sẽ giết tất cả P_old đang sống nếu P_old <= P_new. Điều này có nghĩa là các quái vật yếu hơn hoặc bằng P_new sẽ bị loại bỏ.
Hãy suy nghĩ về thứ tự các quái vật sống. Nếu quái vật sống được lưu trữ theo một thứ tự nhất định (ví dụ, thứ tự xuất hiện), việc kiểm tra và loại bỏ sẽ hiệu quả hơn.
Xét quái vật mới đến P_new. Nó sẽ tiêu diệt những quái vật P_old có P_old <= P_new. Nếu ta lưu các quái vật sống trong một cấu trúc mà quái vật mới sống nhất (đến gần đây nhất) nằm ở một đầu, ta có thể dễ dàng kiểm tra xem P_new có thể tiêu diệt nó không. Nếu có, ta loại bỏ nó và kiểm tra con tiếp theo (cũ hơn một chút), cứ thế cho đến khi gặp một con P_old > P_new hoặc cấu trúc rỗng.
Cấu trúc dữ liệu phù hợp cho thao tác thêm vào một đầu và bóc/kiểm tra ở cùng đầu đó là Stack (Ngăn xếp) hoặc Deque (Hàng đợi hai đầu). Sử dụng Stack (hoặc vector mô phỏng stack) là một lựa chọn tốt ở đây. Ta sẽ lưu sức mạnh của các quái vật đang sống trong Stack, với quái vật mới nhất nằm ở đỉnh Stack.

3. Thuật toán:

Khởi tạo một Stack rỗng để chứa sức mạnh của các quái vật đang sống.
Duyệt qua từng quái vật theo thứ tự chúng xuất hiện (từ i=1 đến n).
Tại phút thứ i, quái vật có sức mạnh P_i xuất hiện:
- Trong khi Stack chưa rỗng VÀ sức mạnh của quái vật ở đỉnh Stack nhỏ hơn hoặc bằng P_i:
  - Loại bỏ (pop) quái vật ở đỉnh Stack (vì nó bị P_i tiêu diệt).
- Sau khi vòng lặp trên kết thúc (hoặc Stack rỗng hoặc quái vật ở đỉnh mạnh hơn P_i), đẩy (push) sức mạnh P_i vào Stack (quái vật P_i gia nhập chiến trường).
- Số lượng quái vật còn sống sau phút thứ i chính là kích thước hiện tại của Stack. In ra kích thước này.

4. Độ phức tạp:

Mỗi quái vật được đẩy vào Stack đúng 1 lần.
Mỗi quái vật, một khi đã nằm trong Stack, chỉ có thể bị pop ra tối đa 1 lần.
Tổng số lần pop trong suốt quá trình là tối đa n.
Thao tác push và pop trên Stack (hoặc vector dùng làm stack) là O(1).
Độ phức tạp thời gian: O(n) vì mỗi quái vật chỉ được xử lý (push, pop) một số lần hằng số.
Độ phức tạp không gian: O(n) để lưu trữ Stack trong trường hợp xấu nhất (ví dụ, quái vật ngày càng yếu đi, không con nào bị giết).

5. Gợi ý bổ sung:

Sử dụng Fast I/O như khuyến nghị để đọc dữ liệu nhanh hơn, đặc biệt hữu ích với n lớn.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.