Khóa học C++

Appearance

Queue - Cấu trúc dữ liệu FIFO ​

📖 Giới thiệu ​

Queue (hàng đợi) là cấu trúc dữ liệu hoạt động theo nguyên tắc FIFO (First In, First Out) - phần tử đầu tiên vào sẽ được lấy ra đầu tiên. Như hàng đợi mua vé, người đến trước sẽ được phục vụ trước.

Ví dụ đơn giản đầu tiên ​

cpp
#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> my_queue;
    
    // Thêm phần tử (enqueue)
    my_queue.push(10);
    my_queue.push(20);
    my_queue.push(30);
    
    cout << "Queue có " << my_queue.size() << " phần tử" << endl;
    cout << "Phần tử đầu: " << my_queue.front() << endl;
    cout << "Phần tử cuối: " << my_queue.back() << endl;
    
    // Lấy phần tử ra (dequeue)
    while (!my_queue.empty()) {
        cout << "Lấy ra: " << my_queue.front() << endl;
        my_queue.pop();
    }
    
    return 0;
}

🔧 Cú pháp ​

Khai báo Queue ​

cpp
#include <queue>

queue<int> int_queue;                    // Queue số nguyên
queue<string> string_queue;             // Queue chuỗi
queue<int, vector<int>> vector_queue;   // Queue dựa trên vector
queue<int, deque<int>> deque_queue;     // Queue dựa trên deque (mặc định)

Các phương thức cơ bản ​

cpp
// Thêm/xóa
queue.push(value);          // Thêm phần tử vào cuối
queue.pop();                // Xóa phần tử đầu

// Truy cập
queue.front();              // Phần tử đầu
queue.back();               // Phần tử cuối

// Thông tin
queue.size();               // Số phần tử
queue.empty();              // Kiểm tra rỗng

💻 Ví dụ minh họa ​

Ví dụ 1: Hệ thống xử lý đơn hàng ​

cpp
#include <iostream>
#include <queue>
#include <string>
#include <iomanip>
using namespace std;

struct DonHang {
    int id;
    string khach_hang;
    string san_pham;
    int so_luong;
    double gia;
    string trang_thai;
    
    DonHang(int id, string kh, string sp, int sl, double g) 
        : id(id), khach_hang(kh), san_pham(sp), so_luong(sl), gia(g), trang_thai("Đang chờ") {}
    
    void hien_thi() const {
        cout << "ID: " << setw(3) << id 
             << " | KH: " << setw(15) << khach_hang
             << " | SP: " << setw(20) << san_pham
             << " | SL: " << setw(3) << so_luong
             << " | Giá: " << setw(8) << fixed << setprecision(0) << gia
             << " | TT: " << trang_thai << endl;
    }
    
    double tinh_tong() const {
        return so_luong * gia;
    }
};

class OrderProcessingSystem {
private:
    queue<DonHang> hang_doi_don_hang;
    queue<DonHang> hang_doi_dong_goi;
    queue<DonHang> hang_doi_giao_hang;
    vector<DonHang> don_hang_hoan_thanh;
    int next_order_id;
    
public:
    OrderProcessingSystem() : next_order_id(1) {
        cout << "🏪 Khởi tạo hệ thống xử lý đơn hàng" << endl;
    }
    
    void them_don_hang(const string& khach_hang, const string& san_pham, int so_luong, double gia) {
        DonHang don_moi(next_order_id++, khach_hang, san_pham, so_luong, gia);
        hang_doi_don_hang.push(don_moi);
        
        cout << "📝 Đã thêm đơn hàng #" << don_moi.id << " của " << khach_hang << endl;
        cout << "    " << san_pham << " x" << so_luong << " = " << don_moi.tinh_tong() << " VND" << endl;
    }
    
    void xu_ly_don_hang() {
        if (hang_doi_don_hang.empty()) {
            cout << "❌ Không có đơn hàng nào để xử lý!" << endl;
            return;
        }
        
        DonHang don = hang_doi_don_hang.front();
        hang_doi_don_hang.pop();
        
        don.trang_thai = "Đã xử lý";
        hang_doi_dong_goi.push(don);
        
        cout << "⚙️ Đã xử lý đơn hàng #" << don.id << " của " << don.khach_hang << endl;
    }
    
    void dong_goi_don_hang() {
        if (hang_doi_dong_goi.empty()) {
            cout << "❌ Không có đơn hàng nào để đóng gói!" << endl;
            return;
        }
        
        DonHang don = hang_doi_dong_goi.front();
        hang_doi_dong_goi.pop();
        
        don.trang_thai = "Đã đóng gói";
        hang_doi_giao_hang.push(don);
        
        cout << "📦 Đã đóng gói đơn hàng #" << don.id << " của " << don.khach_hang << endl;
    }
    
    void giao_hang() {
        if (hang_doi_giao_hang.empty()) {
            cout << "❌ Không có đơn hàng nào để giao!" << endl;
            return;
        }
        
        DonHang don = hang_doi_giao_hang.front();
        hang_doi_giao_hang.pop();
        
        don.trang_thai = "Đã giao";
        don_hang_hoan_thanh.push_back(don);
        
        cout << "🚛 Đã giao đơn hàng #" << don.id << " cho " << don.khach_hang << endl;
    }
    
