Thực hành cài đặt và sử dụng Hàng đợi – Queue trong C++ – VNTALKING

Posted on by adminChuyên mục:Kiến thức Internet
Tiếp tục series về thuật toán sâu xa, tất cả chúng ta cùng nhau tìm hiểu và khám phá về một loại cấu trúc tài liệu rất phổ cập, đó là Hàng đợi ( Queue ) .
Hàng đợi – Queue là kiểu cấu trúc tài liệu tuyến tính, việc truy xuất tài liệu của nó theo nguyên tắc FIFO, tức là tài liệu vào trước thì lấy trước, vào sau lấy sau .

Thực hành cài đặt và sử dụng Hàng đợi - Queue trong C++

Với Queue, phần tử đầu tiên được đưa vào Queue cũng sẽ là phần tử đầu tiên được xóa nếu có yêu cầu. Tức là, nó không cho phép bạn truy xuất trực tiếp dữ liệu nằm ở giữa queue.

Lý thuyết Queue

Queue – hàng đợi nó mô phỏng lại văn hóa truyền thống xếp hàng của con người tất cả chúng ta thôi. Khi tất cả chúng ta đến một tiệm cắt tóc, ngày hôm nay khá là đông khách nên mọi người phải xếp hàng. Ai đến trước thì được cắt trước, cứ lần lượt từng người một. Ai mà tất bật đến sau mà đòi cắt trước thì chỉ có cắt … cái đầu gối thôi 😊

Nguyên lý hoạt động của Queue là FIFO (First In, First Out), tức là vào trước ra trước.

Lý thuyết hàng đợi - queue

Về cơ bản, cấu trúc tài liệu kiểu Queue cung ứng một số ít thao tác để làm bạn như sau :

  • enqueue: Thêm phần tử vào queue, tất nhiên phần tử này sẽ vào cuối của queue
  • dequeue: Xóa phần tử đầu trong queue. Nếu queue rỗng thì thông báo lỗi.
  • isEmpty: Kiểm tra xem queue có rỗng không?
  • isFull: Kiểm tra queue đã đầy hay chưa?
  • peek: Lấy giá trị của phần tử đầu trong queue, chỉ lấy giá trị ra chứ kg có xóa phần tử, queue không thay đổi.

Khi nào sử dụng Queue ?

Sau khi hiểu được định nghĩa cũng như nguyên lý hoạt động của Queue rồi, chúng ta sẽ đặt ngay câu hỏi, vậy Queue được ứng dụng trong những bài toán nào? Khi nào thì sử dụng Queue mà không phải Stack?

Để vấn đáp cho câu hỏi này một cách đúng chuẩn 100 % thì thật là khó ? Việc vận dụng một công cụ trong những bài toán thực tiễn là vô cùng phong phú. Với những đúc rút kinh nghiệm tay nghề thực tiễn và qua nghiên cứu và điều tra, mình thấy Queue thường sử dụng trong những trường hợp sau :

  • Sử dụng queue để lưu trữ tạm các dữ liệu, thực hiện tính toán các biểu thức toán học.
  • Ứng dụng trong các bài toán về in ấn.
  • Quản lý các request trên một tài nguyên được chia sẻ, ví dụ như lập lịch CPU (CPU scheduling)
  • Routers và switches trong mạng networking
  • Quản lý các bài hát (media playlist) trong các chương trình đa phương tiện (Media players)
  • Và còn rất nhiều ứng dụng khác nữa.v.v… (các bạn bổ sung thêm ở phần bình luận nhé)

💦 Đọc thêm về các thuật toán:

Thực hành Implement một queue bằng C + +

Ở phần này, tất cả chúng ta sẽ cùng nhau setup những tính năng chính của một queue ( như đã đề cập ở phần trên ). Có nhiều cách để bạn tạo queue, nhưng sau khi tìm hiểu thêm rất nhiều ví dụ, mình nghĩ sử dụng mảng để tạo queue là cách đơn thuần nhất .

Để đỡ dài dòng lan man, mình sẽ comment thẳng vào trong code để giải thích nhé.

1. Cài đặt Queue

#include 
#include 
using namespace std;
 
// Define the default capacity of a queue
#define SIZE 1000
 
// A class to store a queue
class Queue
{
    int *arr;       // array to store queue elements
    int capacity;   // maximum capacity of the queue
    int front;      // front points to the front element in the queue (if any)
    int rear;       // rear points to the last element in the queue
    int count;      // current size of the queue
 
public:
    Queue(int size = SIZE);     // constructor
    ~Queue();                   // destructor
 
    int dequeue();
    void enqueue(int x);
    int peek();
    int size();
    bool isEmpty();
    bool isFull();
};
 
// Constructor to initialize a queue
Queue::Queue(int size)
{
    arr = new int[size];
    capacity = size;
    front = 0;
    rear = -1;
    count = 0;
}
 
// Destructor to free memory allocated to the queue
Queue::~Queue() {
    delete[] arr;
}

2. Kiểm tra size queue

// Utility function to return the size of the queue
int Queue::size() {
    return count;
}

3. isEmpty – Kiểm tra queue có rỗng không ?

// Utility function to check if the queue is empty or not
bool Queue::isEmpty() {
    return (size() == 0);
}

4. isFull – Kiểm tra xem queue đã đầy hay chưa ?

// Utility function to check if the queue is full or not
bool Queue::isFull() {
    return (size() == capacity);
}

5. enqueue – Thêm mới thành phần

// Utility function to add an item to the queue
void Queue::enqueue(int item)
{
    // check for queue overflow
    if (isFull())
    {
        cout << "Overflow\nProgram Terminated\n";
        exit(EXIT_FAILURE);
    }
 
    cout << "Inserting " << item << endl;
 
    rear = (rear + 1) % capacity;
    arr[rear] = item;
    count++;
}

6. dequeue – Xóa thành phần

// Utility function to dequeue the front element
int Queue::dequeue()
{
    // check for queue underflow
    if (isEmpty())
    {
        cout << "Underflow\nProgram Terminated\n";
        exit(EXIT_FAILURE);
    }
 
    int x = arr[front];
    cout << "Removing " << x << endl;
 
    front = (front + 1) % capacity;
    count--;
 
    return x;
}

7. peek – lấy giá trị của thành phần tiên phong trong queue

int Queue::peek()
{
    if (isEmpty())
    {
        cout << "Underflow\nProgram Terminated\n";
        exit(EXIT_FAILURE);
    }
    return arr[front];
}

8. Sử dụng queue

int main()
{
    // create a queue of capacity 5
    Queue q(5);
 
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
 
    cout << "The front element is " << q.peek() << endl;
    q.dequeue();
 
    q.enqueue(4);
 
    cout << "The queue size is " << q.size() << endl;
 
    q.dequeue();
    q.dequeue();
    q.dequeue();
 
    if (q.isEmpty()) {
        cout << "The queue is empty\n";
    }
    else {
        cout << "The queue is not empty\n";
    }
 
    return 0;
}

Toàn bộ code minh họa trong bài viết được để tại đây :
Trên đây là những lý giải triết lý và cách để bạn thiết lập một queue. Mình hy vọng, nó sẽ ích cho bạn trong những bài tập trong thực tiễn sau này .

admin