Cấu trúc dữ liệu hàng đợi (Queue) là một phần quan trọng trong lập trình. Nó hoạt động theo nguyên tắc "First In First Out" (FIFO), có nghĩa là đối tượng được thêm vào hàng đợi trước sẽ được lấy ra trước. Bài viết này sẽ giúp bạn hiểu rõ hơn về Queue và sự khác biệt giữa Queue và Deque trong ngôn ngữ lập trình C++.
Chức năng của Queue
Một cấu trúc dữ liệu Queue hoàn chỉnh có những chức năng sau:
- Dequeue: Lấy ra phần tử đầu hàng đợi.
- Enqueue: Thêm một phần tử vào cuối hàng đợi.
- IsEmpty: Kiểm tra xem Queue có đang trống hay không.
- Front: Truy xuất phần tử ở đầu hàng đợi.
Cách tự xây dựng hàng đợi trong C++
Dưới đây là một ví dụ về cách tự xây dựng hàng đợi trong ngôn ngữ lập trình 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
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 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
Trong ngôn ngữ lập trình C++, C++ STL cung cấp một cấu trúc Queue với những chức năng sau:
- empty(): Kiểm tra hàng đợi có đang rỗng không.
- size(): Trả về kích thước hàng đợi hiện tại.
- front(): Trả về phần tử đầu tiên của Queue.
- back(): Trả về phần tử cuối cùng của hàng đợi.
- push(): Thêm một phần tử vào Queue.
- emplace(): Thêm một phần tử vào Queue.
- pop(): Xóa phần tử ở đầu hàng đợi.
- swap(): Hoán đổi nội dung giữa hai hàng đợi.
Dưới đây là một mã mẫu về việc sử dụng Queue trong ngôn ngữ lập trình C++ STL:
#include
#include
int main()
{
std::queue 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> b; // Khai báo queue chứa pair
b.emplace(std::make_pair(0, 1)); // Thêm một 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> c; // Khai báo queue chứa pair
b.swap(c); // Hoán đổi dữ liệu của hai 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 lập trình C++ STL cung cấp những chức năng để bổ trợ cho Queue cùng với chức năng của vector. Deque có thể thực hiện vài chức năng nổi bật như:
- begin(): Trả về con trỏ ở vị trí đầu tiên của Deque.
- end(): Trả về con trỏ ở vị trí cuối cùng của Deque.
- size(): Trả về kích thước của Deque.
- resize(): Thay đổi kích thước của Deque.
- empty(): Kiểm tra Deque có rỗng hay không.
- operator(): Truy xuất một phần tử ở một vị trí đã chỉ định trong Deque.
- front(): Trả về phần tử đầu tiên của Deque.
- back(): Trả về phần tử cuối cùng của Deque.
- push_back(): Thêm một phần tử vào cuối Deque.
- push_front(): Thêm một phần tử vào đầu Deque.
- pop_back(): Xóa phần tử ở cuối Deque.
- pop_front(): Xóa phần tử ở đầu Deque.
- insert(): Thêm một phần tử vào một vị trí đã chỉ định trong Deque.
- erase(): Xóa một phần tử ở một vị trí đã chỉ định trong Deque.
- clear(): Xóa toàn bộ các phần tử trong Deque.
- emplace_front(), emplace_back(): Thêm một phần tử vào Deque và khởi tạo ngay tại thời điểm thêm.
Deque là một cấu trúc dữ liệu tích hợp từ vector và hàng đợi Queue trong ngôn ngữ lập trình C++. Bên cạnh việc lưu trữ dữ liệu theo nguyên tắc FIFO, Deque còn có thể được sử dụng như một ngăn xếp theo nguyên tắc LIFO và có khả năng truy xuất vào bất kỳ phần tử nào.
#include
#include
#include
int main()
{
std::deque 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ư một 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); // Thay đổi kích thước của hàng đợi thành 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(); // Xóa 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(); // Xóa 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 sau bướ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 sau bước này: [2, 3, 4]
a.clear(); // Xóa toàn bộ 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
} Hàng đợi là một cấu trúc dữ liệu quen thuộc mà tất cả các lập trình viên đều đã biết. Thông qua bài viết này, chúng ta đã được so sánh rõ ràng về sự khác biệt giữa Queue và Deque. Hy vọng rằng bài viết của chúng tôi đã giúp bạn hiểu rõ hơn về hai cấu trúc này.
