Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue - Hàng đợi Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ dữ liệu nữa đó chính là hàng đợi Queue. Đây là một cấu trúc rất phổ biến trong lập trình và nó rất quen thuộc với chúng ta.

Chúng ta sẽ cùng nhau tìm hiểu về hàng đợi Queue là gì? Các thao tác cơ bản trên hàng đợi Queue cũng như các cách cài đặt nó.

1. Hàng đợi Queue là gì?

Hàng đợi Queue là một cấu trúc trừu tượng. Nó hoạt động dựa trên cơ chế FIFO (first in fisrt out), nghĩa là phần tử nào và trước thì phần tử đó sẽ ra trước.

Ví dụ như lúc nhỏ khi chúng ta xếp hàng vào lớp, thì người đứng ở vị trí đầu tiên là người vào trước, tiếp đến lần lượt các người xếp ở phía sau. Một cấu trúc lưu trữ hoạt động theo cơ chế như vậy được goi là hàng đợi Queue.

Để năm rõ hơn về hàng đợi Queue, bây giờ chúng ta sẽ tìm hiểu về các thao tác cơ bản trong hàng đợi nhé.

2. Các thao tác cơ bản trong Queue

Về cơ bản thì hàng đợi Queue cũng là một cấu trúc lưu trữ tương tự như Stack, chỉ có điều cơ chế hoạt động của nó ngược lại với Stack, vì vậy trong Queue cũng có các hàm cơ bản tương tư như Stack:

• Hàm khởi tạo Queue rỗng.
• Hàm kiểm tra Queue rỗng.
• Hàm trả về phần tử đầu tiên của Queue.
• Hàm thêm phần tử vào cuối Queue.
• Hàm xóa phần tử đầu tiên của Queue.

Những hàm này chúng ta sẽ được học ở những bài tiếp theo.

Trên đây là một số hàm cơ bản khi làm việc với Queue, ngoài ra còn một số hàm khác phụ thuộc vào bài toán yêu cầu, vì vậy các bạn chỉ cần nắm rõ các hàm này để có thể cài đặt một cấu trúc hàng đợi Queue.

3. Các cách cài đặt Queue

Để cài đặt Queue ta cũng sẽ có hai cách cài đặt cơ bản, đó chính là:

• Cài đặt Queue bằng mảng một chiều.
• Cài đặt Queue bằng danh sách liên kết.

Tuy nhiên khi làm việc với các bài toán, ta ưu tiên chọn cách sử dụng danh sách liên kết để cài đặt hàng đợi, vì trong danh sách liên kết có các ưu điểm như lấy phần tử đầu phần tử cuối, thêm phần tử đầu phần tử cuối.

Nếu chúng ta sử dụng mảng để cài đặt cho hàng đợi Queue, thì khi thực hiện insertList và deleteList tốn rất nhiều thời gian. Trong khi đó nếu sử dụng danh sách liên kết đơn dể cài đặt ta chỉ cần sử dụng con trỏ pHead và pTail là có thể thực hiện nó một cách đơn giản.

4. Kết luận

Như vậy là chúng ta đã tìm hiểu xong về hàng đợi Queue là gì? Các thao tác cơ bản trên hàng đợi Queue cũng như các cách có thể cài đặt nó. Ở bài tiếp theo mình sẽ đi chi tiết vào từng cách cài đặt, kèm theo ví dụ cụ thể để các bạn có thể nắm rõ hơn, hãy chú ý theo dõi nhé !!!