Bài giảng Hàng đợi (Queue)

Bài 6: Hàng đợi (Queue) 1. Định nghĩa kiểu dữ liệu trừu tượng quan trọng khác được xây dựng trên cở sở mô hình dữ liệu danh sách. Hàng là một danh sách với hai phép toán quan trọng nhất là thêm một phần tử mới vào một đầu danh sách (đầu này được gọi là cuối hàng) và loại phần tử khỏi danh sách ở một đầu khác (đầu này gọi là đầu hàng). hàng người chờ đợi được phục vụ (chờ mua vé tàu, chẳng hạn). Người ta chỉ có thể đi vào hàng ở cuối hàng, người được phục vụ và ra khỏi hàng là người ở đầu hàng tức là ai vào hàng trước sẽ được phục vụ trước. hàng còn được gọi là danh sách FIFO (viết tắt của First In First Out, nghĩa là, ai vào đầu tiên ra đầu tiên). 2. Các phép toán 1. Khởi tạo hàng rỗng. void Initialize (Queue *Q) ; 2. Kiểm tra hàng rỗng bool Empty (Queue *Q) Emty nhận giá trị true nếu Q rỗng và false nếu không 3. Kiểm tra hàng đầy bool Full (Queue Q) Full nhận giá trị true nếu Q đầy và false nếu không 4. Thêm một phần tử mới x vào cuối hàng void AddQueue (Item x, Queue *Q) 5. Loại phần tử ở đầu hàng, giá trị của phần tử này được lưu vào x. void DeleteQueue (Queue *Q, Item *x) 3. Cài đặt hàng đợi bởi mảng #define max N struct QUEUE { int rear, front; Item element[max]; } typedef struct QUEUE; Trong cách cài đặt này, hàng rỗng nếu rear = 0 và hàng đầy nếu rear = max. 3. Cài đặt hàng đợi… void Initialize (Queue Q) { Q.front = 1 ; Q.rear = 0 ; } Bool Empty (Queue Q) { if Q.rear == 0 Empty = true; else Emty = false } bool Full (Queue Q) { if Q.rear == max Full = true else Full = false } void AddQueue (Item x, Queue Q, bool *ok) { if Q.rear == max OK = false else { Q.rear = Q.rear + 1 Q.element [rear] = x ; OK = true } } void DeleteQueue (Queue Q, Item *x, bool *ok) { if Q.rear == 0 OK = false else { x = Q.element [front] ; if Q.front == rear { Q.front = 1 ; Q.rear = 0 } else Q.front = Q.front + 1 ; OK = true } } 3. Cài đặt hàng đợi… cài đặt hàng bởi mảng với hai chỉ số front, rear có điểm yếu lớn: Nếu phép loại bỏ không thường xuyên làm cho hàng rỗng, chỉ số front và rear sẽ tăng liên tục, nhanh chóng vượt quá cỡ của mảng. Hàng sẽ trở thành đầy, mặc dầu các vị trí trống trong mảng có thể vẫn còn nhiều khắc phục bằng cách sau: chỉ sử dụng một chỉ số rear để chỉ cuối hàng, phần tử đầu hàng luôn luôn được xem là thành phần đầu tiên của mảng ~ front = 1. Tuy nhiên cách cài đặt này không thuận tiện cho phép toán loại phần tử đầu hàng -> phải dồn tất cả các phần tử còn lại của hàng lên một vị trí. 4. Cài đặt hàng bởi mảng vòng tròn. Trong trường hợp số phần tử trong hàng không bao giờ vượt quá một số cố định N tốt nhất là biểu diễn hàng bởi mảng vòng tròn. mảng với chỉ số chạy trong miền 1... max, với mọi i = 1,2,..., max - 1, thành phần thứ i của mảng đi trước thành phần thứ i + 1 còn thành phần thứ max đi trước thành phần đầu tiên Khi biểu diễn đưa thêm vào biến count để đếm số phần tử trong hàng. Chúng ta có khai báo sau. #define max N struct QUEUE { Int count; int rear, front; Item element[max]; } typedef struct QUEUE; Trong cách cài đặt này, điều kiện để hàng Q rỗng là Q.count = 0 và nó đầy nếu Q.count = max. void AddQueue (Item x, Queue Q, bool OK) { with Q do if count == max ok = false else { if rear ==max rear = 1 else rear = rear + 1 ; element [rear] = x ; count = count + 1 ; Ok = true } } void DeleteQueue (Queue Q; Item *x, bool *ok) { with Q do if count == 0 Ok = false else { x = element [front] ; if front == rear { front = 1 ; rear = 0 } else if front == max front = 1 else front = front + 1 ; count = count - 1 ; Ok = true ; } } 5. Cài đặt hàng bởi danh sách liên kết. struct NODE { Item info; struct NODE *next; } typedef struct NODE; struct QUE { NODE *front; NODE *rear; } typedef struct QUE; typedef QUE *QUEUE; void Initialize (QUEUE Q) ; { Q-> front = null } bool Empty (QUEUE Q) { if Q->front = null Empty = true else Emty = false } bool Full (QUEUE Q) { Full = false } void AddQueue (Item x, QUEUE Q, bool *ok) { NODE *P; P= (NODE)malloc(sizeof(NODE)); P-> infor = X ; P-> next = null ; with Q do if front = nil { front = P ; rear = P ; } else{ rear-> next = P ; rear = P } Ok = true; } void DeleteQueue (Queue Q, Item *x, bool *ok) { NODE *P; with Q do if front == null ok = false else { P = front ; x = front->infor ; front = front->next ; Ok = true; free(P); } }