1.Cấu trúc dữ liệu hàng đợi queue là gì?

Cấu trúc dữ liệu hàng đợi queue là một cấu trúc làm việc theo cơ chế FIFO (First In First Out), cấu trúc hàng đợi được sử dụng để chứa các đội tượng theo cách “Vào trước thì ra trước”.

Nghĩa là các thành phần được thêm vào đầu hàng đợi sẽ được xử lý trước và các thành phần thêm vào sau thì phải đợi để được xử lý sau. Có thể nhận thấy rằng cấu trúc hàng đợi là hoàn toàn trái ngược lại với cấu trúc dữ liệu ngăn xếp stack (với cơ chế LIFO)!

Một số thao tác chính khi làm việc với cấu trúc dữ liệu hàng đợi queue:

  • Add(q,x): thêm phần tử x vào hàng đợi queue
  • Remove(q): lấy phần tử (hay đối tượng) được thêm ở đầu queue ra khỏi hàng đợi và trả về giá trị của nó, đồng thời thực hiện xóa đi phần tử đó.

Trên đây là 2 thao tác cơ bản khi thao tác với hàng đợi, tuy nhiên vẫn còn nhiều thao tác cài đặt nữa đối với hàng đợi và sẽ được nêu ra chi tiết ở những bài sau!

2.Cấu trúc hàng đợi queue với mảng

Ta có thể biểu diễn cấu trúc hàng đợi queue với mảng một chiều, khi đó ta cần khai báo một số thông tin cho mảng queue này:

Đầu tiên, là hằng số N cho biết kích thước (số phần tử tối đa) của mảng hàng đợi đó.

Tiếp theo, ta cần khai báo hai biến có kiểu nguyên đó là: int front; int rear; cho biết chỉ số của đầu và cuối của hàng đợi.

Đoạn code dưới đây được sử dụng khai báo một hàng đợi bằng mảng int A[MAX] và có số lượng phần tử là MAX = 100

#define MAX 100
typedef struct queue
{
    int A[MAX];
    int front, rear;
};
typedef struct queue QUEUE;

Ở trên tôi sử dụng int A[MAX] để chỉ ra rằng kiểu dữ liệu mà hàng đợi này đang lưu trữ là kiểu số nguyên int. Tùy vào một số bài toán khác nhau mà ta có thể thay đổi sang kiểu dữ liệu khác sao cho phù hợp.

Trong những bài sau tôi sẽ đi chi tiết hơn về việc cài đặt hàng đợi queue bằng mảng (Phần này chỉ mang tính chất giới thiệu).

3.Cấu trúc hàng đợi queue với danh sách liên kết

Giống như việc cài đặt cấu trúc stack với danh sách liên kết thì ta hoàn toàn có thể sử dụng danh sách liên kết để cài đặt hàng đợi queue. Việc cài đặt queue bằng danh sách liên kết sẽ giúp khắc phục được một số hạn chế của việc cài đặt bằng mảng gây ra như thừa (hoặc thiếu ) bộ nhớ.

Khi cài đặt hàng đợi queue với danh sách liên kết ta phải đảm bảo rằng các phần tử trong queue chính là các node, vì vậy trước tiên ta cần đi định nghĩa một node gồm hai thành phần đó là: thành phần dữ liệu con trỏ next. Đoạn code dưới đây khai báo một node chứa thành phần dữ liệu là kiểu số nguyên int data; và con trỏ node *next;

struct node{
    int data;
    node *next;
};
typedef struct node NODE;

Tiếp theo là việc ta cần khai báo một hàng đợi queue với 2 thành phần đó là NODE *front;NODE *rear;

struct queue{
    NODE *front;
    NODE *rear;
};  
typedef struct queue QUEUE;

Ở trên ta mới chỉ dừng lại ở việc khai báo một node và khai báo một hàng đợi. Việc cài đặt hoàn chỉnh cấu trúc hàng đợi queue với danh sách liên kết sẽ được đi chi tiết hơn ở những bài sau. Mời bạn đọc chú ý đón xem!

4.Một số ứng dụng của cấu trúc dữ liệu hàng đợi queue

Một số ứng dụng của hàng đợi trong tin học:

  • Khử đệ quy
  • Bài toán ‘sản xuất và tiêu thụ’ (ứng dụng trong các hệ điều hành song song).
  • Tổ chức lưu vết các quá trình tìm kiếm theo chiều rộng và quay lui, vét cạn
  • Tổ chức quản lý và phân phối tiến trình trong các hệ điều hành
  • Tổ chức bộ đệm bàn phím.