Queue (Hàng đợi)
Hàng đợi (tiếng Anh: Queue) là cấu trúc dữ liệu đúng như cái tên nó mô tả, giống như hành động xếp hàng của chúng ta, nhưng không có chuyện ai đó chen vào giữa hàng hay chờ lâu quá bỏ hàng đi về.
Hàng đợi hoạt động theo nguyên tắc (FIFO) - First-In-First-Out, đến trước được phục vụ trước; Khác với Ngăn xếp theo nguyên tắc LIFO mà chúng ta đã tìm hiểu trước đó.
Hàng đợi (queue) là gì?
Như đã trình bày ở trên, hàng đợi là cấu trúc dữ liệu chỉ cho phép can thiệp ở 2 đầu, một đầu là thêm dữ liệu mới, thì đầu còn lại là lấy dữ liệu ra - đồng nghĩa là dữ liệu đã ở trong hàng đợi lâu nhất.
Như vậy, với cấu trúc dữ liệu hàng đợi, chúng có 2 phương thức để chúng ta thao tác:
- Thêm dữ liệu vào 1 đầu, tùy vào ngôn ngữ lập trình mà nó có tên gọi khác nhau, có thể là
push
,add
,enqueue
, ... nhưng chỉ là khác tên phương thức. - Lấy dữ liệu ra ở đầu còn lại, phương thức này cũng có nhiều cái tên như
pop
,remove
,dequeue
, ...
Quan sát ảnh phía trên, khi bạn:
- Thêm phần tử vào cuối hàng đợi, chỉ số có
rear
sẽ tăng lên. - Khi bạn xóa phần tử khỏi hàng đợi, chỉ số
front
cũng sẽ tăng lên. - Vì hàng đợi là dãy số liên tiếp từ
front
đếnrear
, nên để lấy size thì bạn sẽ tính khoảng cách giữarear
vàfront
.
📚 Lưu ý: Hàng đợi có 2 đầu và việc chọn đầu nào để thêm dữ liệu cũng được, khi đó đầu còn lại sẽ đảm nhiệm vai trò còn lại.
Tương tự Ngăn xếp, chúng ta cũng có các hàm hỗ trợ như
IsFull()
để kiểm tra hàng đợi đã đầyIsEmpty()
để kiểm tra hàng đợi chưa có dữ liệuSize()
để lấy kích thước hiện tại của hàng đợi
⚠️ Lý thuyết trên đây là hàng đợi phiên bản gốc, chúng ta cũng có biến thể hàng đợi 2 đầu, khi đó chức năng thêm và lấy dữ liệu đều có trên cả 2 đầu, sẽ tìm hiểu ở mục tiếp theo.
Cài đặt hàng đ ợi
Ở mục này, chúng ta sẽ thực hiện cài đặt các chức năng của Queue đã nói ở phần trước. Mục này tôi sẽ cùng các bạn đi cài đặt queue bằng mảng trong C/C++, bởi vì nó sẽ đơn giản hơn, giúp các bạn dễ hiểu hơn. Các cách cài đặt khác sẽ được trình bày ở phần sau.
Để cài đặt được Queue, chúng ta sẽ cần sử dụng các biến như sau:
queue[]
: Một mảng một chiều lưu dữ liệu của hàng đợi, sẽ khai báo trong hàm main sau.MAX_SIZE
: Số lượng phần tử tối đa có thể lưu trữ trong hàng đợifront
: Chỉ số của phần tử ở đang đầu queue. Nó sẽ là chỉ số của phần tử sẽ bị xóa ở lần tiếp theorear
: Chỉ số của phần tử tiếp theo sẽ được thêm vào cuối của queue
const int MAX_SIZE = 7;
int front = 0; // chỉ số đầu
int rear = 0; // chỉ số cuối
Bây giờ ta sẽ đi vào cài đặt từng chức năng của Hàng đợi.