Queue và Deque | How Kteam

Posted on by mtoplistChuyên mục:Top List

Bên cạnh stack
thì queue cũng là một cấu trúc dữ liệu hết sức thông dụng. Ngoài ra, một biến thể được coi là sự kết hợp của
stack và
queue là deque
được ứng dụng phổ biến trong các bài toán. Trong bài học ngày hôm nay, hãy cùng nhau đi tìm hiểu về
queue và
deque để xem nó là gì nhé!

Nội dung

Để có thể hiểu được bài học này một cách tốt nhất, các bạn nên có kiến thức cơ bản về các phần:

Trong bài học ngày hôm nay, chúng ta sẽ tìm hiểu về:

  • Khái niệm

    queue

    và cách sử dụng

  • Khái niệm

    deque

    và cách sử dụng

Queue

Khái niệm

Nếu như stack
là một cấu trúc dữ liệu dạng “vào sau, ra trước” (Last In First Out) thì
queue là một cấu trúc dữ liệu dạng “vào trước, ra trước” (First In First Out), có nghĩa là phần tử nào được vào trong
queue trước sẽ được ra trước.

Một ví dụ minh hoạ thực tế nằm chính ở tên gọi tiếng Việt của
queue là hàng đợi.
Queue giống như một hàng người xếp hàng mua vé vậy, người đến sau sẽ vào cuối hàng, người đến trước được mua vé trước và sau khi mua vé xong sẽ đi ra khỏi hàng để đến người tiếp theo.

Một queue
sẽ hỗ trợ các thao tác sau:

  • Thêm phần tử vào cuối

    queue

  • Loại bỏ phần tử ở đầu

    queue

  • Lấy ra phần tử đầu tiên trong

    queue

  • Lấy ra kích thước của

    queue

Sử dụng queue trong C++

Trong khoá học này, mình sẽ không giới thiệu cách cài đặt
queue thủ công do việc này sẽ khó khăn hơn so với
stack và gần như là không có ứng dụng trong thực tiễn.

Khai báo queue

Thông thường để thêm queue
vào chương trình, chúng ta sẽ thêm thư viện như sau:

#include<queue>

Tuy nhiên, ở trong suốt khoá học này mình sẽ sử dụng header sau:

#include<bits/stdc++.h>

Header này sẽ giúp chúng ta thêm tất cả các thư viện về các cấu trúc dữ liệu mà chúng ta sẽ học trong khoá học này.

Ta sẽ khai báo queue
như sau:

queue <{kiểu dữ liệu}> {tên
queue};

Ví dụ: queue<int> myQueue;

Các phương thức cơ bản của queue

Queue trong C++ sẽ hỗ trợ các phương thức sau:

  • push: Thêm phần tử vào cuối

    queue

  • pop: Loại bỏ phần tử ở đầu

    queue

  • front: Trả về giá trị là phần tử đầu tiên trong

    queue

  • size: Trả về số nguyên là kích thước của

    queue

  • empty: Trả về giá trị

    bool

    ,

    true

    nếu

    queue

    rỗng,

    false

    nếu

    queue

    không rỗng

Các phương thức trên đều mất độ phức tạp O(1).

Lưu ý: Cũng như stack, các phương thức pop và front khi được gọi phải đảm bảo queue không rỗng nếu không sẽ gây ra
Runtime Error. Do đó, nếu không chắc chắn, các bạn sẽ cần kiểm tra bằng phương thức empty trước khi gọi hai phương thức này.

Ở đây mình có một đoạn code demo các phương thức cơ bản của
queue:

#include<bits/stdc++.h>
using namespace std;

queue<int> q;

int main(){
    // Thêm các phần tử vào queue
    q.push(1);
    q.push(3);
    q.push(5);
    // Lúc này, queue là [1, 3, 5]

    // In ra phần tử đầu tiên trong queue
    cout << "Phan tu dau tien trong queue la: " << q.front() << endl;
    // In ra kích thước của queue
    cout << "Kich thuoc cua queue la: " << q.size() << endl;

    // Loại bỏ phần tử đầu tiên ra khỏi queue
    cout << "Loai bo phan tu dau trong queue" << endl;
    q.pop();
    // Khi này queue là [3, 5]

    // Kiểm tra queue có rỗng hay không
    if(q.empty()) cout << "Queue rong" << endl;
    else cout << "Queue khong rong" << endl;

    // In ra phần tử đầu tiên trong queue
    cout << "Phan tu dau tien trong queue la: " << q.front() << endl;
    // In ra kích thước của queue
    cout << "Kich thuoc cua queue la: " << q.size() << endl;
}

Khi chạy đoạn code trên, ta thu được kết quả:

Deque

Khái niệm

Trong bài học trước, mình đã giới thiệu về stack, một cấu trúc dữ liệu cho phép thêm dữ liệu ở cuối và lấy ra dữ liệu ở cuối. Vừa rồi, mình đã giới thiệu thêm cho
các bạn về queue, một cấu trúc dữ liệu cho phép thêm dữ liệu ở cuối và lấy ra dữ liệu ở đầu. Vậy thì có cấu trúc dữ liệu nào có thể kết hợp các tính chất của
stack và
queue hay không? Câu trả lời chính là
deque.

