Bài giảng Cấu trúc hàng đợi (Queue)

Bài giảng "Cấu trúc hàng đợi - Queue" giới thiệu đến các bạn những nội dung về khái niệm hàng đợi, phép toán trên hàng đợi, cài đặt hàng đợi bằng mảng, cài đặt hàng đợi bằng dữ liệu liên kết,.. Với các bạn đang học chuyên ngành Công nghệ thông tin thì đây là tài liệu tham khảo hữu ích cho các bạn.
Nội dung trích xuất từ tài liệu:
Bài giảng 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ềmKhoa 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 front rear Mô hình lưu trữ: Khai báo: 0 1 2 3 …. maxlength-1 #define . . . MaxLength typedef ... ElementType; typedef struct{ ElementType Elements[MaxLength]; int front, rear; } Queue; Queue Q; 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: rear front 0 1 2 … maxlength-1 front rear Xử lý hàng tràn bằng mảng vòng: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