Queue là gì? Các hoạt động cơ bản và ứng dụng của cấu trúc dữ liệu hàng đợi

Từ việc quản lý tiến trình trong hệ điều hành, xử lý thông điệp trong các ứng dụng đa luồng, đến việc xử lý các yêu cầu từ người dùng trong các ứng dụng web, hàng đợi (queue) đóng vai trò quan trọng, giúp cho hệ thống phức tạp trở nên có tổ chức hơn. Vậy cụ thể thì queue là gì?

Queue là gì?

Giải đáp cho câu hỏi hàng đợi - queue là gì thì đây là một khái niệm cơ bản trong lập trình và khoa học máy tính, đóng vai trò quan trọng trong việc tổ chức hay điều phối dữ liệu. Khác với ngăn xếp (stack) - một cấu trúc dữ liệu khác thường được sử dụng - hàng đợi cho phép dữ liệu được thêm vào và loại bỏ theo nguyên tắc “First-In-First-Out” (FIFO). Điều này có nghĩa là phần tử được thêm vào trước sẽ được loại bỏ trước, phần tử thêm vào sau sẽ được loại bỏ sau, tạo ra quy trình tự nhiên giống như việc xếp hàng trong đời sống hàng ngày.

Ví dụ, khi bạn đứng trong hàng đợi tại quầy bán vé, người đến trước sẽ được phục vụ trước, sau đó mới đến lượt của những người đến sau. Tương tự thì trong lập trình, hàng đợi được sử dụng để quản lý các tác vụ hoặc yêu cầu theo thứ tự chúng được gửi đến. Nó có thể áp dụng trong nhiều tình huống khác nhau, từ xử lý thông điệp trong ứng dụng đa luồng đến quản lý tài nguyên trong hệ thống máy tính. Giờ thì ắt hẳn bạn đã hiểu queue là gì rồi chứ!

Các hoạt động cơ bản trên hàng đợi

Tiếp theo sau khi đã nắm rõ khái niệm queue là gì, chúng ta hãy cùng đi vào tìm hiểu các hoạt động cơ bản trên hàng đợi nhé.

Các hoạt động cơ bản trên hàng đợi là những bước quan trọng để quản lý, sử dụng cấu trúc dữ liệu này hiệu quả. Dưới đây là một số phân tích về các hoạt động này:

• enqueue(): Hoạt động này thêm một phần tử mới vào hàng đợi. Khi một phần tử mới được thêm vào, nó sẽ được đặt vào cuối của hàng đợi, là vị trí mà con trỏ rear đang trỏ tới, đảm bảo rằng phần tử mới được thêm vào hàng đợi theo đúng thứ tự của nó. Điều quan trọng là phải kiểm tra xem hàng đợi có đầy không, trước khi thêm phần tử mới vào để tránh trường hợp tràn hàng đợi.
• dequeue(): Hoạt động này xóa một phần tử khỏi đầu hàng đợi. Phần tử ở đầu hàng đợi được trỏ bởi con trỏ front, sẽ được loại bỏ khỏi hàng đợi. Nó giữ cho nguyên tắc FIFO (First-In-First-Out) được duy trì, tức là phần tử đầu tiên được thêm vào sẽ là phần tử đầu tiên được lấy ra. Trước khi thực hiện dequeue, bạn cần kiểm tra xem hàng đợi có trống không.
• Phương thức peek(): Phương thức này cho phép lấy ra phần tử ở đầu hàng đợi mà không xóa nó khỏi hàng đợi, cực hữu ích khi cần xem phần tử tiếp theo sẽ được lấy ra, mà không làm thay đổi trạng thái của hàng đợi.
• Phương thức isFull(): Phương thức này kiểm tra xem hàng đợi có đầy không. Nó giúp đảm bảo rằng không có thêm phần tử mới được thêm vào hàng đợi, khi nó đã đạt đến giới hạn dung lượng tối đa.
• Phương thức isEmpty(): Phương thức này kiểm tra xem hàng đợi có trống không, hỗ trợ khi cần biết xem hàng đợi có phần tử nào hay không, trước khi thực hiện các hoạt động dequeue hoặc peek.

Theo đó, cách thức hoạt động thông thường của hàng đợi đầu tiên sẽ là khởi tạo một hàng đợi mới, bằng cách cấp phát bộ nhớ đủ cho hàng đợi, khởi tạo các biến và con trỏ cần thiết như con trỏ front hay rear.

