Queue Và Deque Trong C++

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.

Related Posts
So sánh ngôn ngữ C++ và Java

Có nhiều điểm khác biệt và tương đồng giữa ngôn ngữ lập trình C++ và Java . Dưới đây là danh sách những điểm khác Read more

Con trỏ trong C/C++

Con trỏ là một trong những tính năng quan trọng của mỗi ngôn ngữ lập trình. Thực tế, để được Read more

Single Linked List C++ (Danh sách liên kết đơn).

Danh sách liên kết đơn là gì? Danh sách đơn liên kết (Danh sách liên kết đơn) là một dữ Read more

Con trỏ và cấp phát động trong C++

Con trỏ và cấp phát động trong C++ Con trỏ (pointer) là một khái niệm quan trọng và khó nhất Read more

Hãy bình luận đầu tiên

Để lại một phản hồi