Tìm hiểu về hàng đợi, ứng dụng thực tế và cài đặt thuật toán bằng lập trình c++

Bạn đang tìm hiểu về hàng đợi (queue) một cấu trúc giải thuật hay trong lập trình ? Khám ngay bài viết này để hiểu rõ hơn về hàng đợi, ứng dụng trong thực tế cũng như cài đặt bằng lập trình c++.

Hàng đợi (queue) là gì ?

Hàng đợi (queue) là một cấu trúc dữ liệu tuyến tính hoạt động theo nguyên tắc "First In, First Out" (FIFO), nghĩa là phần tử được thêm vào đầu tiên sẽ được lấy ra đầu tiên. Hàng đợi thường được sử dụng trong các tình huống cần quản lý thứ tự xử lý, như trong hệ thống hàng đợi in ấn, hàng đợi xử lý yêu cầu mạng,...


Các thao tác cơ bản trên hàng đợi:

  • Enqueue: Thêm một phần tử vào cuối hàng đợi.
  • Dequeue: Lấy phần tử ở đầu hàng đợi ra.
  • Peek/Front: Xem phần tử ở đầu hàng đợi mà không lấy ra.
  • IsEmpty: 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.

Ứng dụng của hàng đợi trong thực tế

Hàng đợi có rất nhiều ứng dụng trong thực tế, đặc biệt trong các lĩnh vực liên quan đến quản lý dữ liệu và xử lý thứ tự. Dưới đây là một số ví dụ phổ biến:

  • Hệ thống hàng đợi in ấn: Khi nhiều tài liệu được gửi đến máy in cùng lúc, chúng sẽ được xếp vào hàng đợi và in theo thứ tự.
  • Hệ thống hàng đợi trong mạng: Các gói dữ liệu được xếp vào hàng đợi để truyền qua mạng, đảm bảo rằng chúng được gửi và nhận theo thứ tự.
  • Hệ thống hàng đợi trong hệ điều hành: Các tiến trình (process) và luồng (thread) được xếp vào hàng đợi để xử lý bởi CPU, đảm bảo rằng các tiến trình được thực hiện theo thứ tự công bằng.
  • Hàng đợi trong dịch vụ khách hàng: Các cuộc gọi đến trung tâm dịch vụ khách hàng được xếp vào hàng đợi và xử lý theo thứ tự, đảm bảo rằng mỗi khách hàng được phục vụ theo thứ tự họ gọi đến.
  • Hàng đợi trong lập trình trò chơi: Trong các trò chơi, hàng đợi có thể được sử dụng để quản lý các sự kiện hoặc hành động của nhân vật, đảm bảo rằng chúng được thực hiện theo thứ tự.
  • Hàng đợi trong hệ thống điều khiển giao thông: Các phương tiện được xếp vào hàng đợi tại các ngã tư hoặc trạm thu phí, đảm bảo rằng chúng được xử lý theo thứ tự để tránh ùn tắc.

Minh họa thuật toán hàng đợi bằng C++:

Như vậy ở trên các bạn đã hiểu rõ hơn về hàng đợi là gì cũng như ứng dụng của nó trong thực tế. Sau đây Stanford sẽ hướng dẫn các bạn học lập trình thực hiện cách triển khai hàng đợi bằng mảng trong lập trình C++ như sau:

#pragma once
#include <iostream>
using namespace std;
 
class HangDoi
{
private:
    int front, rear, size;
    int* queue;
public:
    HangDoi(int c) {
        front = rear = 0;
        size = c;
        queue = new int[size];
    }
    ~HangDoi() {
        delete[] queue;
    }
 
    //Hàm thêm phần tử vào hàng đợi
    void enqueue(int data) {
        if (size == rear) {
            cout << "Queue is full\n";
            return;
        }
        else {
            queue[rear] = data;
            rear++;
        }
        return;
    }
    //Hàm xóa phần tử ở đầu danh sách
    void dequeue() {
        if (front == rear) {
            cout << "Queue is empty\n";
            return;
        }
        else {
            for (int i = 0; i < rear - 1; i++) {
                queue[i] = queue[i + 1];
            }
            rear--;
        }
        return;
    }
    //Hàm hiển thị danh sách
    void display() {
        if (front == rear) {
            cout << "Queue is empty\n";
            return;
        }
        for (int i = front; i < rear; i++) {
            cout << queue[i] << "\t";
        }
        cout << endl;
        return;
    }
    //Lấy phần tử đầu danh sách
    int frontElement() {
        if (front == rear) {
            cout << "Queue is empty\n";
            return -1;
        }
        return queue[front];
    }
};
int main()
{
    HangDoi q(5);
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.enqueue(40);
 
    cout << "Cac phan tu trong hang doi: ";
    q.display();
    q.dequeue();
    cout << "Cac phan tu trong hang doi sau khi xoa phan tu dau: ";
    q.display();
    cout << "Phan tu dau cua hang doi: " << q.frontElement() << endl;
}

Trong ví dụ trên, chúng ta đã tạo một lớp Queue với các phương thức cơ bản như enqueue, dequeue, display, và frontElement. Bạn có thể thử chạy và điều chỉnh mã để hiểu rõ hơn về cách hoạt động của hàng đợi. Bạn có thể tìm hiểu thêm về các thuật toán sắp xếp trong lập trình ở đây. Chúc các bạn thành công !

Bên cạnh đó bạn có thể bắt đầu ngay con đường chinh phục trở thành lập trình viên chuyên nghiệp trong tương lai của mình bằng việc đăng ký tham gia khoá học lập trình tại đây: http://bit.ly/2SLPYFF. Hoặc gọi ngay cho Stanford theo hotline: 0963.723.236 - 0866.586.366 để được gọi lại tư vấn trực tiếp nhé.

==========🎬 🎬 🎬==========
☎️STANFORD – ĐÀO TẠO VÀ PHÁT TRIỂN CÔNG NGHỆ
Hotline: 0963 723 236 - 0866 586 366
Website: https://stanford.com.vn
Facebook: https://www.facebook.com/Stanford.com.vn
Youtube: http://bit.ly/2TkKT7I

Tags: hàng đợi, queue