Danh sách chờ

Danh sách chờ (tiếng Anh: queue) là một kiểu cấu trúc dữ liệu dùng để lưu trữ các đối tượng theo nguyên tắc FIFO (viết tắt từ tiếng Anh: First In First Out), tức là 'vào trước ra trước'

Trong danh sách chờ, các đối tượng có thể được thêm vào bất kỳ lúc nào, nhưng chỉ đối tượng được thêm đầu tiên mới có thể được lấy ra khỏi danh sách. Các thao tác thêm và lấy đối tượng khỏi danh sách được gọi lần lượt là 'enqueue' và 'dequeue'. Việc thêm đối tượng luôn thực hiện ở cuối danh sách và lấy đối tượng luôn từ đầu danh sách.

Trong lập trình, cấu trúc dữ liệu danh sách chờ có nhiều ứng dụng như: loại bỏ đệ quy, quản lý quá trình tìm kiếm theo chiều rộng và quay lui, tổ chức quản lý và phân phối tiến trình trong hệ điều hành, và quản lý bộ đệm bàn phím.

Cấu trúc dữ liệu danh sách chờ có thể được định nghĩa như sau: Danh sách chờ là một kiểu dữ liệu trừu tượng (ADT) tuyến tính. Giống như ngăn xếp, danh sách chờ hỗ trợ các thao tác:

• EnQueue(o): thêm đối tượng o vào cuối danh sách chờ.
• DeQueue(): lấy đối tượng từ đầu danh sách chờ và trả về giá trị của nó. Nếu danh sách chờ rỗng, sẽ xảy ra lỗi.
• IsEmpty(): kiểm tra xem danh sách chờ có rỗng hay không.
• Front(): trả về giá trị của phần tử ở đầu danh sách chờ mà không xóa nó. Nếu danh sách chờ rỗng, sẽ xảy ra lỗi.

Các thao tác thêm, lấy và xóa một phần tử phải được thực hiện từ các phía khác nhau của danh sách chờ, do đó hoạt động của danh sách chờ tuân theo nguyên tắc FIFO. Tương tự như ngăn xếp, danh sách chờ có thể được biểu diễn bằng cấu trúc mảng một chiều hoặc danh sách liên kết.

Cài đặt danh sách chờ

Có hai phương pháp để cài đặt danh sách chờ:

- Sử dụng mảng.

- Sử dụng danh sách liên kết.

1. Cài đặt danh sách chờ bằng mảng trong C (Cài đặt danh sách chờ bằng Mảng)

a) Mảng thông thường:

#include 
#include 

#define MAX 20

typedef  El_type;
typedef struct Queue
{
El_type el[MAX];
int front;
int rear;
} Queue;

Các thao tác: - Khởi tạo danh sách chờ (Khởi tạo Queue)

Eltype *initQ(Queue *q)
{
q = (Queue *)malloc(sizeof(Queue));
if(q!= NULL) 
{
 q->front = -1;
 q->rear = -1;
}
return q;
}

- Kiểm tra danh sách chờ có rỗng không? (Kiểm tra xem danh sách chờ có trống không)

int isEmpty(Queue *q)
{
return (q->front == -1);
}

- Kiểm tra xem danh sách chờ có đầy không? (Xem liệu danh sách chờ có đạt đến giới hạn không)

int isFull(Queue q)
{
return (q.rear - q.front + 1 == MAX);
}

- Thêm một phần tử vào danh sách chờ

void enQ(El_type new_el, Queue *q)
{
if(!isFull(*q))
{
 if(isEmpty(*q)) q->front = q->front + 1;
 q->rear = q->rear + 1;
 q->el[q->rear] = new_el;
}
else
 printf('Danh sách chờ đã đầy.
');
}

- Loại bỏ một phần tử từ danh sách chờ

void deQ(Queue *q)
{
if(!isEmpty(*q)) 
q->front = q->front + 1; 
else
printf('Danh sách chờ trống.
');
}

Những hạn chế:

- Mỗi lần xóa (deQ), phần không sử dụng của mảng sẽ gia tăng (do front tăng lên).

Giải pháp:

- Áp dụng mảng vòng (Circular Array).

b) Mảng vòng:

tương đương với:

- Khởi tạo danh sách chờ (Khởi tạo Queue)

Eltype *initQ(Queue *q)
{
q = (Queue *)malloc(sizeof(Queue));
if(q != NULL) 
{
 q->front = -1;
 q->rear = -1;
}
return q;
}

- Xác định danh sách chờ có trống không? (Kiểm tra xem danh sách chờ có rỗng không)

int empty_queue(queue q)
{
return q.front == -1;
}

- Xem liệu danh sách chờ có đầy không? (Kiểm tra xem danh sách chờ đã đầy chưa)

int full_queue(queue q)
{
return (q.rear - q.front + 1) % maxlength == 0;
}

- Thêm một phần tử vào danh sách chờ

void enqueue(elementtype x, queue *q)
{
if(!full_queue(*q))
{
if(empty_queue(*q)) q->front = 0;
q->rear = (q->rear + 1) % maxlength;
q->data[q->rear] = x;
}
else printf('Danh sách chờ đã đầy!');
}

- Xóa một phần tử khỏi danh sách chờ

void dequeue(queue *q)
{
if(!empty_queue(*q))
{
if(q->front == q->rear) makenull_queue(q);
else q->front = (q->front + 1) % maxlength;
}
else printf('Danh sách chờ trống!');
}

Hạn chế:

- Dù phương pháp sử dụng mảng vòng có thể tận dụng toàn bộ không gian của mảng được cấp phát, khi mảng đầy, không thể thêm phần tử mới vào danh sách chờ.

- Áp dụng danh sách liên kết.

2. Cài đặt danh sách chờ sử dụng Danh Sách Liên Kết: (Cài đặt danh sách chờ bằng con trỏ)

Khai báo cài đặt danh sách chờ bằng con trỏ

#include 
#include 
#include 

typedef int elementtype;
typedef struct node{
elementtype data;
node* next;
};
typedef node* position;
typedef struct queue{
position front, rear;
};

Các thao tác:

- Khởi tạo danh sách chờ (Khởi tạo Queue)

void makenull_queue(queue q)
{
q->front = (node)malloc(sizeof(node));
q->front->next = NULL;
q->rear = q->front;
}

- Xem danh sách chờ có trống không? (Kiểm tra xem danh sách chờ có rỗng không)

int empty_queue(queue q)
{
return (q.front == q.rear);
}

- Kiểm tra danh sách chờ có đầy không (không cần hàm này vì danh sách liên kết không bị đầy ^^!)

- Thêm một phần tử vào danh sách chờ

void enqueue(elementtype x, queue q)
{
q->rear->next = (node)malloc(sizeof(node));
q->rear = q->rear->next;
q->rear->data = x;
q->rear->next = NULL;
}

- Loại bỏ một phần tử từ danh sách chờ

void dequeue(queue *q)
{
position t;
t = q->front;
q->front = q->front->next;
free(t);
}

Ưu điểm: - Giải quyết vấn đề đầy mảng khi sử dụng mảng để cài đặt danh sách chờ.

Các ứng dụng của danh sách chờ

Danh sách chờ có thể được áp dụng trong nhiều tình huống:

• Sản xuất và tiêu thụ (sử dụng trong các hệ điều hành đa luồng).
• Bộ đệm (chẳng hạn như: Nhấn phím -> Bộ đệm -> Xử lý bởi CPU).
• Xử lý lệnh trong máy tính (áp dụng trong hệ điều hành, trình biên dịch), quản lý các tiến trình chờ được xử lý.