Cấu trúc hàng đợi (queue)

CẤU TRÚC HÀNG ĐỢI (QUEUE) Bộ môn Công nghệ phần mềm Khoa Công nghệ thông tin & Truyền thông Đại học Cần Thơ KHÁI NIỆM HÀNG ĐỢI
Là một dạng danh sách ñặc biệt mà việc thêm phần tử chỉ thực hiện tại một ñầu, gọi là cuối hàng; việc loại bỏ phần tử thực hiện ở ñầu kia, gọi là ñầu hàng.
Làm việc theo nguyên tắc FIFO(First In First Out). PHÉP TOÁN TRÊN HÀNG ĐỢI
MAKENULL_QUEUE(Q): khởi tạo hàng ñợi rỗng.
EMPTY_QUEUE(Q): kiểm tra hàng ñợi rỗng.
FULL_QUEUE(Q): kiểm tra hàng ñợi ñầy.
FRONT(Q): nội dung phần tử ñầu hàng.
ENQUEUE(X,Q): thêm phần tử X vào cuối hàng ñợi Q.
DEQUEUE(Q): xóa phần tử ở ñầu hàng ñợi. CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG
Mô hình lưu trữ:
Khai báo: #define . . . MaxLength typedef ... ElementType; typedef struct{ ElementType Elements[MaxLength]; int front, rear; } Queue; Queue Q; front rear 0 1 2 3 . maxlength-1 CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG
Hàng ñầy: front rear 0 1 2 3 . maxlength-1
Hàng tràn: front rear 0 1 2 3 . maxlength-1  Sử dụng bộ nhớ không hiệu quả. Phải xử lý hàng tràn. CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG
Xử lý hàng tràn bằng mảng tịnh tiến: front rear 0 1 2 maxlength-1
Xử lý hàng tràn bằng mảng vòng: front rear CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG
Khởi tạo hàng rỗng void MakeNull_Queue(Queue *Q){ Q->Front = -1; Q->Rear = -1; } CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG
Kiểm tra hàng rỗng int Empty_Queue(Queue Q){ return Q.Front == -1; } CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG
Kiểm tra hàng ñầy int Full_Queue(Queue Q){ return (Q.Rear-Q.Front+1) % MaxLength == 0; } CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG
Nội dung phần tử ñầu hàng: ElementType Front(Queue Q){ if (Empty_Queue (Q)) printf(“Loi ! Hang doi rong”); else return Q.Element[Q.Front]; } CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG
Xóa phần tử ñầu hàng: CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG
Xóa phần tử ñầu hàng: void DeQueue(Queue *Q){ if (Empty_Queue(*Q)) printf("Loi: Hang rong!"); else if (Q->Front == Q->Rear) MakeNull_Queue(Q); else Q->Front=(Q->Front+1) % MaxLength; } CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG
Thêm phần tử vào cuối hàng: CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG
Thêm phần tử vào cuối hàng: void EnQueue(ElementType X,Queue *Q){ if (Full_Queue(*Q)) printf("Loi: Hang day!"); else{ if (Empty_Queue(*Q)) Q->Front = 0; Q->Rear = (Q->Rear+1) % MaxLength; Q->Elements[Q->Rear] = X; } } CÀI ĐẶT HÀNG ĐỢI BẰNG DSLK front rear