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 Aptech tìm hiểu chi tiết về nó qua bài viết sau nhé!
Nội dung
Chức năng của Queue
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
- 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.
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
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
- 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, 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, 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
}
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 đã 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.
| FPT Aptech trực thuộc Tổ chức Giáo dục FPT có hơn 25 năm kinh nghiệm đào tạo lập trình viên quốc tế tại Việt Nam, và luôn là sự lựa chọn ưu tiên của các sinh viên và nhà tuyển dụng. |
