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 chúng tôi tìm hiểu chi tiết về nó qua bài viết sau nhé!
FPT Aptech đang tuyển sinh 50 chỉ tiêu cuối cùng ngành Lập Trình Viên Quốc Tế với ưu đãi giảm 50% học phí cho 40 thí sinh đăng ký sớm nhất trên toàn quốc.
Đăng ký ngay
Tóm Tắt
Chức năng của Queue là gì?
Một cấu trúc Queue hoàn hảo sẽ có những tính năng sau :
-
Dequeue: Mục đích là lấy ra phần tử đầu Queue.
- 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 = 1 e5 ; / / Kích cỡ lớn nhất của hàng đợi, biến này hoàn toàn có thể đổi khác tùy vào bạn
template
{
T base [ MAX ] ; / / Mảng base tàng 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 thành phần vào đầu hàng đợi
{
a [ size ] = x ; / / Đặt x vào cuối hàng đợi
size + + ; / / Tăng size hàng đợi lên 1
}
void Dequeue ( ) / / Loại bỏ thành phần ở đầu hàng đợi
{
+ + a ; / / Loại bỏ thành phần ở đầ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ề thành phần ở đầu hàng đợi
{
return a [ 0 ] ;
}
} ;
int main ( ) / / Chương trình chạy mẫu
{
Queue
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ỏ thành phần ở đầ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 thành phần ở đầu hàng đợi, lúc này đang là 2
}
Trong ngôn ngữ C++ STL cấu trúc hàng đợi – Queue là gì?
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 của Queue.
- 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 Queue, 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 Queue, 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
std::cout << a.empty() << ‘\n’; // Lúc này hàng đợi đang rỗng, nên sẽ in ra 1
Xem thêm: Tg Trong Toán Học Là Gì
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 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 thành phần ở đầu hàng đợi, lúc này là 1
std :: cout < < a.back ( ) < < ‘ \ n ’ ; / / In ra thành phần ở cuối hàng đợi, lúc này là 2
a.pop ( ) ; / / Loại bỏ thành phần ở đầ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 cỡ hàng đợi hiện tại, lúc này là 1
std :: cout < < a.front ( ) < < ‘ \ n ’ ; / / In ra thành phần ở đầu hàng đợi, lúc này là 2
std::queue
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 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 thành phần ở đầu hàng đợi, lúc này là { 0, 1 }
std::queue
b.swap ( c ) ; / / Hoán đổi tài 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 tài 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 của Queue đã 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
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 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 thành phần ở đầu hàng đợi, lúc này là 4 std :: cout < < a.back ( ) < < ‘ \ n ’ ; / / In ra thành phần ở 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 thông 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 những 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 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ỏ thành phần ở đầ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 cỡ hàng đợi hiện tại, lúc này là 4 std :: cout < < a.front ( ) < < ‘ \ n ’ ; / / In ra thành phần ở đầu hàng đợi, lúc này là 2 a. pop_back ( ) ; / / Loại bỏ thành phần ở 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 thành phần ở 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 thành phần 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ổng thể những thành phần 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 tài liệu mà toàn bộ 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 .
Source: https://final-blade.com
Category : Kiến thức Internet