    void hien_thi_trang_thai() {
        cout << "\n📊 TRẠNG THÁI HỆ THỐNG" << endl;
        cout << string(80, '=') << endl;
        
        cout << "🔄 Đơn hàng chờ xử lý (" << hang_doi_don_hang.size() << "):" << endl;
        if (hang_doi_don_hang.empty()) {
            cout << "  (Trống)" << endl;
        } else {
            queue<DonHang> temp = hang_doi_don_hang;
            while (!temp.empty()) {
                cout << "  ";
                temp.front().hien_thi();
                temp.pop();
            }
        }
        
        cout << "\n📦 Đơn hàng chờ đóng gói (" << hang_doi_dong_goi.size() << "):" << endl;
        if (hang_doi_dong_goi.empty()) {
            cout << "  (Trống)" << endl;
        } else {
            queue<DonHang> temp = hang_doi_dong_goi;
            while (!temp.empty()) {
                cout << "  ";
                temp.front().hien_thi();
                temp.pop();
            }
        }
        
        cout << "\n🚛 Đơn hàng chờ giao (" << hang_doi_giao_hang.size() << "):" << endl;
        if (hang_doi_giao_hang.empty()) {
            cout << "  (Trống)" << endl;
        } else {
            queue<DonHang> temp = hang_doi_giao_hang;
            while (!temp.empty()) {
                cout << "  ";
                temp.front().hien_thi();
                temp.pop();
            }
        }
        
        cout << "\n✅ Đơn hàng hoàn thành (" << don_hang_hoan_thanh.size() << "):" << endl;
        if (don_hang_hoan_thanh.empty()) {
            cout << "  (Trống)" << endl;
        } else {
            for (const auto& don : don_hang_hoan_thanh) {
                cout << "  ";
                don.hien_thi();
            }
        }
        cout << string(80, '=') << endl;
    }
    
    void xu_ly_tat_ca() {
        cout << "\n🔄 Xử lý tất cả đơn hàng trong hệ thống..." << endl;
        
        while (!hang_doi_don_hang.empty()) {
            xu_ly_don_hang();
        }
        
        while (!hang_doi_dong_goi.empty()) {
            dong_goi_don_hang();
        }
        
        while (!hang_doi_giao_hang.empty()) {
            giao_hang();
        }
        
        cout << "✅ Đã xử lý xong tất cả đơn hàng!" << endl;
    }
    
    void thong_ke() {
        if (don_hang_hoan_thanh.empty()) {
            cout << "\n📈 Chưa có đơn hàng hoàn thành để thống kê!" << endl;
            return;
        }
        
        double tong_doanh_thu = 0;
        int tong_san_pham = 0;
        
        for (const auto& don : don_hang_hoan_thanh) {
            tong_doanh_thu += don.tinh_tong();
            tong_san_pham += don.so_luong;
        }
        
        cout << "\n📈 THỐNG KÊ KINH DOANH" << endl;
        cout << "Số đơn hàng hoàn thành: " << don_hang_hoan_thanh.size() << endl;
        cout << "Tổng sản phẩm bán: " << tong_san_pham << endl;
        cout << "Tổng doanh thu: " << fixed << setprecision(0) << tong_doanh_thu << " VND" << endl;
        cout << "Doanh thu trung bình/đơn: " << (tong_doanh_thu / don_hang_hoan_thanh.size()) << " VND" << endl;
    }
    
    int get_tong_don_cho() const {
        return hang_doi_don_hang.size() + hang_doi_dong_goi.size() + hang_doi_giao_hang.size();
    }
};

int main() {
    cout << "=== HỆ THỐNG XỬ LÝ ĐƠN HÀNG ===" << endl;
    
    OrderProcessingSystem system;
    
    // Thêm đơn hàng
    cout << "\n--- Thêm đơn hàng ---" << endl;
    system.them_don_hang("Nguyễn Văn A", "Laptop Dell", 1, 15000000);
    system.them_don_hang("Trần Thị B", "iPhone 15", 2, 25000000);
    system.them_don_hang("Lê Văn C", "Tai nghe Sony", 1, 2000000);
    system.them_don_hang("Phạm Thị D", "Bàn phím cơ", 3, 1500000);
    system.them_don_hang("Hoàng Văn E", "Chuột gaming", 2, 800000);
    
    system.hien_thi_trang_thai();
    
    // Xử lý từng bước
    cout << "\n--- Xử lý từng bước ---" << endl;
    system.xu_ly_don_hang();
    system.xu_ly_don_hang();
    system.dong_goi_don_hang();
    system.giao_hang();
    
    system.hien_thi_trang_thai();
    
    // Xử lý tất cả còn lại
    cout << "\n--- Xử lý hết đơn hàng còn lại ---" << endl;
    system.xu_ly_tat_ca();
    
    system.hien_thi_trang_thai();
    system.thong_ke();
    
    return 0;
}

🏋️ Thực hành ​

Bài tập 1: Print Queue Simulator ​

Tạo class PrintQueue để:

  • Quản lý hàng đợi in ấn
  • Priority theo loại tài liệu
  • Estimate thời gian hoàn thành

Bài tập 2: CPU Task Scheduler ​

Tạo class TaskScheduler với:

  • Round-robin scheduling
  • Process queues theo priority
  • CPU time tracking

Bài tập 3: Customer Service System ​

Tạo hệ thống chăm sóc khách hàng:

  • Multiple service queues
  • Average waiting time calculation
  • Customer satisfaction tracking

📋 Tóm tắt ​

  1. Queue: FIFO data structure - First In, First Out

  2. Operations:

    • push(): Thêm vào cuối O(1)
    • pop(): Xóa khỏi đầu O(1)
    • front(): Xem đầu O(1)
    • back(): Xem cuối O(1)

  3. Ứng dụng:

    • Task scheduling
    • Buffer systems
    • BFS algorithms
    • Producer-consumer problems

  4. Priority Queue: Sử dụng priority_queue cho ordering đặc biệt

Bài tiếp theo: Deque - Double-ended queue với truy cập hai đầu.

Khóa học C++ miễn phí

Copyright © 2024 zukahai