Ngôn ngữ lập trình C - Chương 7 - Bài 3. Queue

Queue (Hàng đợi)- Là một hàng chờ đợi, xếp hàng (waiting line)- Là một cấu trúc dữ liệu trong đó cho phép sửdụng cả 2 phía: một phía để thêm và một phía đểlấy ra phần tử
Nội dung trích xuất từ tài liệu:
Ngôn ngữ lập trình C - Chương 7 - Bài 3. Queue 4/28/2010 Chương 7. Bài 3. Queue ĐỖ BÁ LÂM ViỆN CNTT&TT, TRƯỜNG ĐHBK HÀ NỘINội dung 1. Khái niệm queue 2. Xây dựng queue 2.1. Sử dụng mảng 2.2. Sử dụng danh sách liên kết 21. Khái niệm queue Queue (Hàng đợi)  Là một hàng chờ đợi, xếp hàng (waiting line)  Là một cấu trúc dữ liệu trong đó cho phép sử dụng cả 2 phía: một phía để thêm và một phía để lấy ra phần tử 3 1 4/28/2010 1. Khái niệm Queue Dữ liệu được thêm vào ở lối sau lối (rear), và lấy ra ở lối trước trước (front) Cấu trúc FIFO (First In First Out) – Vào trước ra trước Thao tác  enqueue(Element e)  Element dequeue() lối sau Các thao tác cơ bản của Queue enQueue: Thêm một phần tử vào Queue Data D Enqueue A B A B D rear rear front front Queue Queue Các thao tác cơ bản của Queue deQueue: Lấy một phần tử khỏi QueueData A Dequeue A B D B D rear rear front front Queue Queue 2 4/28/2010Ứng dụng của Queue Hàng đợi trong các phòng bán vé Truy nhập vào các thiết bị dùng chung tại văn phòng (ví dụ máy in) 7Ghi nhớ Queue được hình dung như một hàng đợi bao gồm nhiều nhiều người xếp hàng với 2 thao tác đưa vào và đẩy ra theo nguyên tắc:  Người nào vào trước sẽ được ra trước – FIFO (First In First Out)2. Xây dựng Queue Lưu trữ được các đối tượng dữ liệu Xây dựng 2 thao tác Push và Pop theo nguyên tắc FIFO Có hai cách cài đặt queue  Sử dụng mảng  Sử dụng danh sách liên kết 3 4/28/20102.1. Sử dụng mảng 0 1 2 MAX-1 ...F (Front) R (Rear) Biễu diễn Queue dưới dạng mảng Q Lưu trữ chỉ số phần tử lối trước và lối sau của Queue qua biến F và R Khởi tạo F=R=-1 Queue rỗng (empty) F = R = -1 Queue đầy (full) R=MAX-12.1. Sử dụng mảng Để thuận tiện định nghĩa cấu trúc Queue gồm mảng và 2 biến Front, Rear#define MAX 100typedef ... ElementType;typedef struct { ElementType Elements[MaxLength]; //Lưu trữ các chỉ số int Front, Rear;} Queue;Queue Q; 112.1. Sử dụng mảng Khởi tạo Queue  Front = -1  Rear = -1 Khi bổ sung thêm một phần tử vào Queue  Nếu Front=-1 thì gán Front=0  Rear tăng lên 1. Khi lấy ra một phần tử trong Queue  Nếu Front==Rear thì gán Front = Rear = -1  Ngược lại Front tăng lên 1 12 4 4/28/2010Enqueueint EnQueue(ElementType N){ if(Q.Rear==MAX-1) return 0; else{ if(Q.Front==-1) Q.Front=0; Q.Rear=Q.Rear+1; Q.Elements[Q.Rear]=X; return 1; } 13}Dequeueint DeQueue(ElementType *N){ if(Q.Front == -1) return 0; else{ *N = Q.Element[Q.Front]; if (Q.Front == Q.Rear){ Q.Front = -1; Q.Rear = -1; }else Q.Front=Q.Front+1; return 1; //Dequeue thanh cong }}2.1. Sử dụng mảng Nhược điểm của cách tổ chức lưu trữ này  Hiện tượng ĐẦY (Full) vẫn xảy ra dù mảng Q vẫn còn chỗ nhưng R = MAX-1 0 1 2 MAX-1 ... F (Front) R (Rear) 15 5 4/28/2010Cải tiến EMPTY QUEUE [2] [1] [2] [1] J2 J3 [0] [3] [0] [3] J1 [5] [4] [5] [4] front = -1 front = 0 rear = -1 rear = 2Cải tiến [1] [2] [1] [2] ...