Hàng đợi – Queue trong C++

Trong những bài trước, ta đã tìm hiểu về Stack, trong lập trình C++, còn có một loại cấu trúc dữ liệu trái ngược với Stack đó là Queue – Hàng đợi. Trong bài viết này, chúng ta sẽ cùng tìm hiểu sâu hơn về Queue trong C++, từ cách khởi tạo, sử dụng đến những ứng dụng thực tế của nó trong lập trình C++.

Queue C++ là gì?

Hàng đợi – Queue là một cấu trúc dữ liệu đặc biệt trong C++ được quản lý theo nguyên tắc First In First Out (FIFO), tức là phần tử được thêm vào trước sẽ được lấy ra trước. Cấu trúc này rất hữu ích trong nhiều bài toán liên quan đến quản lý luồng dữ liệu, xử lý các yêu cầu theo thứ tự hoặc trong các hệ thống hàng đợi.

Với sự hỗ trợ mạnh mẽ từ một thư viện chứa những template C++ (STL – Standard Template Library), Queue trở thành một công cụ hữu ích và linh hoạt, giúp lập trình viên dễ dàng xây dựng các giải pháp hiệu quả và tối ưu.

>> Đọc thêm: Ngăn xếp stack trong C++

Các phương thức của Queue trong C++

Trong C++, queue là một lớp cung cấp nhiều phương thức khác nhau để thực hiện các thao tác với hàng đợi. Dưới đây là các phương thức chính:

Cách hàng đợi Queue hoạt động

Trong C++, queue là một container adapter được xây dựng dựa trên các container khác như deque hoặc list. Điều này có nghĩa là queue sử dụng một đối tượng của các container này làm nền tảng, và cung cấp một tập hợp các hàm thành viên (member functions) để truy cập và quản lý các phần tử.

Queue trong C++ cho phép cấu hình thông qua các tham số mẫu sau:

• Container: Tham số này xác định đối tượng bên trong (internal object) của container nơi tất cả các phần tử của hàng đợi được lưu trữ. Ví dụ, queue thường được cài đặt dựa trên std::deque hoặc std::list, vì các container này hỗ trợ truy cập đầu và cuối một cách hiệu quả.
• T: Tham số này xác định kiểu dữ liệu của các phần tử sẽ được giữ bởi container adapter. Ví dụ, nếu bạn muốn tạo một queue của số nguyên, T sẽ là int.

>> Xem thêm: Phân biệt ngăn xếp và hàng đợi (Stack vs Queue) trong C++

Cài đặt hàng đợi

Bây giờ chúng ta hãy cùng xem cách cài đặt hàng đợi trong C++.

Cấu trúc một phần tử

Hàng đợi cũng dựa trên danh sách liên kết đơn, do đó một phần tử trong hàng đợi có cấu trúc không khác gì một phần tử trong danh sách liên kết đơn.

struct Node
{
    int data;
    Node *next;
};

Cấp phát động, khởi gán giá trị một node và trả về địa chỉ của node đó tương tự như stack hay linked list:

Node* CreateNode(int init)
{
    Node *node = new Node;
    node->data = init;
    node->next = NULL;
    return node;
}

Cấu trúc một hàng đợi

Không giống như ngăn xếp, hàng đợi yêu cầu ta phải quản lý được cả phần tử đầu và cuối, do chúng ta thêm vào hàng đợi là thêm vào cuối và lấy một phần tử là lấy từ đầu hàng đợi. Vậy chúng ta sẽ có cấu trúc Queue như sau:

struct Queue
{
    Node *head;
    Node *tail;
};

Tương tự, hàng đợi rỗng khi được khởi tạo, ta sẽ gán head và tail bằng NULL:

void CreateQueue(Queue &q)
{
    q.head = NULL;
    q.tail = NULL;
}

Kiểm tra hàng đợi rỗng

Tương tự như stack, hàng đợi rỗng khi phần tử đầu hàng đợi bằng NULL, chúng ta sẽ kiểm tra như sau

int IsEmpty(Queue q)
{
    if (q.head == NULL)
        return 1;
    return 0;
}

Thêm phần tử vào cuối hàng đợi – Enqueue trong C++

Thêm phần tử vào cuối hàng đợi (EnQueue) thực hiện cũng tương tự như khi ta thêm phần tử vào cuối danh sách liên kết đơn, tức là thêm vào tail. Chúng ta thực hiện như sau:

void EnQueue(Queue &q, Node *node)
{
    if (IsEmpty(q))
    {
        q.head = node;
        q.tail = node;
    }
    else
    {
        q.tail->next = node;
        q.tail = node;
    }
}

Lấy phần tử đầu ra khỏi hàng đợi – Dequeue trong C++

Để lấy phần tử đầu ra khỏi hàng đợi (DeQueue), chúng ta sẽ lưu trữ giá trị phần tử đầu hàng đợi, sau đó xóa nó đi như xóa phần tử đầu của danh sách liên kết đơn, tất nhiên là với điều kiện hàng đợi không rỗng. Sau khi lấy phần tử đầu tiên ra, nếu như đó là phần tử duy nhất của hàng đợi thì chúng ta sẽ gán lại tail bằng NULL luôn. Chúng ta sẽ có đoạn code như sau:

int DeQueue(Queue &q)
{
    if (IsEmpty(q))
        return 0;
    Node *node = q.head;
    int data = node->data;
    q.head = node->next;
    delete node;
    if (q.head == NULL)
        q.tail = NULL;
    return data;
}

Lấy giá trị phần tử đầu hàng đợi

Lấy giá trị phần tử đầu hàng đợi cũng tương tự như lấy phần tử đầu ra khỏi hàng đợi, nhưng không xóa phần tử đầu đi. Chúng ta thực hiện như sau:

int Front(Queue q)
{
    if (IsEmpty(q))
        return 0;
    return q.head->data;
}

Tham khảo việc làm C++ Developer hấp dẫn tại TopDev

Độ phức tạp thời gian

Các thao tác trên queue đều có độ phức tạp thời gian O(1), tức là chúng hoạt động với thời gian hằng số bất kể kích thước của hàng đợi. Điều này làm cho queue trở thành một cấu trúc dữ liệu rất hiệu quả trong nhiều tình huống xử lý dữ liệu.