Hàng đợi ưu tiên



Hàng đợi ưu tiên

Hàng đợi là một cấu trúc dữ liệu được sử dụng rộng rãi trong nhiều vấn đề của đời sống. Ở bài viết này mình sẽ đề cập sơ qua về cấu trúc dữ liệu hàng đợi và các biến để của nó trong ngôn ngữ C++.

Khái niệm về hàng đợi ưu tiên



Cấu trúc dữ liệu hàng đợi được định nghĩa như sau:
Hàng đợi là một cấu trúc dữ liệu một chiều được sử dụng để lưu các phần tử theo quy luật FIFO - First In First Out.

FIFO - First In First Out có nghĩa là vào trước ra trước, tức là bạn chỉ được lấy ra phần tử trên cùng mà thôi, những phần tử khác phải được lấy theo thứ tự.

Một hàng đợi cơ bản có các chức năng sau:

  • Dequeue: Lấy ra phần tử đầu queue.
  • Enqueue: Thêm một phần tử vào cuối của queue.
  • IsEmpty: Kiểm tra xem queue hiện tại có đang rỗng hay không.
  • Front: Truy nhập phần tử ở đầu queue.
Tự xây dựng hàng đợi cho riêng mình:

#include <bits/stdc++.h>
const int MAX = 1e5; // Kích cỡ lớn nhất của hàng đợi, biến này có thể thay đổi tùy vào bạn
template<typename T> class Queue
{
    T base[MAX];
    T *a = base;
    int size = 0;
    public:
        Queue()
        {
            
        }
        void Enqueue(T x)
        {
            a[size] = x;
            size++;
        }
        void Dequeue()
        {
            ++a;
            size--;
        }
        bool isEmpty()
        {
            return size > 0;
        }
        T front()
        {
            return a[0];
        }
};
int main() // Chương trình chạy mẫu
{
    Queue<int> a;
    a.Enqueue(1);
    a.Enqueue(2);
    a.Dequeue();
    std::cout << a.front();
}

Một vài ứng dụng của hàng đợi:

  • Sản xuất và tiêu thụ (ứng dụng trong các hệ điều hành song song).
  • Bộ đệm (ví dụ: Nhấn phím -> Bộ đệm -> CPU xử lý).
  • Xử lý các lệnh trong máy tính (ứng dụng trong hệ điều hành, trình biên dịch), hàng đợi các tiến trình chờ được xử lý.
  • Trong lập trình thi đầu, hàng đợi được sử dụng như là phương tiện cho nhiều thuật toán, như là 2-pointers method và BFS.

Hàng đợi trong C++


Queue

Cấu trúc queue trong C++ STL hỗ trợ các chức năng sau:

  • empty(): Kiểm tra xem hàng đợi hiện tại có đang rỗng hay không.
  • size(): Trả về kích thước hàng đợi hiện tại.
  • front(): Trả về phần tử đầu tiên của hàng đợi.
  • back(): Trả về phần tử cuối cùng của hàng đợi.
  • push(): Nạp thêm một phần tử vào hàng đợi, biến cần được khởi tạo trước đó.
  • emplace(): Nạp thêm một phần tử vào hàng đợi, có thể khởi tạo biến ngay tại thời điểm nạp.
  • pop(): Xóa một phần tử ở đầu của hàng đợi.
  • swap(): Hoán đổi nội dung giữa 2 queue.
Ngoài 4 hàm cơ bản ra thì queue của STL C++ còn hỗ trợ các hàm khác như size() hay back() giúp chúng ta thuận tiện trong việc kiểm soát cấu trúc dữ liệu này hơn, ngoài ra chức năng chính của nó không thay đổi.

Chú ý: queue không hỗ trợ truy nhập 1 phần tử ở vị trí ngoài vị trí đầu và vị trí cuối.

Một đoạn code mẫu về sử dụng deque:

#include <bits/stdc++.h>
int main()
{
    std::queue<int> a; // Khai báo queue chứa int
    
    std::cout << a.empty() << '\n'; // Lúc này hàng đợi đang rỗng, nên sẽ in ra 1
    
    a.push(1); // Thêm 1 vào cuối hàng đợi, hàng đợi lúc này: [1]
    a.push(2); // Thêm 2 vào cuối hàng đợi, hàng đợi lúc này: [1, 2]
    std::cout << a.size() << '\n'; // In ra kích thước hàng đợi hiện tại, lúc này là 2
    std::cout << a.empty() << '\n'; // Lúc này hàng đợi không rỗng, nên sẽ in ra 0
    std::cout << a.front() << '\n'; // In ra phần tử ở đầu hàng đợi, lúc này là 1
    std::cout << a.back() << '\n'; // In ra phần tử ở cuối hàng đợi, lúc này là 2
    
    a.pop(); // Loại bỏ phần tử ở đầu hàng đợi, lúc này đang là 1, hàng đợi sau bước này: [2]
    std::cout << a.size() << '\n'; // In ra kích thước hàng đợi hiện tại, lúc này là 1
    std::cout << a.front() << '\n'; // In ra phần tử ở đầu hàng đợi, lúc này là 2
    
    std::queue<std::pair<int, int> > b; // Khai báo queue chứa pair<int, int>
    b.emplace(std::make_pair(0, 1)); // Thêm 1 pair {0, 1} vào cuối hàng đợi, pair được khởi tạo ngay khi thêm vào
    std::cout << b.size() << '\n'; // In ra kích thước hàng đợi hiện tại, lúc này là 1
    std::cout << b.front().first << ' ' << b.front().second << '\n'; // In ra phần tử ở đầu hàng đợi, lúc này là {0, 1}
    
    std::queue<std::pair<int, int> > c; // Khai báo queue chứa pair<int, int>
    b.swap(c); // Hoán đổi dữ liệu của 2 hàng đợi cùng loại
    std::cout << b.empty() << '\n'; // Lúc này hàng đợi đang rỗng do vừa tráo đổi dữ liệu với một hàng đợi rỗng, nên sẽ in ra 1
}

