Queue hay hàng đợi trong cơ sở lập trình đó là một cấu trúc dữ liệu có chức năng lưu giữ đối tượng theo cơ chế First In First Out – FIFO. Vậy nó được sử dụng như thế nào và bao gồm những chức năng gì? Hãy cùng chúng tôi tìm hiểu chi tiết về nó qua bài viết sau nhé!

Chức năng của Queue là gì?

Một cấu trúc Queue hoàn chỉnh sẽ có những chức năng sau:

  • Dequeue: Mục đích là lấy ra phần tử đầu Queue.
  • Enqueue: Mục đích là để thêm một phần tử vào cuối của hàng đợi.
  • IsEmpty: Dùng để kiểm tra xem Queue hiện tại có đang trống hay không.
  • Front: Dùng để truy nhập phần tử ở đầu hàng đợi.
Queue hoàn chỉnh sẽ có chức năng gì?
Queue hoàn chỉnh sẽ có chức năng gì?

Cách tự xây dựng hàng đợi trong C++

#include 

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 // Xây dựng hàng đợi

{

    T base[MAX]; // Mảng base lưu trữ thông tin

    T *a = base; // Con trỏ của mảng base

    int size = 0;

    public:

        Queue() // Hàm khởi tạo

        {

        }

        void Enqueue(T x) // Thêm 1 phần tử vào đầu hàng đợi

        {

            a[size] = x; // Đặt x vào cuối hàng đợi

            size++; // Tăng kích thước hàng đợi lên 1

        }

        void Dequeue() // Loại bỏ phần tử ở đầu hàng đợi

        {

            ++a; // Loại bỏ phần tử ở đầu hàng đợi

            size–; // Giảm kích cỡ hàng đợi đi 1

        }

        bool isEmpty() // Kiểm tra hàng đợi có rỗng hay không

 {

            return size > 0; // Kiểm tra kích cỡ có lớn hơn 0 hay không?

        }

        T front() // Trả về phần tử ở đầu hàng đợi

        {

            return a[0];

        }

};

int main() // Chương trình chạy mẫu

{

    Queue<int> a;

    a.Enqueue(1); // Thêm 1 vào cuối hàng đợi, hàng đợi lúc này: [1]

    a.Enqueue(2); // Thêm 2 vào cuối hàng đợi, hàng đợi lúc này: [1, 2]

    a.Dequeue(); // 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.front(); // In ra phần tử ở đầu hàng đợi, lúc này đang là 2

}

Trong ngôn ngữ  C++ STL cấu trúc hàng đợi

Cấu trúc hàng đợi

Queue hoạt động dựa vào nguyên tắc FIFO
Queue hoạt động dựa vào nguyên tắc FIFO

Trong C++ STL các chức năng của Queue là gì:

  • empty(): Mục đích là để Kiểm tra hàng đợi hiện tại có đang rỗng không.
  • size(): Là để trả về kích thước hàng đợi hiện tại.
  • front(): Dùng để trả về phần tử đầu tiên của Queue.
  • back(): Dùng để 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 Queue, biến nạp thêm phải cần được khởi tạo trước đó.
  • emplace(): Để nạp thêm một phần tử vào Queue, biến có thể được khởi tạo ngay tại thời điểm nạp.
  • pop(): Dùng để Xóa một phần tử ở đầu hàng đợi.
  • swap(): Sử dụng khi cần hoán đổi nội dung giữa 2 hàng đợi

Trong lập trình ngôn ngữ C++ STL, code mẫu Queue là gì?

#include 

#include 

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

    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

    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

}

Ứng dụng hàng đợi trong việc in ấn
Ứng dụng hàng đợi trong việc in ấn

Cấu trúc Deque 

Cấu trúc Deque trong khi lập trình C++ STL là một phần để bổ trợ cho những chức năng của Queue đã kể trên cùng với đó là chức năng của vector. Có thể kể đến vài chức năng nổi bật như:

  • begin(): Dùng để trả về con trỏ ở vị trí đầu tiên của Deque.
  • end(): Khi cần trả về con trỏ ở vị trí cuối cùng của Deque chúng ta dùng end().
  • size(): Trả về kết quả là kích thước của Deque.
  • resize(): Nếu bạn cần thay đổi kích thước của 1 Deque thì dùng resize()
  • empty(): Mục đích là để kiểm tra xem Deque có rỗng hay không.
  • operator(): Khi cần truy nhập một phần tử ở một vị trí của Deque đã chỉ định, đây là chức năng không thể thực hiện được trên hàng đợi.
  • front(): Kết quả trả về phần tử đầu tiên của Deque.
  • back(): Kết quả trả về phần tử cuối cùng của Deque.
  • push_back(): Dùng khi cần thêm 1 phần tử vào cuối Deque.
  • push_front(): Dùng khi cần thêm 1 phần tử vào đầu Deque.
  • pop_back(): Mục đích để xóa phần tử ở cuối Deque.
  • pop_front(): Mục đích để xóa phần tử ở đầu Deque.
  • insert(): Nếu cần thêm 1 phần tử vào 1 vị trí của Deque đã chỉ định erase(): Xóa 1 phần tử ở 1 vị trí chỉ định của Deque thì dùng erase() .
  • clear(): Dùng để xóa toàn bộ mọi phần tử trong Deque.
  • emplace_front(), emplace_back(): Mục đích tương tự như emplace() trong Queue.

Qua đây, bạn có thể thấy cấu trúc dữ liệu của Deque là tích hợp từ vector và hàng đợi Queue của C++. Bên cạnh việc lưu dữ liệu theo dạng FIFO thì Deque có thể được sử dụng như một last in first out – LIFO. Và chúng cũng có khả năng dùng để truy nhập vào một phần tử bất kỳ nào đó. 

#include 

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

}

Queue là một cấu trúc dữ liệu mà tất cả những lập trình viên đều đã biết. Bài viết trên đây của chúng tôi là để so sánh cho bạn thấy rõ giữa Queue và Deque khác nhau như thế nào. Hi vọng qua bài viết của FPT Aptech đã giúp bạn hiểu rõ hơn về 2 cấu trúc này. 

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

0981578920
icons8-exercise-96