Deque là viết tắt của
double-ended queue, có nghĩa là hàng đợi hai đầu. Một
deque
sẽ hỗ trợ các phươ ng thức sau:

  • Thêm một phần tử vào cuối

    deque

  • Thêm một phần tử vào đầu

    deque

  • Bỏ đi phần tử ở cuối

    deque

  • Bỏ đi phần tử ở đầu

    deque

  • Lấy ra giá trị phần tử đầu

    deque

  • Lấy ra giá trị phần tử cuối

    deque

Sử dụng deque trong C++

Giống như với queue, việc cài đặt
deque thủ công là tương đối phức tạp và không cần thiết nên mình sẽ không hướng dẫn các bạn cài đặt
deque thủ công.

Khai báo deque

Thông thường để thêm deque
vào chương trình, chúng ta sẽ thêm thư viện như sau:

#include<deque>

Tuy nhiên, ở trong suốt khoá học này mình sẽ sử dụng header sau:

#include<bits/stdc++.h>

Header này sẽ giúp chúng ta thêm tất cả các thư viện về các cấu trúc dữ liệu mà chúng ta sẽ học trong khoá học này.

Ta sẽ khai báo deque
như sau:

deque <{kiểu dữ liệu}> {tên
deque};

Ví dụ: deque<int> myDeque;

Các phương thức cơ bản của deque

Deque trong C++ sẽ hỗ trợ các phương thức cơ bản sau:

  • push_front: Thêm phần tử vào đầu

    deque

  • push_back: Thêm phần tử vào cuối

    deque

  • pop_front: Loại bỏ phần tử ở đầu

    deque

  • pop_back: Loại bỏ phần tử ở cuối

    deque

  • front: Trả về giá trị là phần tử đầu trong

    deque

  • back: Trả về giá trị là phần tử cuối trong

    deque

  • size: Trả về giá trị nguyên là kích thước của

    deque

  • empty: Trả về giá trị

    bool

    ,

    true

    nếu

    deque

    rỗng,

    false

    nếu

    deque

    không rỗng

Các phương thức trên đều mất độ phức tạp O(1).

Lưu ý: Cũng như các cấu trúc dữ liệu khác, các phương thức pop_front, pop_back, front, back khi được gọi phải đảm bảo deque không rỗng nếu không sẽ gây ra
Runtime Error. Do đó, nếu không chắc chắn, các bạn sẽ cần kiểm tra bằng phương thức empty trước khi gọi các phương thức trên.

Ở đây mình có một đoạn code demo về các phương thức của
deque như sau:

#include<bits/stdc++.h>
using namespace std;

deque<int> dq;

int main(){
    // Thêm 3, 6 vào cuối deque
    dq.push_back(3);
    dq.push_back(6);
    // Lúc này deque là [3, 6]
    // Thêm 4 vào đầu deque
    dq.push_front(4);
    // Lúc này deque là [4, 3, 6]
    // Thêm 1 vào đầu deque
    dq.push_front(1);
    // Lúc này deque là [1, 4, 3, 6]

    cout << "Kich thuoc cua deque la: " << dq.size() << endl;
    cout << "Phan tu dau tien trong deque la: " << dq.front() << endl;
    cout << "Phan tu cuoi cung trong deque la: " << dq.back() << endl;

    cout << "Xoa bo phan tu cuoi deque" << endl;
    dq.pop_back();
    // Lúc này deque là [1, 4, 3]

    cout << "Kich thuoc cua deque la: " << dq.size() << endl;
    cout << "Phan tu dau tien trong deque la: " << dq.front() << endl;
    cout << "Phan tu cuoi cung trong deque la: " << dq.back() << endl;

    cout << "Xoa bo phan tu dau deque" << endl;
    dq.pop_front();
    // Lúc này deque là [4, 3]

    cout << "Kich thuoc cua deque la: " << dq.size() << endl;
    cout << "Phan tu dau tien trong deque la: " << dq.front() << endl;
    cout << "Phan tu cuoi cung trong deque la: " << dq.back() << endl;
}

Khi chạy đoạn code trên ta thu được kết quả sau:

Ứng dụng trong thực tế của queue và deque

Khi học bài này, sẽ có bạn thấy lạ: Tại sao mình không nêu ra một bài toán ban đầu rồi suy luận để đi đến cấu trúc dữ liệu như trong bài trước? Lí do là vì
queue và
deque hầu như không đứng độc lập để giải quyết các bài toán.

Queue được ứng dụng trong các thuật toán thiên về yếu tố cần duyệt và lưu trữ các trạng thái,  điển hình cho dạng thuật toán như vậy là loang và BFS. Đối với
deque, thuật toán ứng dụng quan trọng nhất là tìm kiếm min-max trên đoạn tịnh tiến. Các thuật toán trên sẽ đều có trong khoá học này của mình. Khi đi đến thuật toán đó, mình sẽ hướng dẫn cho
các bạn cách sử dụng cụ thể.

Tất nhiên, queue
và deque sẽ có thể ứng dụng trong các bài toán khác. Tuỳ vào tính chất của bài toán và tính chất của
queue và
deque, các bạn có thể sử dụng chúng linh hoạt sao cho phù hợp.

Kết luận

Qua bài này chúng ta đã nắm được về queue
và deque.

Bài sau chúng ta sẽ bắt đầu tìm hiểu về cấu trúc dữ liệu
Linked List.

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.

mtoplist