Deque

Cấu trúc deque trong C++ STL hỗ trợ tất cả các chức năng mà queue có ở trên, cộng thêm các chức năng của 1 vector. 

Một vài chức năng nổi bật của deque:

  • begin(): Trả về con trỏ ở vị trí đầu tiên của deque.
  • end(): Trả về con trỏ ở vị trí cuối cùng của deque.
  • size(): Trả về kích thước của deque.
  • resize(): Thay đổi kích thước của 1 deque.
  • empty(): Kiểm tra xem deque có rỗng hay không.
  • operator[]: Truy nhập một phần tử ở một vị trí chỉ định của deque, chức năng này không thể thực hiện được trên queue.
  • front(): Trả về phần tử đầu tiên của deque.
  • back(): Trả về phần tử cuối cùng của deque.
  • push_back(): Thêm 1 phần tử vào cuối deque.
  • push_front(): Thêm 1 phần tử vào đầu deque.
  • pop_back(): Xóa phần tử ở cuối deque.
  • pop_front(): Xóa phần tử ở đầu deque.
  • insert(): Thêm 1 phần tử vào 1 vị trí chỉ định của deque.
  • erase(): Xóa 1 phần tử ở 1 vị trí chỉ định của deque.
  • clear(): Xóa toàn bộ phần tử trong deque.
  • emplace_front(), emplace_back(): Tương tự emplace() trong queue.
Ngoại trừ việc hỗ trợ lưu dữ liệu dạng FIFO như queue thì deque cũng có thể được sử dụng dưới dạng LIFO (last in first out – vào sau ra trước) và cũng có thể truy nhập một phần tử bất kì. Ngoài các chức năng của vector, deque còn hỗ trợ xóa và thêm phần tử ở đầu dãy trong O(1), thay vì O(n) như vector.

Vậy nhược điểm của deque với hai CTDL trên là gì? Thực ra là không có, nếu có thì chẳng qua là nó sinh sau nên không được phổ biến bằng hai CTDL trên mà thôi. Tất cả các bài cần sử dụng queue và vector (thậm chí cả stack) đề có thể sử dụng deque để thay thế.


#include <bits/stdc++.h>
int main()
{
    std::deque<int> a; // Khai báo deque
    
    std::cout << a.empty() << '\n'; // Lúc này hàng đợi đang rỗng, nên sẽ in ra 1
    
    a.push_back(2); // Thêm 2 vào cuối hàng đợi, hàng đợi lúc này: [2]
    a.push_front(1); // Thêm 1 vào đầu hàng đợi, hàng đợi lúc này: [1, 2]
    a.push_back(3); // Thêm 3 vào cuối hàng đợi, hàng đợi lúc này: [1, 2, 3]
    a.push_front(4); // Thêm 4 vào đầu hàng đợi, hàng đợi lúc này: [4, 1, 2, 3]
    
    std::cout << a.size() << '\n'; // In ra kích thước hàng đợi hiện tại, lúc này là 4
    std::cout << a.empty() << '\n'; // Lúc này hàng đợi không rỗng, nên sẽ in ra 0
    
    std::cout << a.front() << '\n'; // In ra phần tử ở đầu hàng đợi, lúc này là 4
    std::cout << a.back() << '\n'; // In ra phần tử ở cuối hàng đợi, lúc này là 3
    std::sort(a.begin(), a.end()); // Sắp xếp hàng đợi như 1 vector bình thường, hàng đợi lúc này: [1, 2, 3, 4]
    
    for (int i = 0; i < a.size(); i++)
    {
        std::cout << a[i] << ' '; // In ra các giá trị của hàng đợi, hàng đợi lúc này: [1, 2, 3, 4]
    }
    std::cout << '\n';
    
    a.resize(5); // Ép kích thước của hàng đợi lên 5, hàng đợi lúc này: [1, 2, 3, 4, 0]
    a[4] = 5; // Gán giá trị cho vị trí i = 4 của hàng đợi, hàng đợi lúc này: [1, 2, 3, 4, 5]
    
    a.pop_front(); // Loại bỏ phần tử ở đầu hàng đợi, lúc này đang là 1, hàng đợi sau bước này: [2, 3, 4, 5]
    std::cout << a.size() << '\n'; // In ra kích thước hàng đợi hiện tại, lúc này là 4
    std::cout << a.front() << '\n'; // In ra phần tử ở đầu hàng đợi, lúc này là 2
    a.pop_back(); // Loại bỏ phần tử ở cuối hàng đợi, lúc này đang là 5, hàng đợi sau bước này: [2, 3, 4]
    std::cout << a.back() << '\n';  // In ra phần tử ở cuối hàng đợi, lúc này là 4
    
    a.insert(a.begin() + 1, 0); // Chèn 0 vào vị trí i = 1 của hàng đợi, hàng đợi lúc này: [2, 0, 3, 4]
    a.erase(a.begin() + 1); // Xóa phần tử tại vị trí i = 1 của hàng đợi, hàng đợi lúc này: [2, 3, 4]
    a.clear(); // Xóa tất cả các phần tử của hàng đợi
    
    std::cout << a.empty() << '\n'; // Lúc này hàng đợi đang rỗng, nên sẽ in ra 1
    
}

Chúc bạn thành công.

Nhận xét