Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 4: Ngăn xếp và hàng đợi - Võ Quang Hoàng Khang

Nội dung text: Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 4: Ngăn xếp và hàng đợi - Võ Quang Hoàng Khang

1. Chương 4. Ngăn xếp & Hàng đợi Võ Quang Hoàng Khang Email: vqhkhang@gmail.com 1
2. Nội dung .Trình bày khái niệm Ngăn xếp (Stack) và Hàng đợi (Queue) .Minh họa các ứng dụng .Các phương pháp xây dựng Stack và Queue 2
3. Khái niệm Stack 3
4. Khái niệm Stack .Gồm nhiều phần tử .Hoạt động theo cơ chế “Vào sau – Ra trước” (LIFO – Last In, First Out) Đỉnh ngăn xếp 4
5. Thao tác cơ bản trên Stack .InitStack: khởi tạo Stack rỗng .IsEmpty: kiểm tra Stack rỗng? Push Pop .IsFull: kiểm tra Stack đầy? .Push: thêm 1 phần tử vào Stack .Pop: lấy ra 1 phần tử khỏi Stack 5
6. Thao tác Push vào Stack PUSH Top 6
7. Thao tác Pop khỏi stack Top POP 7
8. Cách xây dựng Stack Mảng 1 chiều Danh sách liên kết . Viết chương trình dễ . Phức tạp khi triển khai dàng, nhanh chóng chương trình . Bị hạn chế do số . Không bị cố định về lượng phần tử cố định số phần tử, phụ thuộc . Tốn chi phí tái cấp vào bộ nhớ phát và sao chép vùng nhớ nếu sử dụng mảng động 8
9. Stack – Sử dụng mảng Top 6 3 9 Stack 9 3 6 0 1 2 3 4 5 6 7 8 9 9
10. Stack số nguyên – Sử dụng mảng struct ttStack { int* StkArray; // mảng chứa các phần tử int StkMax; // số phần tử tối đa int StkTop; // vị trí đỉnh Stack }; typedef struct ttStack STACK; 10
11. Stack số nguyên – Sử dụng mảng bool InitStack(STACK& s, int MaxItems) { s.StkArray = new int[MaxItems]; if (s.StkArray == NULL) return false; s.StkMax = MaxItems; s.StkTop = -1; return true; } 11
12. Stack số nguyên – Sử dụng mảng bool IsEmpty(const STACK &s) { if (s.StkTop==-1) return true; return false; } 12
13. Stack số nguyên – Sử dụng mảng bool IsFull(const STACK &s) { if (s.StkTop==s.StkMax-1) return true; return false; } 13
14. Stack số nguyên – Sử dụng mảng bool Push (STACK &s, int newitem) { if (IsFull(s)) return false; s.StkTop++; s.StkArray[s.StkTop] = newitem; return true; } 14
15. Stack số nguyên – Sử dụng mảng bool Pop(STACK &s, int &outitem) { if (IsEmpty(s)) return false; outitem = s.StkArray[s.StkTop]; s.StkTop ; return true; } 15
16. Bài tập .Viết hàm nhập và xuất Stack số nguyên .Khai báo cấu trúc và viết hàm tạo Stack từ chuỗi ký tự str (mỗi phần tử Stack là ký tự) .Khai báo cấu trúc và viết hàm tạo Stack từ chuỗi ký tự str (mỗi phần tử Stack là một từ - từ cách nhau bởi khoảng trắng) 16
17. Stack – Ví dụ ứng dụng .Kiểm tra sự tương ứng của các cặp ngoặc đơn trong một biểu thức ? ? .( ( A + B ) / C ( A + B ) / C) .Đảo ngược một chuỗi ký tự .Cá Ăn Kiến nếiK nĂ áC 17
18. Stack – Sử dụng DSLK StkCnt StkTop N 7 7 Data Link 9 9  Data Link 4 4 Data Link 18
19. Stack – Sử dụng DSLK .Cấu tạo đầu stack stack StkCnt StkCnt StkTop StkTop N end stack node .Cấu tạo một phần tử Data Link end node Data Link 19
20. Stack số nguyên – Sử dụng DSLK typedef struct tagSTACK_NODE { int Data; tagSTACK_NODE *pNext; } STACK_NODE; typedef struct STACK { int StkCount; STACK_NODE *StkTop; }; 20
21. Stack – Sử dụng DSLK .VD: Thực hiện một số thao tác trên stack STACK s; StkCnt StkTop N InitStack(s); 74 Push(s, 7); Data Link Push(s, 4); Pop(s, x); // x = ? 21
22. Stack số nguyên – Sử dụng DSLK void InitStack(STACK &s) { s.StkTop = NULL; s.StkCount = 0; } 22
23. Stack số nguyên – Sử dụng DSLK bool IsEmpty(const STACK &s) { if (s.StkTop == NULL) return true; return false; } 23
24. Stack số nguyên – Sử dụng DSLK bool IsFull (const STACK s) { STACK_NODE* temp = new STACK_NODE; if (temp == NULL) return true; delete temp; return false; } 24
25. Stack số nguyên – Sử dụng DSLK bool Push(STACK &s, int newitem) { if (IsFull(s)) StkCnt StkTop return false; N STACK_NODE *pNew = new STACK_NODE; 74 pNew->Data = newitem; Data Link pNew->pNext = s.StkTop; s.StkTop = pNew; s.StkCount++; return true; } 25
26. Stack số nguyên – Sử dụng DSLK bool Pop(STACK &s, int &outitem) { StkCnt StkTop if (IsEmpty(s)) N temp return false; STACK_NODE *temp = s.StkTop; 4 outitem = s.StkTop->Data; Data Link s.StkTop = s.StkTop->pNext; 7 delete temp; Data Link s.StkCount ; return true; } outitem = 4 26
27. Stack – Ứng dụng .Stack có nhiều ứng dụng: .Lưu vết trong thuật toán “back-tracking” (theo dõi dấu vết) .Tính giá trị biểu thức toán học (thuật toán Balan ngược) .Khử đệ quy . 27
28. Stack – Quick Sort .Để khử đệ quy cho Quick Sort, ta sử dụng một stack để lưu lại các partition (phân hoạch) cần tiến hành sắp xếp. .Ý tưởng: .Push phân hoạch đầu tiên (0, n-1) vào stack .Trong khi stack chưa rỗng . Pop một phân hoạch từ stack . Chọn phần tử trục trên phân hoạch này . Điều chỉnh phân hoạch tương ứng với trục . Push 2 phân hoạch bên trái và phải trục vào stack 28
29. Stack – Quick Sort . Push phân hoạch đầu tiên (0, n-1) vào stack . Trong khi stack chưa rỗng . Pop một phân hoạch từ stack . Chọn phần tử trục trên phân hoạch này . Điều chỉnh phân hoạch tương ứng với trục . Push 2 phân hoạch bên trái và phải trục vào stack Stack rỗng t Stop 1 53 4 75 357 0 1 2 3 4 (3,4) i j (0,4)(0,1) 29
30. Queue Phòng vé 30
31. Queue – Định nghĩa .Hàng đợi là một cấu trúc: .Gồm nhiều phần tử có thứ tự .Hoạt động theo cơ chế “Vào trước, ra trước” (FIFO - First In First Out) 31
32. Queue – Định nghĩa .Các thao tác cơ bản trên hàng đợi: .InitQueue: khởi tạo hàng đợi rỗng .IsEmpty: kiểm tra hàng đợi rỗng? .IsFull: kiểm tra hàng đợi đầy? .EnQueue: thêm 1 phần tử vào cuối hàng đợi, có thể làm hàng đợi đầy .DeQueue: lấy ra 1 phần tử từ đầu Queue, có thể làm Queue rỗng 32
33. Queue .Minh họa thao tác EnQueue .Minh họa thao tác DeQueue 33
34. Cách xây dựng Queue .Sử dụng mảng một chiều .Sử dụng danh sách liên kết đơn 34
35. Queue – Sử dụng mảng .Dùng 1 mảng (QArray) để chứa các phần tử. .Dùng 1 số nguyên (QMax)để lưu số phần tử tối đa trong hàng đợi .Dùng 2 số nguyên (QFront, QRear) để xác định vị trí đầu, cuối hàng đợi .Dùng 1 số nguyên (QNumItems) để lưu số phần tử hiện có trong hàng đợi 35
36. Queue – Sử dụng mảng 0 1 2 3 4 5 6 Qarray 37 22 15 3 QMax = 7 QNumItems = 4 QFront = 1 QRear = 4 36
37. Queue số nguyên – Sử dụng mảng typedef struct QUEUE { int* QArray; int QMax; int QNumItems; int QFront; int QRear; }; 37
38. Queue số nguyên – Sử dụng mảng .Khi thêm nhiều phần tử sẽ xảy ra hiện tượng “tràn giả” 0 1 2 3 4 5 6 Qarray 37 22 15 3 7 9 QMax = 7 QNumItems = 6 QFront = 1 QRear = 6 .Giải pháp? Nối dài mảng (mảng động) hay sử dụng một mảng vô cùng lớn? 38
39. Queue số nguyên – Sử dụng mảng .Xử lý mảng như một danh sách liên kết vòng 0 1 2 3 4 5 6 Qarray 37 22 15 3 7 9 QMax = 7 QNumItems = 6 QFront = 1 QRear = 6 39
40. Queue số nguyên – Sử dụng mảng VD: Cho queue như sau Chỉ số mảng 0 1 2 3 4 5 6 QArray 11 7 19 21 81 QMax 7 QNumItems 5 QFront 1 QRear 5
41. Queue số nguyên – Sử dụng mảng 1. Thêm giá trị 123 vào hàng đợi Chỉ số mảng 0 1 2 3 4 5 6 QArray 11 7 19 21 81 123 QMax 7 QNumItems 6 QFront 1 QRear 6
42. Queue số nguyên – Sử dụng mảng 2. Lấy một phần tử khỏi hàng đợi Chỉ số mảng 0 1 2 3 4 5 6 QArray 11 7 19 21 81 123 QMax 7 QNumItems 5 QFront 2 QRear 6
43. Queue số nguyên – Sử dụng mảng 3. Thêm giá trị 456 vào hàng đợi Chỉ số mảng 0 1 2 3 4 5 6 QArray 456 11 7 19 21 81 123 QMax 7 QNumItems 6 QFront 2 QRear 0
44. Queue số nguyên – Sử dụng mảng bool InitQueue(QUEUE &q, int MaxItem) { q.QArray = new int[MaxItem]; if (q.QArray == NULL) return false; q.QMax = MaxItem; q.QNumItems = 0; q.QFront = q.QRear = -1; return true; } 44
45. Queue số nguyên – Sử dụng mảng bool IsEmpty(QUEUE q) { if (q.QNumItems == 0) return true; return false; } 45
46. Queue số nguyên – Sử dụng mảng bool IsFull(QUEUE q) { if (q.QMax == q.QNumItems) return true; return false; } 46
47. Queue số nguyên – Sử dụng mảng bool EnQueue(QUEUE &q, int newitem) { if (IsFull(q)) return false; q.QRear++; if (q.QRear==q.QMax) q.QRear = 0; q.QArray[q.QRear] = newitem; if (q.QNumItems==0) q.QFront = 0; q.QNumItems++; return true; } 47
48. Queue số nguyên – Sử dụng mảng bool DeQueue(QUEUE &q, int &itemout) { if (IsEmpty(q)) return false; itemout = q.QArray[q.QFront]; q.QFront++; q.QNumItems ; if (q.QFront==q.QMax) q.QFront = 0; if (q.QNumItems==0) q.QFront = q.QRear = -1; return true; } 48
49. Queue số nguyên – Sử dụng mảng bool QueueFront(const QUEUE &q, int &itemout) { if (IsEmpty(q)) return false; itemout = q.QArray[q.QFront]; return true; } 49
50. Queue số nguyên – Sử dụng mảng bool QueueRear(const QUEUE &q, int &itemout) { if (IsEmpty(q)) return false; itemout = q.QArray[q.QRear]; return true; } 50
51. Queue – Ví dụ ứng dụng .Quản lý việc thực hiện các tác vụ (task) trong môi trường xử lý song song .Hàng đợi in ấn các tài liệu .Vùng nhớ đệm (buffer) dùng cho bàn phím .Quản lý thang máy 51
52. Queue – Sử dụng DSLK typedef struct tagNODE { int data; tagNODE* pNext; } NODE, *PNODE; typedef struct tagQUEUE { int NumItems; PNODE pFront, pRear; } QUEUE; 52
53. Queue – Sử dụng DSLK .Các thao tác cơ bản bool InitQueue(QUEUE &q); bool IsEmpty(const QUEUE &q); bool IsFull(const QUEUE &q); bool EnQueue(QUEUE &q, int newitem); bool DeQueue(QUEUE &q, int& itemout); 53
54. Queue – Sử dụng DSLK bool InitQueue(QUEUE &q) { q.NumItems = 0; q.pFront = q.pRear = NULL; return true; } 54
55. Queue – Sử dụng DSLK bool IsEmpty(const QUEUE& q) { return (q.NumItems==0); } 55
56. Queue – Sử dụng DSLK bool IsFull(const QUEUE &q) { PNODE tmp = new NODE; if (tmp==NULL) return true; delete tmp; return false; } 56
57. Queue – Sử dụng DSLK bool EnQueue(QUEUE &q, int newitem) { if (IsFull(q)) return false; PNODE p = new NODE; p->data = newitem; p->pNext = NULL; if (q.pFront==NULL && q.pRear==NULL) q.pFront = q.pRear = p; else { q.pRear->pNext = p; q.pRear = p; } q.NumItems++; return true; } 57
58. Queue – Sử dụng DSLK bool DeQueue(QUEUE &q, int &itemout) { if (IsEmpty(q)) return false; PNODE p = q.pFront; q.pFront = p->pNext; itemout = p->data; q.NumItems ; delete p; if (q.NumItems==0) InitQueue(q); return true; } 58