Trong quá trình sử dụng, các phần tử mới được thêm vào hàng đợi thông qua hoạt động enqueue. Phần tử này được đặt vào vị trí cuối cùng của hàng đợi (vị trí mà con trỏ rear đang trỏ tới), mở rộng hàng đợi theo hướng sau. Quá trình này đảm bảo rằng dữ liệu được duy trì theo thứ tự đến, khi cần thì các phần tử được lấy ra từ hàng đợi thông qua hoạt động dequeue. Phần tử ở đầu hàng đợi (được con trỏ front trỏ tới) sẽ được loại bỏ rồi trả về cho người dùng.

Cuối cùng, khi không còn cần thiết nữa, hàng đợi được giải phóng khỏi bộ nhớ để tránh lãng phí tài nguyên, bao gồm việc giải phóng bộ nhớ cấp phát cho hàng đợi cũng như các biến và con trỏ liên quan, giúp hệ thống hoạt động hiệu quả.

Các biến thể của hàng đợi

Hàng đợi hai đầu

Hàng đợi hai đầu hay còn gọi là Double-ended queue (DE queue), là một cải tiến của hàng đợi tiêu chuẩn, cho phép thêm hoặc xóa dữ liệu ở cả hai đầu của hàng đợi. Nó hỗ trợ việc quản lý dữ liệu trở nên linh hoạt, mở ra nhiều khả năng ứng dụng hơn.

Trong DE queue, bạn có thể thêm một phần tử vào cuối hoặc đầu của hàng đợi, cũng như xóa một phần tử từ đầu hoặc cuối của hàng đợi nhanh chóng. Nó đặc biệt hữu ích khi bạn cần thực hiện các thao tác như thêm và xóa dữ liệu từ cả hai phía của hàng đợi, mà không cần phải chờ nhiều thời gian.

Các hàm chức năng của DE queue bao gồm:

1. InsertAtBack(): Thêm một phần tử vào cuối của hàng đợi.
2. DeleteFromBack(): Xóa một phần tử từ cuối của hàng đợi.
3. InsertAtFront(): Thêm một phần tử vào đầu của hàng đợi.
4. DeleteAtFront(): Xóa một phần tử từ đầu của hàng đợi.
5. GetFront(): Lấy giá trị của phần tử ở đầu của hàng đợi.
6. GetRear(): Lấy giá trị của phần tử ở cuối của hàng đợi.

Thông qua các hàm này, việc thực hiện các hoạt động trên cả hai đầu của hàng đợi trở nên thuận tiện, tối ưu hóa quy trình xử lý dữ liệu và làm tăng tính ứng dụng của hàng đợi trong các tình huống phức tạp hơn.

Hàng đợi vòng

Hàng đợi vòng là một cải tiến của hàng đợi tiêu chuẩn, giải quyết vấn đề lãng phí không gian khi các vị trí bị xóa không được tái sử dụng. Trong hàng đợi vòng, khi một phần tử bị xóa khỏi hàng đợi, các vị trí đó sẽ được tái sử dụng khi thêm phần tử mới vào hàng đợi.

Cài đặt hàng đợi vòng đòi hỏi một biến bổ sung là “count’ để lưu số lượng phần tử đang có trong hàng đợi. Bên cạnh đó, chúng ta sử dụng các biến và hàm tương tự như trong hàng đợi tiêu chuẩn.

 Các hàm chức năng cơ bản cho hàng đợi vòng bao gồm:

1. Enqueue: Thêm một phần tử vào hàng đợi. Nếu hàng đợi đã đầy sẽ có thông báo “OverFlown”. Ngược lại, bạn thêm phần tử vào vị trí rear và điều chỉnh rear sử dụng toán tử % để đảm bảo hàng đợi là vòng tròn. Đồng thời tăng biến count lên 1.

2. Dequeue: Xóa phần tử khỏi hàng đợi. Nếu hàng đợi rỗng, thông báo “UnderFlown” sẽ xuất hiện. Ngược lại, bạn xóa phần tử từ vị trí front và điều chỉnh front sử dụng toán tử % để đảm bảo hàng đợi là vòng tròn. Đồng thời giảm biến count đi 1.

3. Front: Trả về giá trị của phần tử ở đầu hàng đợi.

4. Size: Trả về số lượng phần tử hiện có trong hàng đợi.

5. IsEmpty: Kiểm tra xem hàng đợi có rỗng hay không.

Cách để xây dựng hàng đợi

Xây dựng hàng đợi bằng mảng

