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.
Để lại một phản hồi
Bạn phải đăng nhập để gửi phản hồi.