›
›

Cấu trúc dữ liệu và giải thuật - Chương 5: Ngăn xếp – hàng đợi (stack - Queue)

pdf 88 trang vanle 2670
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cấu trúc dữ liệu và giải thuật - Chương 5: Ngăn xếp – hàng đợi (stack - Queue)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfcau_truc_du_lieu_va_giai_thuat_chuong_5_ngan_xep_hang_doi_st.pdf

Nội dung text: Cấu trúc dữ liệu và giải thuật - Chương 5: Ngăn xếp – hàng đợi (stack - Queue)

  1. 1 Chương 5: NGĂN XẾP – HÀNG ĐỢI (Stack - Queue)
  2. Nội dung 2  Ngăn xxếpếp (Stack)  Hàng Khái đợ iniệm Stack  Các thao tác trên Stack  Hiện thực Stack  Ứng dụng của Stack  Hàng đợi Chương 5: Ngăn xếp – Hàng đợi
  3. Stack - Khái niệm 3  Stack là một danh sách mà các đối tượng được thêm vào và lấy ra chỉ ở một đầu của danh sách (A stack is simply a list of elements with insertions and deletions permitted at one end)  Vì thế, việc thêm một đối tượng vào Stack hoặc lấy một đối tượng ra khỏi Stack được thực hiện theo cơ chế LIFO (Last In First Out - Vào sau ra trước)  Các đối tượng có thể được thêm vào Stack bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi Stack Chương 5: Ngăn xếp – Hàng đợi
  4. Stack – Các thao tác 4  Stack hỗ trợ 2 thao tác chính:  “Push”: Thao tác thêm 1 đối tượng vào Stack  “Pop”: Thao tác lấy 1 đối tượng ra khỏi Stack  Ví dụ: 5 3 2 - - 4 Chương 5: Ngăn xếp – Hàng đợi
  5. Stack – Các thao tác 5  Stack cũng hỗ trợ một số thao tác khác:  isEmpty(): Kiểm tra xem Stack có rỗng không  Top(): Trả về giá trị của phần tử nằm ở đầu Stack mà không hủy nó khỏi Stack. Nếu Stack rỗng thì lỗi sẽ xảy ra Chương 5: Ngăn xếp – Hàng đợi
  6. Stack – Hiện thực Stack (Implementation of a Stack) 6 Mảng 1 chiều Danh sách LK Kích thước stack Cấp phát khi quá thiếu, lúc động! quá thừa Push/Pop khá dễ Push / Pop hơi dàng phức tạp Chương 5: Ngăn xếp – Hàng đợi
  7. Hiện thực Stack dùng mảng (Implementation of a Stack using Array) 7  Có thể tạo một Stack bằng cách khai báo một mảng 1 chiều với kích thước tối đa là N (ví dụ: N =1000)  Stack có thể chứa tối đa N phần tử đánh số từ 0 đến N-1  Phần tử nằm ở đỉnh Stack sẽ có chỉ số là top ( lúc đó trong Stack đang chứa top+1 phần tử)  Như vậy, để khai báo một Stack, ta cần một mảng 1 chiều list, và 1 biến số nguyên top cho biết chỉ số của đỉnh Stack: struct Stack { DataType list[N]; int top; }; Chương 5: Ngăn xếp – Hàng đợi
  8. Hiện thực Stack dùng mảng (Implementation of a Stack using Array) 8  Lệnh top = 0 sẽ tạo ra một Stack S rỗng  Giá trị của top sẽ cho biết số phần tử hiện hành có trong Stack  Khi cài đặt bằng mảng 1 chiều, Stack bị giới hạn kích thước nên cần xây dựng thêm một thao tác phụ cho Stack:  isFull(): Kiểm tra xem Stack có đầy chưa, vì khi Stack đầy, việc gọi đến hàm Push() sẽ phát sinh ra lỗi Chương 5: Ngăn xếp – Hàng đợi
  9. Hiện thực Stack dùng mảng (Implementation of a Stack using Array) 9  Khởi tạo Stack: void Init (Stack &s) { s.top = 0; } Chương 5: Ngăn xếp – Hàng đợi
  10. Hiện thực Stack dùng mảng (Implementation of a Stack using Array) 10  Kiểm tra Stack rỗng hay không: int isEmpty(Stack s) { if (s.top==0) return 1; // stack rỗng else return 0; } Chương 5: Ngăn xếp – Hàng đợi
  11. Hiện thực Stack dùng mảng (Implementation of a Stack using Array) 11  Kiểm tra Stack đầy hay không: int isFull(Stack s) { if (s.top>=N) return 1; else return 0; } Chương 5: Ngăn xếp – Hàng đợi
  12. Hiện thực Stack dùng mảng (Implementation of a Stack using Array) 12  Thêm một phần tử x vào Stack void Push (Stack &s, DataType x) { if (!isFull(s)) // stack chưa đầy { s.list[s.top]=x; s.top++; } } Chương 5: Ngăn xếp – Hàng đợi
  13. Hiện thực Stack dùng mảng (Implementation of a Stack using Array) 13  Trích thông tin và huỷ phần tử ở đỉnh Stack DataType Pop(Stack &s) { DataType x; if (!Empty(s)) // stack khác rỗng { x = s.list[s.top]; s.top ; } return x; } Chương 5: Ngăn xếp – Hàng đợi
  14. Hiện thực Stack dùng mảng (Implementation of a Stack using Array) 14 Nhận xét:  Các thao tác trên đều làm việc với chi phí O(1)  Việc cài đặt Stack thông qua mảng một chiều đơn giản và khá hiệu quả  Tuy nhiên, hạn chế lớn nhất của phương án cài đặt này là giới hạn về kích thước của Stack (N)  Giá trị của N có thể quá nhỏ so với nhu cầu thực tế hoặc quá lớn sẽ làm lãng phí bộ nhớ Chương 5: Ngăn xếp – Hàng đợi
  15. Hiện thực Stack dùng DSLK (Implementation of a Stack using Linked List) 15  Có thể tạo một Stack bằng cách sử dụng một danh sách liên kết đơn (DSLK) struct Node  Khai báo các cấu trúc: { DataType data; Node *pNext; }; struct Stack { Node *top; }; Chương 5: Ngăn xếp – Hàng đợi
  16. Hiện thực Stack dùng DSLK (Implementation of a Stack using Linked List) 16  Khởi tạo Stack: void Init(Stack &t) { t.top = NULL; } Chương 5: Ngăn xếp – Hàng đợi
  17. Hiện thực Stack dùng DSLK (Implementation of a Stack using Linked List) 17  Kiểm tra xem Stack có rỗng không: int isEmpty (Stack t) { return t.top == NULL ? 1 : 0; } Chương 5: Ngăn xếp – Hàng đợi
  18. Hiện thực Stack dùng DSLK (Implementation of a Stack using Linked List) 18  Thêm một phần tử x vào Stack: void Push (Stack &t, DataType x) { Node *p = new Node; if (p==NULL) { cout data = x; pThêm->pNext= phần NULL tử vào; đầu danh sách if (t.top==NULL) // if (Empty(l)) t.top = p; else{ p->pNext = t.top; t.top = p; } } Chương 5: Ngăn xếp – Hàng đợi
  19. Hiện thực Stack dùng DSLK (Implementation of a Stack Using Linked List) 19  Trích thông tin và hủy phần tử ở đỉnh Stack: DataType Pop (Stack &t) { if (t.top==NULL){ cout pNext = NULL; t.top = t.top->pNext; x = p->data; delete p; return x; } Chương 5: Ngăn xếp – Hàng đợi
  20. Stack - Ứng dụng 20  Stack thích hợp lưu trữ các loại dữ liệu mà trình tự truy xuất ngược với trình tự lưu trữ  Một số ứng dụng của Stack:  Trong trình biên dịch (thông dịch), khi thực hiện các thủ tục, Stack được sử dụng để lưu môi trường của các thủ tục  Lưu dữ liệu khi giải một số bài toán của lý thuyết đồ thị (như tìm đường đi)  Khử đệ qui  Ứng dụng trong các bài toán tính toán biểu thức  Chương 5: Ngăn xếp – Hàng đợi
  21. Stack - Ứng dụng 21 Ví dụ: thủ tục Quick_Sort dùng Stack để khử đệ qui:  Bước 1. l=1; r=n;  Bước 2. Chọn phần tử giữa x=a[(l+r) / 2]  Bước 3. Phân hoạch (l, r) thành (l1, r1) và (l2, r2) bằng cách xét:  y thuộc (l1, r1) nếu y x  y thuộc (l2, r2) ngược lại  Bước 4. Nếu phân hoạch (l2, r2) có nhiều hơn 1 phần tử thì thực hiện:  Cất (l2, r2) vào Stack  Nếu (l1, r1) có nhiều hơn 1 phần tử thì thực hiện:  l = l1  r = r1  Quay lên bước 2  Ngược lại  Lấy (l, r) ra khỏi Stack, nếu Stack khác rỗng thì quay lên bước 2, ngược lại thì dừng Chương 5: Ngăn xếp – Hàng đợi
  22. Stack - Ứng dụng Bài tập: đổi số từ cơ số 10 sang cơ số x 57 2 Ví dụ: 57 = ???2 1 28 2 57 = 1110012 0 14 2 0 7 2 1 3 2 1 1 2 1 0 22 Chương 5: Ngăn xếp – Hàng đợi
  23. void main() { Stack s; int coso, so, sodu; Init(s); // Nhập số cần chuyển vào so // Nhập cơ số cần chuyển vào coso while (so != 0) { sodu = so % coso; Push (s, sodu); // push so du vao stack so = so/coso; } cout<<"Kết quả: "; while (!isEmpty(s)) cout<<Pop(s); // pop so du ra khoi stack } 23 Chương 5: Ngăn xếp – Hàng đợi
  24. Stack - Ứng dụng 24  Thuật toán Ba Lan ngược (Reverse Polish Notation – RPN)  Định nghĩa RPN:  Biểu thức toán học trong đó các toán tử được viết sau toán hạng và không dùng dấu ngoặc  Phát minh bởi Jan Lukasiewics một nhà khoa học Ba Lan vào những năm 1950 Chương 5: Ngăn xếp – Hàng đợi
  25. RPN Infix : toán tử viết giữa toán hạng Postfix (RPN): toán tử viết sau toán hạng Prefix : toán tử viết trước toán hạng Examples: INFIX RPN (POSTFIX) PREFIX A + B A B + + A B A * B + C A B * C + + * A B C A * (B + C) A B C + * * A + B C A - (B - (C - D))A B C D - - - - A - B - C D A - B - C - D A B - C - D - - - - A B C D 25 Chương 5: Ngăn xếp – Hàng đợi
  26. Lượng giá biểu thức RPN Kỹ thuật gạch dưới: 1. Duyệt từ trái sang phải của biểu thức cho đến khi gặp toán tử. 2. Gạch dưới 2 toán hạng ngay trước toán tử và kết hợp chúng bằng toán tử trên 3. Lặp đi lặp lại cho đến hết biểu thức. Ví dụ 2*((3+4)-(5-6)) 2 3 4 + 5 6 - - * 2 3 4 + 5 6 - - * 2 7 5 6 - - * 2 7 5 6 - - * 2 7 -1 - * 2 7 -1 - * 2 8 * 2 8 * 16 26
  27. Thuật toán tính giá trị 1. Khởi tạo Stack rỗng (chứa hằng hoặc biến). 2. Lặp cho đến khi kết thúc biểu thức: Đọc 01 phần tử của biếu thức (hằng, biến, phép toán). Nếu phần tử là hằng hay biến: đưa vào Stack. Ngược lại: Lấy ra 02 phần tử của Stack. Áp dụng phép toán cho 02 phần tử vừa lấy ra. Đưa kết quả vào Stack. 3. Giá trị của biểu thức chính là phần tử cuối cùng của Stack. 27 Chương 5: Ngăn xếp – Hàng đợi
  28. 2*((3+4)-(5-6)) Example: 2 3 4 + 5 6 - - * Push 2 4 Push 3 3 Push 4 2 Read + 6 Pop 4, Pop 3, 3 + 4 = 7 Push 7 5 Push 5 7 Push 6 2 Read - Pop 6, Pop 5, 5 - 6 = -1 -1 Push -1 Read - 7 Pop -1, Pop 7, 7 - -1 = 8 2 Push 8 8 Read * 2 Pop 8, Pop 2, 2 * 8 = 16 Push 16 16 28
  29. Chuyển infix thành postfix 1. Khởi tạo Stack rỗng (chứa các phép toán). 2. Lặp cho đến khi kết thúc biểu thức: Đọc 01 phần tử của biếu thức (01 phần tử có thể là hằng, biến,phép toán, “)” hay “(” ). Nếu phần tử là: 2.1 “(”: đưa vào Stack. 2.2 “)”: lấy các phần tử của Stack ra cho đến khi gặp “(” trong Stack. 29 Chương 5: Ngăn xếp – Hàng đợi
  30. Chuyển infix thành postfix 2.3 Một phép toán: + - * / Nếu Stack rỗng: đưa vào Stack. Nếu Stack khác rỗng và phép toán có độ ưu tiên cao hơn phần tử ở đầu Stack: đưa vào Stack. Nếu Stack khác rỗng và phép toán có độ ưu tiên thấp hơn hoặc bằng phần tử ở đầu Stack: - lấy phần tử từ Stack ra; - sau đó lặp lại việc so sánh với phần tử ở đầu Stack. 30 Chương 5: Ngăn xếp – Hàng đợi
  31. Chuyển infix thành postfix 2.4 Hằng hoặc biến: đưa vào kết quả. 3. Lấy hết tất cả các phần tử của Stack ra. 31 Chương 5: Ngăn xếp – Hàng đợi
  32. Độ ưu tiên  + , _ 1  *, / 2  ^ 3 32 Chương 5: Ngăn xếp – Hàng đợi
  33. Example: (A+B*C)/(D((A(A+(A+B(A+B*(A+B*C(A+B*C)(A+B*C)/(A+B*C)/(A+B*C)/(D+B*C)/(DB*C)/(D*C)/(DC)/(D)/(D/(D(DD-(E(E-F))FF)))) Push ( Output Display A A * Push + + Display B AB Push * ( Display C ABC + Read ) ( Pop *, Display *, ABC* Pop +, Display +, Pop ( ABC*+ ( Push / Push ( - Display D ABC*+D ( Push - Push ( - Display E ABC*+DE ( Push - / Display F ABC*+DEF - Read ) Pop -, Display -, Pop ( ABC*+DEF- ( Read ) / Pop -, Display -, Pop ( ABC*+DEF / Pop /, Display / ABC*+DEF / 33
  34. Ví dụ A + (B*C - (D/E^F) * G) * H S=[]; KQ=“” 34 Chương 5: Ngăn xếp – Hàng đợi
  35. Ví dụ A + (B*C - (D/E^F) * G)A +* H(B*C - (D/E^F) * G) * H S=[];S=[+]; KQ=“A”KQ=“” 35 Chương 5: Ngăn xếp – Hàng đợi
  36. Ví dụ A + (B*C((B(B*B*C*CC - (D/E^F) * G) * H S=[+];S=[+(];S=[+(*]; KQ=ABCKQ=AKQ=AB 36 Chương 5: Ngăn xếp – Hàng đợi
  37. Ví dụ A + (B*C - (D/E^F) * G) * H S=[+(S=[+(];S=[+(*];-]; KQ=ABC*KQ=ABC 37 Chương 5: Ngăn xếp – Hàng đợi
  38. Ví dụ A + (B*C - (D/E^F) * G) * H S=[+(S=[+( ];(]; KQ=ABC* 38 Chương 5: Ngăn xếp – Hàng đợi
  39. Ví dụ A + (B*C - (D/E^F) * G) * H S=[+(-(]; KQ=ABC*KQ=ABC*D 39 Chương 5: Ngăn xếp – Hàng đợi
  40. Ví dụ A + (B*C - (D/E^F) * G) * H S=[+(S=[+( (/];(]; KQ=ABC*D 40 Chương 5: Ngăn xếp – Hàng đợi
  41. Ví dụ A + (B*C - (D/E^F) * G) * H S=[+(-(/]; KQ=ABC*DKQ=ABC*DE 41 Chương 5: Ngăn xếp – Hàng đợi
  42. Ví dụ A + (B*C - (D/E^F) * G) * H S=[+(S=[+( (/^];(/]; KQ=ABC*DE 42 Chương 5: Ngăn xếp – Hàng đợi
  43. Ví dụ A + (B*C - (D/E^F) * G) * H S=[+(-(/^]; KQ=ABC*DEKQ=ABC*DEF 43 Chương 5: Ngăn xếp – Hàng đợi
  44. Ví dụ A + (B*C - (D/E^F) * G) * H S=[+(S=[+(S=[+( (/^];];(/];(]; KQ=ABC*DEF^/KQ=ABC*DEF^KQ=ABC*DEF 44 Chương 5: Ngăn xếp – Hàng đợi
  45. Ví dụ A + (B*C - (D/E^F) * G) * H S=[+(-];*]; KQ=ABC*DEF^/ 45 Chương 5: Ngăn xếp – Hàng đợi
  46. Ví dụ A + (B*C - (D/E^F) * G) * H S=[+(-*]; KQ=ABC*DEF^/GKQ=ABC*DEF^/ 46 Chương 5: Ngăn xếp – Hàng đợi
  47. Ví dụ A + (B*C - (D/E^F) * G) * H S=[+];S=[+(S=[+(];-*];]; KQ=ABC*DEF^/G*KQ=ABC*DEF^/G - 47 Chương 5: Ngăn xếp – Hàng đợi
  48. Ví dụ A + (B*C - (D/E^F) * G) * H S=[+];S=[+*]; KQ=ABC*DEF^/G*- 48 Chương 5: Ngăn xếp – Hàng đợi
  49. Ví dụ A + (B*C - (D/E^F) * G) * H S=[+*]; KQ=ABC*DEF^/G*KQ=ABC*DEF^/G* H 49 Chương 5: Ngăn xếp – Hàng đợi
  50. Ví dụ A + (B*C - (D/E^F) * G) * H S=[+*];S=[]; KQ=ABC*DEF^/G*KQ=ABC*DEF^/G*-H*+H -H*+ 50 Chương 5: Ngăn xếp – Hàng đợi
  51. Nội dung 51  Ngăn xếp (Stack)  Hàng đợi (Queue)  Khái niệm Queue  Các thao tác trên Queue  Hiện thực Queue  Ứng dụng Queue Chương 5: Ngăn xếp – Hàng đợi
  52. Queue - Khái niệm 52  Queue là một danh sách mà các đối tượng được thêm vào ở một đầu của danh sách và lấy ra ở một đầu kia của danh sách (A queue is also a list of elements with insertions permitted at one end and deletions permitted from the other end)  Việc thêm một đối tượng vào Queue luôn diễn ra ở cuối Queue và việc lấy một đối tượng ra khỏi Queue luôn diễn ra ở đầu Queue  Vì thế, việc thêm một đối tượng vào Queue hoặc lấy một đối tượng ra khỏi Queue được thực hiện theo cơ chế FIFO (First In First Out - Vào trước ra trước) Chương 5: Ngăn xếp – Hàng đợi
  53. Queue - Khái niệm 53 Imaging Chương 5: Ngăn xếp – Hàng đợi
  54. Queue – Các thao tác 54  Hàng đợi hỗ trợ các thao tác:  EnQueue(): Thêm đối tượng vào cuối (rear) Queue  DeQueue(): Lấy đối tượng ở đầu (front) Queue ra khỏi Queue  Ví dụ: 5 3 2 - - 4 Front Rear Chương 5: Ngăn xếp – Hàng đợi
  55. Queue – Các thao tác 55  Queue còn hỗ trợ các thao tác:  isEmpty(): Kiểm tra xem hàng đợi có rỗng không  Front(): Trả về giá trị của phần tử nằm ở đầu hàng đợi mà không hủy nó. Nếu hàng đợi rỗng thì lỗi sẽ xảy ra Chương 5: Ngăn xếp – Hàng đợi
  56. Queue – Hiện thực Queue (Implementation of a Queue) 56 Mảng 1 chiều Danh sách LK Kích thước queue Cấp phát khi quá thiếu, lúc động! quá thừa EnQueue/DeQueue khá dễ dàng EnQueue/DeQueue hơi phức tạp Chương 5: Ngăn xếp – Hàng đợi
  57. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 57  Có thể tạo một Queue bằng cách sử dụng một mảng 1 chiều theo kiểu xoay vòng (coi phần tử an-1 kề với phần tử a0) Hàng đợi chứa tối đa N phần tử  Phần tử ở đầu hàng đợi sẽ có chỉ số front  Phần tử ở cuối hàng đợi sẽ có chỉ số rear  The limitation of an array implementation is that the queue cannot grow and shrink dynamically as per the requirement Chương 5: Ngăn xếp – Hàng đợi
  58. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 58  Dùng mảng: Có xu hướng dời về cuối mảng  Hai cách hiện thực:  Khi lấy một phần tử ra thì đồng thời dời ô lên một vị trí: A B C D B C D B C D E Ban đầu Lấy ra 1 phần tử: Thêm vào 1 phần tử dời tất cả về trước để trống chỗ thêm vào  Khi lấy một phần tử ra thì không dời ô lên: A B C D B C D B C D E Ban đầu Lấy ra 1 phần tử Thêm vào 1 phần tử Chương 5: Ngăn xếp – Hàng đợi
  59. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 59  Trạng thái Queue lúc bình thường:  Trạng thái Queue lúc xoay vòng: Chương 5: Ngăn xếp – Hàng đợi
  60. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 60 f r A 12 1 4 2 5 A[0] A[1] A[2] A[N-1] DeQueue(Q) Cách dùng mảng 1 Chương 5: Ngăn xếp – Hàng đợi
  61. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 61 f r A 1 4 2 5 A[0] A[1] A[2] A[N-1] DeQueue(Q) Cách dùng mảng 1 Chương 5: Ngăn xếp – Hàng đợi
  62. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 62 f r A 1 4 2 5 A[0] A[1] A[2] A[N-1] Cách dùng mảng 1 Chương 5: Ngăn xếp – Hàng đợi
  63. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 63 f r A 12 1 4 2 5 A[0] A[1] A[2] A[N-1] f r A A[0] A[1] A[2] Cách dùng mảng 2 Empty queue f=r Chương 5: Ngăn xếp – Hàng đợi
  64. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 64 f r A 12 1 4 2 5 A[0] A[1] A[2] A[N-1] DeQueue(Q) Cách dùng mảng 2 Chương 5: Ngăn xếp – Hàng đợi
  65. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 65 f r A 1 4 2 5 A[0] A[1] A[2] A[N-1] DeQueue(Q) EnQueue(5,Q) Cách dùng mảng 2 Chương 5: Ngăn xếp – Hàng đợi
  66. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 66 f r A 1 4 2 5 5 A[0] A[1] A[2] A[N-1] DeQueue(Q) EnQueue(5,Q) EnQueue(5,Q) Cách dùng mảng 2 Chương 5: Ngăn xếp – Hàng đợi
  67. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 67 f r A 1 4 2 5 5 5 A[0] A[1] A[2] A[N-1] DeQueue(Q) EnQueue(5,Q) EnQueue(5,Q) DeQueue(Q) Cách dùng mảng 2 DeQueue(Q) Chương 5: Ngăn xếp – Hàng đợi
  68. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 68 f r A 2 5 5 5 A[0] A[1] A[2] A[N-1] DeQueue(Q) EnQueue(5,Q) EnQueue(5,Q) DeQueue(Q) Cách dùng mảng 2 DeQueue(Q) DeQueue(Q), EnQueue(5,Q), DeQueue(Q), EnQueue(5,Q), . Chương 5: Ngăn xếp – Hàng đợi
  69. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 69 f r A 5 5 5 5 A[0] A[1] A[2] A[N-1] DeQueue(Q) EnQueue(5,Q) EnQueue(5,Q) DeQueue(Q) Cách dùng mảng 2 DeQueue(Q) DeQueue(Q), EnQueue(5,Q), DeQueue(Q), EnQueue(5,Q), . Chương 5: Ngăn xếp – Hàng đợi
  70. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 70 r f A 5 5 5 5 A[0] A[1] A[2] A[N-1] DeQueue(Q), EnQueue(5,Q), DeQueue(Q), EnQueue(5,Q), . Cách dùng mảng 2 Chương 5: Ngăn xếp – Hàng đợi
  71. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 71 f r A 1 4 2 5 A[0] A[1] A[2] A[N-1] empty(Q): return (f = r) Front(Q): if empty(Q) then error else return A[f] Cách dùng mảng 2 Chương 5: Ngăn xếp – Hàng đợi
  72. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 72 f r A 1 4 2 5 A[0] A[1] A[2] A[N-1] size(Q): if (r >= f) then return (r-f) else return N-(f-r) Cách dùng mảng 2 Chương 5: Ngăn xếp – Hàng đợi
  73. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 73 r f A 5 5 5 5 A[0] A[1] A[2] A[N-1] size(Q): if (r >= f) then return (r-f) else return N-(f-r) Cách dùng mảng 2 Chương 5: Ngăn xếp – Hàng đợi
  74. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 74  Để khai báo một Queue, ta cần khai báo:  một mảng một chiều list,  hai biến nguyên front, rear cho biết chỉ số của đầu và cuối của hàng đợi,  hằng số N cho biết kích thước tối đa của Queue  Hàng đợi có thể được khai báo cụ thể như sau: struct Queue { int front, rear; DataType list[N]; }; Chương 5: Ngăn xếp – Hàng đợi
  75. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 75  Do khi cài đặt bằng mảng một chiều, hàng đợi bị giới hạn kích thước nên cần xây dựng thêm một thao tác phụ cho hàng đợi:  isFull(): Kiểm tra xem hàng đợi có đầy chưa Chương 5: Ngăn xếp – Hàng đợi
  76. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 76  Khởi tạo Queue: void Init(Queue &q) { q.front = q.rear = 0; }  Kiểm tra xem Queue có rỗng không: int isEmpty(Queue q) { if (q.front == q.rear == 0) return 1; if (q.front == q.rear) return 1; return 0; } Chương 5: Ngăn xếp – Hàng đợi
  77. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 77  Kiểm tra hàng đợi đầy hay không: int isFull(Queue q) { if (q.front == 0 && q.rear == N-1) return 1; if (q.front == q.rear) return 1; return 0; } Chương 5: Ngăn xếp – Hàng đợi
  78. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 78  Thêm một phần tử x vào cuối Queue: int EnQueue(Queue &q, DataType x) { if (isFull(q)) return 0; // không thêm được vì Queue đầy q.list[q.rear] = x; q.rear++; if (q.rear == N) q.rear=0; return 1; } Chương 5: Ngăn xếp – Hàng đợi
  79. Hiện thực Queue dùng mảng (Implementation of a Queue using Array) 79  Trích, huỷ phần tử ở đầu hàng đợi: DataType DeQueue(Queue &q) { if (Empty(q)) return NULLDATA; DataType t = q.list[q.front]; q.front++; if (q.front == N) q.front = 0; return t; } Chương 5: Ngăn xếp – Hàng đợi
  80. Hiện thực Queue dùng mảng (Implementation of a Queue using Array)  Xem thông tin của phần tử ở đầu Queue: DataType Front(Queue q) { if (isEmpty(q)) return NULLDATA; return q.list[q.front]; } Chương 5: Ngăn xếp – Hàng đợi
  81. Hiện thực Queue dùng DSLK (Implementation of a Queue using Linked List) 81  Có thể tạo một hàng đợi sử dụng một DSLK đơn  Phần tử đầu DSKL (phead) sẽ là phần tử đầu Queue (front), phần tử cuối DSKL (ptail) sẽ là phần tử cuối Queue (rear) Cuối queue Đầu queue a0 a1 a2 aN-2 an-1 Chương 5: Ngăn xếp – Hàng đợi
  82. Hiện thực Queue dùng DSLK (Implementation of a Queue using Linked List) 82  Khai báo các cấu trúc: struct Node { DataType data; Node *pNext; }; struct Queue { Node *front, *rear; }; Chương 5: Ngăn xếp – Hàng đợi
  83. Hiện thực Queue dùng DSLK (Implementation of a Queue using Linked List) 83  Khởi tạo Queue rỗng: void Init(Queue &q) { q.front = q.rear = NULL; }  Kiểm tra hàng đợi rỗng : int isEmpty(Queue &q) { if (q.front == NULL) return 1; else return 0; } Chương 5: Ngăn xếp – Hàng đợi
  84. Hiện thực Queue dùng DSLK (Implementation of a Queue using Linked List) 84  Thêm một phần tử p vào cuối Queue: int EnQueue(Queue &q, DataType x) { Node *p = new Node; if (p==NULL) return 0; //Khong du bo nho p->pNext = NULL; p->data = x; if (q.front == NULL) // TH Queue rỗng q.front = q.rear = new_node; else { q.rear->pNext = new_node; q.rear = new_node; } return 1; } Chương 5: Ngăn xếp – Hàng đợi
  85. Hiện thực Queue dùng DSLK (Implementation of a Queue using Linked List) 85  Trích và huỷ phần tử ở đầu Queue: DataType DeQueue(Queue &q) { if (isEmpty(q)) return NULLDATA; Node *p = q.front; p->pNext = NULL; q.front = q.front->pNext; if (q.front==NULL) q.rear = NULL; DataType x = p->data; delete p; return x; } Chương 5: Ngăn xếp – Hàng đợi
  86. Hiện thực Queue dùng mảng (Implementation of a Queue using Array)  Xem thông tin của phần tử ở đầu Queue: DataType Front(Queue q) { if (isEmpty(q)) return NULLDATA; return q.front->data; } Chương 5: Ngăn xếp – Hàng đợi
  87. Hiện thực Queue dùng DSLK (Implementation of a Queue using Linked List) 87 Nhận xét:  Các thao tác trên Queue biểu diễn bằng danh sách liên kết làm việc với chi phí O(1)  Nếu không quản lý phần tử cuối xâu, thao tác Dequeue sẽ có độ phức tạp O(n) Chương 5: Ngăn xếp – Hàng đợi
  88. Queue - Ứng dụng 88  Queue có thể được sử dụng trong một số bài toán:  Bài toán “sản xuất và tiêu thụ” (ứng dụng trong các hệ điều hành song song)  Bộ đệm (ví dụ: Nhấn phím Bộ đệm CPU xử lý)  Xử lý các lệnh trong máy tính (ứng dụng trong HĐH, trình biên dịch), hàng đợi các tiến trình chờ được xử lý, . Chương 5: Ngăn xếp – Hàng đợi