C++: Queue

Tổng quan

Queue (hàng đợi) là một cấu trúc dữ liệu hoạt động theo kiểu sắp xếp vào trước ra trước (FIFO - first in first out). Các phần tử khi được thêm vào queue được chèn vào phía cuối. Phần tử nào được thêm vào trước sẽ được lấy ra trước. Thư viện mẫu chuẩn (STL) cung cấp sẵn một class template cho việc sử dụng queue

Sử dụng queue

Khai báo thư viện

#include <queue>

Khởi tạo queue với một kiểu dữ liệu

std::queue<int> myQueue;

Các hàm cơ bản

push(): Để chèn một phần tử vào cuối hàng đợi.
pop(): Để loại bỏ phần tử ở đầu hàng đợi.
front(): Trả về phần tử đầu tiên trong hàng đợi.
back(): Trả về phần tử cuối cùng trong hàng đợi.
empty(): Kiểm tra xem hàng đợi có rỗng hay không.
size(): Trả về số lượng phần tử trong hàng đợi.

Ví dụ

#include <iostream>
#include <queue>

int main() {
    std::queue<int> myQueue;

    // Chèn phần tử vào cuối hàng đợi
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);

    // Trả về tham chiếu đến phần tử đầu tiên trong hàng đợi
    std::cout << "Front of queue: " << myQueue.front() << std::endl; // output: Front of queue: 10

    // Trả về tham chiếu đến phần tử cuối cùng trong hàng đợi
    std::cout << "Back of queue: " << myQueue.back() << std::endl;// output: Back of queue: 30

    // Loại bỏ phần tử đầu tiên trong hàng đợi 10
    myQueue.pop();

    std::cout << "Front of queue: " << myQueue.front() << std::endl; // output: Front of queue: 20

    // Kiểm tra xem hàng đợi có rỗng không
    if (myQueue.empty()) {
        std::cout << "Queue is empty" << std::endl;
    } else {
        std::cout << "Queue is not empty" << std::endl; // output: Queue is not empty
    }

    // Trả về số lượng phần tử trong hàng đợi
    std::cout << "Size of queue: " << myQueue.size() << std::endl; // output: Size of queue: 2

    return 0;
}

Cài đặt queue bằng mảng

Có thể sử dụng mảng để cài đặt queue một cách đơn giản nếu như không muốn sử dụng thư viện chuẩn STL. Tư tưởng chính là duy trì 2 biến front và rear để lưu trữ vị trí đầu và vị trí cuối của queue. Trong cài đặt dưới đây, chúng ta sử dụng một template Queue với một tham số kiểu T cho phép queue chứa bất kỳ kiểu dữ liệu nào và một tham số nguyên MAX_SIZE để xác định kích thước tối đa của queue. Sau đó, chúng ta tạo các queue riêng biệt, một cho kiểu int và một cho kiểu char, và thực hiện các thao tác cơ bản của queue như enqueue, dequeue, getFront, getRear.

#include <iostream>

template <typename T, int MAX_SIZE>
class Queue {
private:
    T arr[MAX_SIZE];
    int front, rear;

public:
    Queue() {
        front = -1;
        rear = -1;
    }

    bool isEmpty() {
        return (front == -1 && rear == -1);
    }

    bool isFull() {
        return (rear + 1) % MAX_SIZE == front ? true : false;
    }

    void enqueue(T x) {
        if (isFull()) {
            std::cout << "Queue is full. Cannot enqueue " << x << std::endl;
            return;
        } else if (isEmpty()) {
            front = rear = 0;
        } else {
            rear = (rear + 1) % MAX_SIZE;
        }
        arr[rear] = x;
    }

    void dequeue() {
        if (isEmpty()) {
            std::cout << "Queue is empty. Cannot dequeue" << std::endl;
            return;
        } else if (front == rear) {
            front = rear = -1;
        } else {
            front = (front + 1) % MAX_SIZE;
        }
    }

    T getFront() {
        if (isEmpty()) {
            std::cout << "Queue is empty. No front element" << std::endl;
            return T();
        }
        return arr[front];
    }

    T getRear() {
        if (isEmpty() || rear < 0) {
            std::cout << "Queue is empty. No rear element" << std::endl;
            return T();
        }
        return arr[rear];
    }
};

int main() {
    Queue<int, 5> intQueue;
    Queue<char, 10> charQueue;

    intQueue.enqueue(10);
    intQueue.enqueue(20);
    intQueue.enqueue(30);

    std::cout << "Front of intQueue: " << intQueue.getFront() << std::endl;
    std::cout << "Rear of intQueue: " << intQueue.getRear() << std::endl;

    charQueue.enqueue('A');
    charQueue.enqueue('B');

    std::cout << "Front of charQueue: " << charQueue.getFront() << std::endl;
    std::cout << "Rear of charQueue: " << charQueue.getRear() << std::endl;

    return 0;
}

Ouput: 

Front of intQueue: 10
Rear of intQueue: 30
Front of charQueue: A
Rear of charQueue: B