Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 13: Hàng đợi - Queues - Ngô Hữu Phước

Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com Cấu trúc dữ liệu và giải thuật Bài 13. Hàng đợi - Queues @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University1 Bài 13. Hàng đợi - Queues Nội dung: 13.1. Khái niệm về hàng đợi. 13.2. Xây dựng và sử dụng Queue. 13.3. Ví dụ về hàng đợi. Tham khảo: 1. Data structures and Algorithms Stacks.htm, Kyle Loudon Mastering Algorithms, 2. Chapter 6 Stacks and Queues, Elliz Horowitz – Fundamentals of Data Structures. 3. Chapter 3 Stacks and Queues, Deshpande Kakle – C and Data Structures. 4. Bài giảng TS Nguyễn Nam Hồng. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University2 13.1. Khái niệm về hàng đợi (1/8) @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University3 13.1. Khái niệm về hàng đợi (2/8)  Trong ứng dụng máy tính, định nghĩa CTDL hàng đợi là danh sách, trong đó việc thêm một phần tử được thực hiện ở đầu một danh sách (cuối hàng đợi) và việc lấy ra một phần tử được thực hiện ở cuối danh sách (đầu hàng).  Hàng đợi còn được gọi là danh sách FIFO (First In First Out). @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University4 Ví dụ về hàng đợi 13.1. Khái niệm về hàng đợi (3/8)  Đối với hàng đợi, số lượng ứng dụng có nhiều hơn cả ngăn xếp.  Ví dụ như máy tính thực hiện nhiệm vụ, có nhiều hàng đợi được sử dụng:  hàng đợi máy in,  việc truy xuất đĩa,  sử dụng CPU.  chuyển đổi từ Infix sang Prefix.  Phần tử đầu hàng đợi được phục vụ trước, phần tử này thường gọi là front hay head. Phần tử mới thêm vào được gọi là rear hay tail. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University5 13.1. Khái niệm về hàng đợi (4/8) Định nghĩa: Một hàng đợi các phần tử kiểu T là một chuỗi nối tiếp các phần tử của T và kèm theo một số tác vụ sau: 1. Tạo mới một đối tượng hàng rỗng. 2. Thêm một phần tử mới vào hàng, giả sử hàng đợi chưa đầy (phần tử dữ liệu mới luôn được thêm vào cuối hàng). 3. Loại một phần tử ra khỏi hàng, giả sử hàng chưa rỗng (phần tử bị loại là phần tử tại đầu hàng, thường là phần tử vừa được xử lý xong). 4. Xem phần tử tại đầu hàng (phần tử sắp được xử lý). @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University6 13.1. Khái niệm về hàng đợi (5/8) @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University7 Hoạt động của hàng đợi 13.1. Khái niệm về hàng đợi (3/8) Xây dựng Queue:  Thành phần dữ liệu cho Queue:  MaxEntry: Kích thước của Queue.  QueueEntry: Kiểu dữ liệu dành cho mỗi phần tử trong Queue.  Một số phương thức cơ bản của Queue:  QueueClassL();  int isEmpty();  int isFull();  int Dequeue(QueueEntry *value);  int Enqueue(QueueEntry value);  int Peek(QueueEntry *value);  void makeEmpty(); @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University8 13.1. Khái niệm về hàng đợi (4/8) Khai báo lớp Queue (dạng tuyến tính): template // Lớp mẫu cho kiểu dữ liệu của Queue class QueueClassL{ // Định nghĩa tên lớp public: QueueClassL(); // Hàm tạo của lớp, khởi tạo thông tin cho Queue int isEmpty(); // Queue rỗng → 1, ngược lại → 0 int isFull(); // Queue đầy → 1, ngược lại → 0 int Dequeue(QueueEntry *value); // Lấy 1 phần tử Queue int Enqueue(QueueEntry value); // Thêm 1 phần tử vào Queue int Peek(QueueEntry *value); // Xem giá trị tại đầu của Queue void makeEmpty(); // Làm rỗng Queue private: int front, rear; // front: đầu Queue, rear: cuối Queue QueueEntry entry[MaxEntry]; // Mảng lưu thông tin của Queue }; @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University9 13.1. Khái niệm về hàng đợi (5/8) Một số phương thức của Queue: template QueueClassL ::QueueClassL(void) { front=rear=-1; } template int QueueClassL ::isEmpty() { if(front==rear) return 1; else return 0; } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University10 13.1. Khái niệm về hàng đợi (6/8) Một số phương thức của Queue: template int QueueClassL::isFull() { if(rear==MaxEntry-1) return 1; else return 0; } template int QueueClassL ::Dequeue(QueueEntry *value) { if(!isEmpty()) { front++; *value = entry[front]; return 1; } else return 0; } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University11 13.1. Khái niệm về hàng đợi (7/8) Một số phương thức của Queue: template int QueueClassL ::Enqueue(QueueEntry value) { if(!isFull()) { rear++; entry[rear]=value; return 1; } else return 0; } template int QueueClassL ::Peek(QueueEntry *value) { if(!isEmpty() && front!=-1) { *value = entry[front]; return 1; } else return 0; } template void QueueClassL ::makeEmpty() { front=rear=-1; } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University12 13.1. Khái niệm về hàng đợi (8/8) Một số dạng của hàng đợi:  Hàng đợi tuyến tính - Linear Queues Tổ chức hàng đợi theo nghĩa thông thường.  Hàng đợi vòng - Circular Queues Giải quyết việc thiếu bộ nhớ khi sử dụng hàng đợi.  Hàng đợi ưu tiên - Priority Queues Mỗi phần tử có kết hợp thêm thông tin về độ ưu tiên. Khi chương trình cần lấy một phần tử khỏi hàng đợi, nó sẽ xét những phần tử có độ ưu tiên cao trước.  Multi-Headed Queues. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University13 13.2. Xây dựng và sử dụng Queue (1/7) #include #include #include typedef int QueueEntry; #define MaxEntry 10 #include "QueueClass.h“ void menu() { printf("1. Nhap vao QUEUE\n"); printf("2. Lay ra khoi QUEUE\n"); printf("3. Gia tri tren dinh QUEUE la gi?\n"); printf("4. QUEUE rong?\n"); printf("5. QUEUE day?\n"); printf("6. Lam rong QUEUE!\n"); printf("7. Thoat\n"); } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University14 void main() { QueueClassL queue; QueueEntry value; int key; char ch; do { menu(); printf("Moi lua chon: "); scanf("%d",&key); switch (key) { case 1: printf("Nhap phan tu can dua vao QUEUE\n"); scanf("%d",&value); if(queue.Enqueue(value)) printf("Da them vao Queue\n"); Với Queue đã được khai báo, xây dựng chương trình sử dụng Queue 13.2. Xây dựng và sử dụng Queue (2/7) else printf("Queue da day!\n"); break; case 2: printf("Lay mot phan tu khoi QUEUE\n"); if(queue.Dequeue(&value)) printf("Gia tri lay ra: %d\n",value); else printf("Queue rong\n"); break; case 3: if(queue.Peek(&value)) printf("Gia tri tai front QUEUE: %d\n",value); else printf("Queue rong\n"); break; case 4: if(queue.isEmpty()==1) printf("QUEUE rong\n"); else @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University15 printf("QUEUE van co gia tri\n"); break; case 5: if(queue.isFull()==1) printf("QUEUE day\n"); else printf("QUEUE chua day\n"); break; case 6: printf("Lam rong QUEUE? Co chac khong? (C/K)"); fflush(stdin); scanf("%c",&ch); if(ch=='c' || ch=='C') queue.makeEmpty(); break; } } while (key!=7); } 13.2. Xây dựng và sử dụng Queue (3/7) Một số nhận xét cho dạng Queue nói trên:  Đáp ứng được các tiêu chí về Queue.  Tuy nhiên, với kích thước Queue là 10 (theo ví dụ) chỉ có thể thêm tối 10 phần tử.  Ngoài ra, vì front chỉ tăng, do đó, trong Queue vẫn còn ô nhớ nhưng không sử dụng được. Giải quyết vấn đề trên:  Sử dụng Queue có dạng vòng.  Khi đó, làm thế nào để biết Queue đã đầy hay rỗng?  Giá trị khởi tạo cho front và rear như thế nào?  Xây dựng Queue như thế nào? @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University16 13.2. Xây dựng và sử dụng Queue (4/7) @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University17 Ví dụ về Queue có dạng vòng 13.2. Xây dựng và sử dụng Queue (5/7) @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University18 1 0 12 11 10 After 7 enqueues front rear 1 0 12 11 10 After 5 dequeues front rear 1 0 12 11 10 After 8 more enqueues front rear Hoạt động của Queue 13.2. Xây dựng và sử dụng Queue (6/7) template class QueueClassC{ public: QueueClassC(); int isEmpty(); int isFull(); int Dequeue(QueueEntry *value); int Enqueue(QueueEntry value); int Peek(QueueEntry *value); void makeEmpty(); private: int front, rear; QueueEntry entry[MaxEntry]; }; @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University19 template QueueClassC::QueueClassC(void) { front = 0; rear = 0; } template int QueueClassC::isEmpty() { if(front= =rear) return 1; else return 0; } Xây dựng hàng đợi vòng 13.2. Xây dựng và sử dụng Queue (7/7) template int QueueClassC::isFull() { if((rear+1)%MaxEntry== front) return 1; else return 0; } template int QueueClassC::Dequeue(QueueEntry *value) { if(!isEmpty()) { front = (front+1)%MaxEntry; *value = entry[front]; return 1; } else return 0; } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University20 template int QueueClassC::Enqueue(QueueEntry value) { if(!isFull()) { rear = (rear+1) % MaxEntry; entry[rear]=value; return 1; } else return 0; } template int QueueClassC::Peek(QueueEntry *value) { if(!isEmpty()) { *value = entry[(front+1)%MaxEntry]; return 1; } else return 0; } template void QueueClassC::makeEmpty() { front=rear=0; } 13.3. Ví dụ về hàng đợi (1/5) Palindromes (1/4)  Khái niệm: Một chuỗi được gọi là Palindrome nếu như đọc xuôi giống đọc ngược.  Bài toán: Cho trước một chuỗi, kiểm tra xem chuỗi đó có phải là chuỗi palindrome hay không?  Ví dụ về chuỗi palindrome: Able was I ere I saw Elba  Giải pháp:  Để tránh ảnh hưởng tới chuỗi ban đầu, đọc chuỗi nói trên vào stack và queue.  So sánh từng phần tử của stack và queue, nếu giống nhau từng cặp thì đó là chuỗi Palindrome, ngược lại thì chuỗi trên không phải là chuỗi Palindrome. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University21 13.3. Ví dụ về hàng đợi (2/5) ... typedef char StackEntry; typedef char QueueEntry; #define MaxEntry 100 #include "StackClass.h" #include "QueueClass.h" ... int palindrome(char* sstring); void main() { char sstring[100]; printf("Nhap mot xau ky tu: "); gets(sstring); int vt = palindrome(sstring); if(!vt) printf("Chuoi da nhap la chuoi Palindrome!"); else printf(“Ko phai Palindrome!, co %d cap ky tu khong khop!",vt/2); getch(); } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University22 int palindrome(char* sstring) { StackClass stack; QueueClassC queue; for(int i=0;i<strlen(sstring);i++) { stack.push(sstring[i]); queue.Enqueue(sstring[i]); } int kt=0; while(!queue.isEmpty() && !stack.isEmpty()) { StackEntry a; QueueEntry b; stack.pop(&a); queue.Dequeue(&b); if(a!=b) kt++; } return kt; } Kiểm tra chuỗi có phải là chuỗi Palindrome hay không? 13.3. Ví dụ về hàng đợi (3/5) Tổ chức dữ liệu hợp lý - Demerging (1/4) Bài toán: Xem xét bài toán sau:  Giả sử, với một hệ thống quản lý nhân sự. Các bản ghi được lưu trên file.  Mỗi bản ghi gồm các trường: Họ tên, giới tính, ngày tháng năm sinh, ...  Dữ liệu trên đã được sắp theo ngày tháng năm sinh.  Cần tổ chức lại dữ liệu sao cho nữ được liệt kê trước nam nhưng vẫn giữ được tính đã sắp theo ngày tháng năm sinh. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University23 13.3. Ví dụ về hàng đợi (4/5) Tổ chức dữ liệu hợp lý - Demerging (1/4) Cách giải quyết:  Ý tưởng không hiệu quả:  Sử dụng thuật toán sắp xếp.  Độ phức tạp của thuật toán O(n log n) trong trường hợp tốt nhất.  Ý tưởng hiệu quả hơn:  Sử dụng giải thuật demerging.  Độ phức tạp của giải thuật này là O(n). @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University24 13.3. Ví dụ về hàng đợi (5/5) Giải thuật Demerging. 1. Tạo 2 queue rỗng, có tên lần lượt là NU và NAM. 2. Với mỗi bản ghi p, xem xét: 2.1. Nếu p có giới tính nữ, đưa vào queue NU. 2.2. Nếu p có giới tính nam, đưa vào queue NAM. 3. Xét queue NU, khi queue chưa rỗng: 3.1. Lấy từng phần tử trong queue này. 3.2. Ghi vào file output nào đó. 4. Xét queue NAM, khi queue chưa rỗng: 4.1. Lấy từng phần tử trong queue này. 4.2. Ghi tiếp vào file output trên. 5. Kết thúc giải thuật. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University25/25 13.3. Thuật toán chuyển đổi biểu thức dạng Infix sang Prefix (1/4) Thuật toán thứ nhất: chuyển đổi biểu thức từ Infix sang Prefix: Sử dụng queue, stack và stackkq.  Bước 1 : Đọc một thành phần của biểu thức E (dạng Infix biểu diễn bằng xâu, đọc từ phải qua trái). Giả sử thành phần đọc được là x 1.1. Nếu x là toán hạng thì đưa nó vào queue. 1.2. Nếu x là dấu ‘)’ thì đẩy nó vào stack. 1.3. Nếu x là một trong các phép toán +, -, *, / thì 1.3.1. Kiểm tra xem stack có rỗng không? Nếu rỗng, đẩy vào stack, nếu không rỗng, sang bước 1.3.2. 1.3.2. Lấy phần tử y ở đỉnh stack. 1.3.3. Nếu Pri(y)>=Pri(x), đưa tất cả các phần tử trong queue vào stackkq, đưa y vào stackkq, đưa x vào stack. 1.3.4. Nếu Pri(y)<Pri(x) thì đẩy x vào stack. PhD Ngo Huu Phuc, Le Quy Don Technical University26 13.3. Thuật toán chuyển đổi biểu thức dạng Infix sang Prefix (1/4) 1.4. Nếu x là dấu ‘(’ thì 1.4.1. Đưa tất cả các phần tử trong queue vào stackkq, 1.4.2. Xét phần tử y ở đầu của stack. 1.4.3. y là phép toán thì loại y ra khỏi stack, đưa y vào stackkq, quay về bước 1.4.2. 1.4.3. Nếu y là dấu ‘)’ loại y ra khỏi stack.  Bước 2 : Lập lại bước 1 cho đến khi toàn bộ biểu thức E được duyệt.  Bước 3 : Đưa tất cả các phần tử trong queue vào stackkq, tất cả phần tử trong stack và stackkq.  Bước 4: Lấy từng phần tử trong stackkq ra, đó là kết quả dạng Prefix.  Bước 5: Tính giá trị của biểu thức dưới dạng tiền tố. Chú ý: Pri(‘(‘)=Pri(‘)‘) <Pri(‘+‘)=Pri(‘-‘)<Pri(‘*‘)=<Pri(‘/‘) PhD Ngo Huu Phuc, Le Quy Don Technical University27 13.3. Thuật toán chuyển đổi biểu thức dạng Infix sang Prefix (1/4) Thuật toán thứ hai: Tính giá trị biểu thức dạng Prefix:  Bước 1 : Đọc lần lượt các phần tử của biểu thức E1 (từ phải qua trái)  Nếu gặp toán hạng thì đẩy nó vào stack.  Nếu gặp phép toán thì lấy hai phần tử liên tiếp trong stack thực hiện phép toán, kết quả được đẩy vào trong stack.  Bước 2 : Lập lại bước 1 cho đến khi hết tất cả các phần tử trong biểu thức E1. Lúc đó đỉnh của stack chứa giá trị của biểu thức cần tính.  Bước 3. Kết thúc. PhD Ngo Huu Phuc, Le Quy Don Technical University28 13.3. Ví dụ về chuyển đổi từ Infix sang Prefix (1/2) Cho biểu thức: E=a*b+c/d. PhD Ngo Huu Phuc, Le Quy Don Technical University29 Bước E Phần tử xét queue stack stackkq 0 a*b+c/d null empty empty null 1 a*b+c/ d d empty null 2 a*b+c / d / null 3 a*b+ c d c / null 4 a*b + empty + dc/ 5 a* b b + dc/ 6 A * b * + dc/ 7 Null a b a * + dc/ 8 Null null empty empty dc/ba*+ Kết quả: +*ab/cd 13.3. Ví dụ về tính biểu thức dạng Prefix (2/2) Xét biểu thức dạng Prefix: (đọc từ phải qua trái) /+7 8 + 6 * + 3 2 + 5 4 PhD Ngo Huu Phuc, Le Quy Don Technical University30 51 8 7 4 4 5 4 5 9 9 2 9 2 3 9 2 3 9 5 9 5 45 45 6 45 6 51 51 8 51 8 7 51 15 51 15 3.4 + + * + + / 13.3. Chương trình minh họa (1/4) PhD. Ngo Huu Phuc, Le Quy Don Technical University31 #include "stdio.h" #include "conio.h" #include "string.h" #include "ctype.h" #define MaxEntry 100 #include "StackClass.h" #include "QueueClass.h" typedef char StackEntry; typedef char QueueEntry; int priority(char c); char *InfixToPrefix(char *Infix); void show(char *); int calculate(char []); void main() { char input[MaxEntry]; printf("Nhap Infix:"); gets(input); printf("Output:"); strcpy(input,InfixToPrefix(input)); show(input); printf("\nGia tri bieu thuc: %d",calculate(input)); getch(); } int priority(char c) { if (c == '$') return 3; if (c == '*' || c == '/' || c == '%') return 2; else { if (c == '+' || c == '-') return 1; else return 0; } } 13.3. Chương trình minh họa (2/4) PhD. Ngo Huu Phuc, Le Quy Don Technical University32 char *InfixToPrefix(char *Infix) { StackClass stack, stackkq; QueueClassL queue; int n=strlen(Infix); char opr, kt, vt; int i=n-1; while(i>=0) { vt=Infix[i]; if(Infix[i]==' ' || Infix[i]=='\t') { i--; continue; } if(isdigit(Infix[i]) || isalpha(Infix[i])) { queue.Enqueue(Infix[i]); } if(Infix[i]==')') { stack.push(Infix[i]); } if(Infix[i]=='+' || Infix[i]=='-' || Infix[i]=='*' || Infix[i]=='/' || Infix[i]=='%' || Infix[i]=='$') { if(!stack.isEmpty()) { stack.pop(&opr); while(priority(opr)>=priority(Infix[i])) { while(!queue.isEmpty()) { queue.Dequeue(&kt); stackkq.push(kt); } stackkq.push(opr); vt=stack.pop(&opr); if(!vt) break; } if(vt) stack.push(opr); stack.push(Infix[i]); } else { stack.push(Infix[i]); } } 13.3. Chương trình minh họa (3/4) PhD. Ngo Huu Phuc, Le Quy Don Technical University33 if(Infix[i]=='(') { while(!queue.isEmpty()) { queue.Dequeue(&opr); stackkq.push(opr); } stack.pop(&opr); while(opr!=')') { stackkq.push(opr); stack.pop(&opr); } } i--; } while(!queue.isEmpty()) { queue.Dequeue(&opr); stackkq.push(opr); } while(!stack.isEmpty()) { stack.pop(&opr); stackkq.push(opr); } char kq[MaxEntry]; i=0; while(!stackkq.isEmpty()) { stackkq.pop(&opr); kq[i]=opr; i++; } kq[i]='\0'; return kq; } void show(char *value) { puts(value); } 13.3. Chương trình minh họa (4/4) PhD. Ngo Huu Phuc, Le Quy Don Technical University34 int calculate(char input[MaxEntry]) { int n=strlen(input); StackClass stack; int i=n-1; while(i>=0) { char vt=input[i]; if(isdigit(input[i])) stack.push(input[i]); if(input[i]=='+' || input[i]=='-' || input[i]=='*' || input[i]=='/' || input[i]=='%' || input[i]=='$') { char a; char b; stack.pop(&a); stack.pop(&b); a=a-'0'; b=b-'0'; if(input[i]=='+') a=a+b; if(input[i]=='-') a=a-b; if(input[i]=='*') a=a*b; if(input[i]=='/') a=a/b; if(input[i]=='%') a=a%b; a=a+'0'; stack.push(a); } i--; } char a; stack.pop(&a); return a-'0'; }