Hàng đợi (Queue) trong C++

Queue là một cấu trúc dữ liệu trong C++ tuân theo nguyên tắc FIFO (First In, First Out), nghĩa là phần tử được thêm vào đầu tiên sẽ được lấy ra đầu tiên. C++ cung cấp thư viện chuẩn STL (Standard Template Library) hỗ trợ việc sử dụng queue thông qua lớp queue.

Các lệnh cơ bản trong Queue:

• push(element): Thêm một phần tử vào cuối của queue.
  • Độ phức tạp: O(1)
• pop(): Loại bỏ phần tử ở đầu của queue.
  • Độ phức tạp: O(1)
• front(): Truy cập phần tử ở đầu của queue mà không loại bỏ nó.
  • Độ phức tạp: O(1)
• back(): Truy cập phần tử ở cuối của queue mà không loại bỏ nó.
  • Độ phức tạp: O(1)
• empty(): Kiểm tra xem queue có rỗng không.
  • Độ phức tạp: O(1)
• size(): Trả về số lượng phần tử trong queue.
  • Độ phức tạp: O(1)
• swap(queue& other): Hoán đổi nội dung của queue hiện tại với một queue khác.
  • Độ phức tạp: O(1)

Ví dụ minh họa code Queue trong C++:

#include <iostream>
#include <queue>

using namespace std;

int main() {
    // Khai báo queue chứa các số nguyên
    queue<int> myQueue;

    // Thêm các phần tử vào queue
    myQueue.push(10);  // [10]
    myQueue.push(20);  // [10, 20]
    myQueue.push(30);  // [10, 20, 30]

    // In ra kích thước của queue: 3
    cout << "Size of queue: " << myQueue.size() << endl;

    // Truy cập phần tử ở đầu của queue: 10
    cout << "Front element: " << myQueue.front() << endl;

    // Truy cập phần tử ở cuối của queue: 30
    cout << "Back element: " << myQueue.back() << endl;

    // Loại bỏ phần tử ở đầu của queue
    myQueue.pop();     // [20, 30]

    // Truy cập phần tử ở đầu của queue sau khi pop: 20
    cout << "Front element after pop: " << myQueue.front() << endl;

    // Kiểm tra queue có rỗng không
    if (myQueue.empty()) {
        cout << "Queue is empty." << endl;
    } else {
        cout << "Queue is not empty." << endl;
    }

    // Khai báo hai queue chứa các số nguyên
    queue<int> queue1;
    queue<int> queue2;

    // Thêm các phần tử vào queue1
    queue1.push(10);
    queue1.push(20);
    queue1.push(30);

    // Thêm các phần tử vào queue2
    queue2.push(100);
    queue2.push(200);

    // Trước khi hoán đổi
    cout << "Queue1 front before swap: " << queue1.front() << endl; // Output: 10
    cout << "Queue2 front before swap: " << queue2.front() << endl; // Output: 100

    // Hoán đổi nội dung của queue1 và queue2
    queue1.swap(queue2);

    // Sau khi hoán đổi
    cout << "Queue1 front after swap: " << queue1.front() << endl; // Output: 100
    cout << "Queue2 front after swap: " << queue2.front() << endl; // Output: 10

    return 0;
}