Hàng đợi trong C++ | Sử dụng hàng đợi trong thư viện STL

Hàng đợi là một cấu trúc dữ liệu cơ bản mà lập trình viên nào cũng cần biết. Ở bài này chúng ta sẽ tìm hiểu về các cấu trúc dữ liệu hàng đợi và tiến hành cài đặt hàng đợi trong C++ sử dụng bộ thư viện STL bao gồm queue và deque. Chúng ta sẽ cùng nhau đi cài đặt, làm rõ sự khác nhau giữa queue và dequee trong bài này luôn.

Nhắc lại khái niệm hàng đợi

Nếu bạn đọc quan tâm tới việc tự cài đặt cấu trúc dữ liệu hàng đợi, hãy tham khảo bài viết hàng đợi nhé.

Định nghĩa hàng đợi

Hàng đợi (tiếng anh: Queue) là một cấu trúc dữ liệu dùng để lưu giữ các đối tượng theo cơ chế FIFO (viết tắt từ tiếng Anh: First In First Out), nghĩa là “vào trước ra trước”.

unnamed file

Một cấu trúc queue có các chức năng cơ bản như sau:

Dequeue: Lấy ra phần tử đầu queue.
Enqueue: Thêm một phần tử vào cuối của queue.
IsEmpty: Kiểm tra xem queue hiện tại có đang rỗng hay không.
Front: Truy nhập phần tử ở đầu queue.

Tự xây dựng hàng đợi trong C++

#include <iostream>
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
}

Kết quả chạy chương trình:

Các cấu trúc hàng đợi trong C++ STL

Cấu trúc Queue

Cấu trúc queue trong C++ STL hỗ trợ các chức năng sau:

empty(): Kiểm tra xem hàng đợi hiện tại có đang rỗng hay 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 hàng đợi.
back(): 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 hàng đợi, biến cần được khởi tạo trước đó.
emplace(): Nạp thêm một phần tử vào hàng đợi, có thể khởi tạo biến ngay tại thời điểm nạp.
pop(): Xóa một phần tử ở đầu của hàng đợi.
swap(): Hoán đổi nội dung giữa 2 queue.

Ngoài 4 hàm cơ bản ra thì queue của STL C++ còn hỗ trợ các hàm khác như size() hayback() giúp chúng ta thuận tiện trong việc kiểm soát cấu trúc dữ liệu này hơn, ngoài ra chức năng chính của nó không thay đổi.

Chú ý: queue không hỗ trợ truy nhập 1 phần tử ở vị trí ngoài vị trí đầu và vị trí cuối.

Một đoạn code mẫu về sử dụng queue trong C++ STL:

#include <iostream>
#include <queue>

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<int, int>
	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<int, int>
	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
}

Kết quả chạy chương trình:

Bài tập sử dụng Queue:

Bài tập hàng đợi – Luyện Code
https://www.spoj.com/PTIT/problems/P175SUME/
https://vn.spoj.com/problems/MSE07B/
https://www.hackerearth.com/practice/data-structures/queues/basics-of-queues/practice-problems/

Cấu trúc Deque

Cấu trúc deque trong C++ STL hỗ trợ tất cả các chức năng mà queue có ở trên, cộng thêm các chức năng của 1 vector. Một vài chức năng nổi bật của deque:

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 1 deque.
empty(): Kiểm tra xem deque có rỗng hay không.
operator[]: Truy nhập một phần tử ở một vị trí chỉ định của deque, chức năng này không thể thực hiện được trên queue.
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 1 phần tử vào cuối deque.
push_front(): Thêm 1 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 1 phần tử vào 1 vị trí chỉ định của deque.
erase(): Xóa 1 phần tử ở 1 vị trí chỉ định của deque.
clear(): Xóa toàn bộ phần tử trong deque.
emplace_front(), emplace_back(): Tương tự emplace() trong queue.

Như ta có thể thấy, deque là cấu trúc dữ liệu tích hợp từ vector và queue của C++. Ngoại trừ việc hỗ trợ lưu dữ liệu dạng FIFO như queue thì deque cũng có thể được sử dụng dưới dạng LIFO (last in first out – vào sau ra trước) và cũng có thể truy nhập một phần tử bất kì. Và ngoài các chức năng của vector, deque còn hỗ trợ xóa và thêm phần tử ở đầu dãy trong O(1), thay vì O(n) như vector.

Vậy nhược điểm của deque với hai CTDL trên là gì? Thực ra là không có, nếu có thì chẳng qua là nó sinh sau nên không được phổ biến bằng hai CTDL trên mà thôi. Tất cả các bài cần sử dụng queue và vector (thậm chí cả stack) đề có thể sử dụng deque để thay thế.

#include <bits/stdc++.h>
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
	
}

Một số bài tập về deque:

https://www.hackerrank.com/challenges/deque-stl/problem
https://practice.geeksforgeeks.org/problems/c-stl-deque/1
https://practice.geeksforgeeks.org/problems/deque-implementations/1/

4.7/5 - (3 bình chọn)

Nhắc lại khái niệm hàng đợi

Định nghĩa hàng đợi

Tự xây dựng hàng đợi trong C++

Các cấu trúc hàng đợi trong C++ STL

Cấu trúc Queue

Cấu trúc Deque

Bài viết liên quan

Reader Interactions

Để lại một bình luận Hủy