Xây dựng hàng đợi bằng mảng là một phương pháp phổ biến và dễ hiểu. Tuy nhiên, cần lưu ý một số vấn đề để đảm bảo hiệu suất và tính linh hoạt của cấu trúc này.

• Chỉ số front và rear: Cần có hai chỉ số front và rear để theo dõi phần tử đầu và cuối của hàng đợi. Khởi tạo queue rỗng, ta gán front = 0 và rear = -1.
• Thêm và loại bỏ phần tử: Để thêm một phần tử vào queue, ta tăng rear lên 1 và gán giá trị phần tử đó vào phần tử tại chỉ số rear trong mảng. Để loại bỏ một phần tử, ta tăng front lên 1 và trả về giá trị của phần tử tại chỉ số front.
• Phần tử trong queue: Chỉ những phần tử có chỉ số từ front đến rear mới được coi là các phần tử trong queue. Các phần tử từ vị trí 0 đến front - 1 không thuộc queue và bị lãng phí.
• Kiểm tra trạng thái của hàng đợi: Khi front > rear, hàng đợi đang rỗng. Khi rear vượt quá giới hạn của mảng, hàng đợi tràn và không thể thêm phần tử mới vào nữa.

Dưới đây là một ví dụ cài đặt hàng đợi bằng mảng trong C++:

Kết quả:

Các phần tử trong Queue:5 21 10 99 101.

Loại bỏ phần tử khỏi hàng đợi:5 21.

Các phần tử trong Queue:10 99 101.

Xây dựng hàng đợi bằng danh sách liên kết

Khi xây dựng hàng đợi bằng danh sách liên kết, chúng ta có thể khắc phục các hạn chế của việc sử dụng mảng như lãng phí không gian, hạn chế về kích thước của hàng đợi. Dưới đây là cách cài đặt hàng đợi bằng danh sách liên kết trong C++:

Kết quả:

Các ứng dụng của hàng đợi

Hàng đợi là một cấu trúc dữ liệu quan trọng được sử dụng trong nhiều ứng dụng khác nhau. Dưới đây là một số ứng dụng phổ biến của hàng đợi:

• Thuật toán BFS (Breadth-First Search): Trong thuật toán BFS, hàng đợi được sử dụng để duyệt các đỉnh của đồ thị một cách theo chiều rộng. Cụ thể, các đỉnh được thăm được lưu trữ trong hàng đợi và được truy cập theo thứ tự FIFO (First-In-First-Out).
• Quản lý tài nguyên hệ thống: Trong hệ thống máy tính và mạng, hàng đợi thường được sử dụng để quản lý các tác vụ hoặc yêu cầu tới tài nguyên hệ thống. Ví dụ, các yêu cầu gửi từ các ứng dụng hay tiến trình có thể được xử lý theo thứ tự đến hàng đợi, được xử lý tuần tự.
• Quản lý hàng chờ: Trong các hệ thống dịch vụ như ngân hàng, bệnh viện hoặc nhà hàng, hàng đợi được sử dụng để quản lý việc chờ đợi của khách hàng. Mỗi khách hàng mới đến được thêm vào cuối hàng đợi, được phục vụ theo thứ tự đến lượt của họ.
• Sử dụng trong hệ thống điều phối tác vụ (Task Scheduling): Trong hệ thống điều phối tác vụ đa luồng hoặc đa tiến trình, hàng đợi có thể được sử dụng để lên lịch và quản lý các tác vụ hoặc tiến trình đang chờ để được thực thi.
• Thu thập dữ liệu và xử lý hàng đợi (Message Queuing): Trong hệ thống phân tán hay các ứng dụng đám mây, hàng đợi thường được sử dụng để truyền và xử lý các thông điệp, sự kiện giữa các thành phần khác nhau của hệ thống.

Tạm kết

Với những thông tin được cung cấp trong bài, hy vọng rằng bạn đã hiểu queue là gì và các hoạt động, ứng dụng của hàng đợi. Chúc bạn thành công!

Nếu bạn là một lập trình viên và đang cần laptop có hiệu suất làm việc ổn định thì hãy tham khảo qua tại gian hàng của FPT Shop nhé. Tại đây, FPT Shop cung cấp các sản phẩm công nghệ đa dạng về mẫu mã, có giá cả hợp lý. Bài viết xin giới thiệu tới bạn top các PC bán chạy nhất của cửa hàng:

• PC

Xem thêm:

• Tìm hiểu về Kafka: Các tính năng và khái niệm cần nắm rõ của nền tảng Apache Kafka
• Tìm hiểu về Java Message Service (JMS), thành phần và các khái niệm liên quan