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

0
762
83 / 100
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”.

Hàng đợi trong C++ | Sử dụng hàng đợi trong thư viện STL 1
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++

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() hay back() 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:

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ế.

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/
Into the mirror. ICPC PTIT. facebook.com/terrorblade7227.
Subscribe
Notify of
guest
0 Bình luận
Inline Feedbacks
View all comments