Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3.2: Ngăn xếp và Hàng đợi - Trần Minh Thái

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3.2: Ngăn xếp và Hàng đợi - Trần Minh Thái

1. Chương 3.2. Ngăn xếp & Hàng đợi Trần Minh Thái Email: minhthai@itc.edu.vn Website: www.minhthai.edu.vn 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