›
›

Cấu trúc dữ liệu và giải thuật - Stack – Ngăn xếp

pdf 61 trang vanle 2730
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 - Stack – Ngăn xếp", để 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_stack_ngan_xep.pdf

Nội dung text: Cấu trúc dữ liệu và giải thuật - Stack – Ngăn xếp

  1. INDUSTRIAL UNIVERSITY OF HO CHI MINH CITY Data structures and algorithms Stack and Queue Dr. Ngô Hữu Dũng
  2. Introduction  Stack (LIFO – last in, first  Queue (FIFO – first in, out: a collection of items first out): a collection of in which only the most items in which first items recently added item may entered are the first ones to be removed. be removed. 2 Cấu trúc dữ liệu và giải thuật - Stack&Queue
  3. Stack vs. Queue  Stack – Ngăn xếp  Last In First Out (LIFO) Push 34 Top  Thao tác Pop  Push 56  Pop 45  Queue – Hàng đợi 37  First In First Out (FIFO)  Thao tác deQueue 34 56 45 37 enQueue  enQueue  deQueue Front Rear 3 Cấu trúc dữ liệu và giải thuật - Stack&Queue
  4. Push 34 Top Pop 56 45 37 Stack – Last in, first out Stack Ngăn xếp 4 Cấu trúc dữ liệu và giải thuật - Stack&Queue
  5. Khái niệm Stack  Lưu trữ một tập các phần tử theo một trật tự nhất định  Nguyên tắc: Last in, first out  Vào sau cùng, ra trước tiên  Top: Phần tử trên cùng Push 34 Top  Chèn phần tử vào top Pop  Thao tác push 56  Chèn vào đầu danh sách 45  Xuất phần tử từ top 37  Thao tác pop  Xoá phần tử ở đầu danh sách 5 Cấu trúc dữ liệu và giải thuật - Stack&Queue
  6. Applications  Balancing of symbols  Infix to Postfix /Prefix conversion  Redo-undo features at many places like editors, Photoshop.  Forward and backward feature in web browsers  Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem.  Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and Sudoku solver 6 Cấu trúc dữ liệu và giải thuật - Stack&Queue
  7. Thao tác trên Stack  Push: Thêm một phần tử vào stack  Nếu stack chưa đầy thì thêm phần tử ở top  Pop: Xoá một phần tử từ stack  Nếu stack không rỗng thì xoá phần tử ở top  Top: Lấy phần tử ở top  initStack: khởi tạo Stack  isEmpty: Kiểm tra stack rỗng?  Trả về true nếu stack rỗng  isFull: Kiểm tra stack đầy?  Trả về true nếu stack đầy 7
  8. Tổ chức dữ liệu  Array  Linked list 1. struct Stack 1. struct Node 2. { 2. { 3. int top; 3. int data; 4. int capacity; 4. struct Node* next; 5. int* array; 5. }; 6. }; 6. struct Stack 7. struct Stack* tStack; 7. { 8. Node *top; 9. }; 8
  9. Thao tác Push vào Stack PUSH Top 9
  10. Thao tác Pop khỏi stack Top POP 10
  11. Stack – Sử dụng mảng Top 6 3 9 Stack 9 3 6 0 1 2 3 4 5 6 7 8 9 11
  12. 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; 12
  13. 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; } 13
  14. Stack số nguyên – Sử dụng mảng bool IsEmpty(const STACK &s) { if (s.StkTop==-1) return true; return false; } 14
  15. Stack số nguyên – Sử dụng mảng bool IsFull(const STACK &s) { if (s.StkTop==s.StkMax-1) return true; return false; } 15
  16. 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; } 16
  17. 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; } 17
  18. 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) 18
  19. 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 19
  20. Stack – Sử dụng DSLK StkCnt StkTop N 7 7 Data Link 9 9  Data Link 4  4 Data Link 20
  21. Stack – Sử dụng DSLK  Cấu tạo đầu stack stack StkCnt StkCnt StkTop StkTop  CấuNtạo một phần tử end stack node Data Link end node Data Link 21
  22. 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; }; 22
  23. Stack – Sử dụng DSLK  VD: Thực hiện một số thao tác trên stack STACK s; InitStack(s); StkCnt StkTop Push(s, 7); N Push(s, 4); 74 Pop(s, x); // x = ? Data Link 23
  24. Stack số nguyên – Sử dụng DSLK void InitStack(STACK &s) { s.StkTop = NULL; s.StkCount = 0; } 24
  25. Stack số nguyên – Sử dụng DSLK bool IsEmpty(const STACK &s) { if (s.StkTop == NULL) return true; return false; } 25
  26. 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; } 26
  27. 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; pNew->Data = newitem; 74 Data Link pNew->pNext = s.StkTop; s.StkTop = pNew; s.StkCount++; return true; } 27
  28. 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; delete temp; 7 s.StkCount ; Data Link return true; } outitem = 4 28
  29. 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  29
  30. 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 30
  31. 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 Stop t 1 53 4 75 357 0 1 2 3 4 (3,4) i j 31 (0,4)(0,1)
  32. deQueue 34 56 45 37 enQueue Front Rear Queue – First in, first out Queue Hàng đợi 32 Cấu trúc dữ liệu và giải thuật - Stack&Queue
  33. Queue Phòng vé 33
  34. 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) 34
  35. 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 35
  36. Queue  Minh họa thao tác EnQueue  Minh họa thao tác DeQueue 36
  37. 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 37
  38. 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 38
  39. 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 39
  40. Queue số nguyên – Sử dụng mảng typedef struct QUEUE { int* QArray; int QMax; int QNumItems; int QFront; int QRear; }; 40
  41. 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? 41
  42. 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 42
  43. 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
  44. 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
  45. 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
  46. 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
  47. 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; } 47
  48. Queue số nguyên – Sử dụng mảng bool IsEmpty(QUEUE q) { if (q.QNumItems == 0) return true; return false; } 48
  49. Queue số nguyên – Sử dụng mảng bool IsFull(QUEUE q) { if (q.QMax == q.QNumItems) return true; return false; } 49
  50. 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; } 50
  51. 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; } 51
  52. 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; } 52
  53. 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; } 53
  54. 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 54
  55. Queue – Sử dụng DSLK typedef struct tagNODE { int data; tagNODE* pNext; } NODE, *PNODE; typedef struct tagQUEUE { int NumItems; PNODE pFront, pRear; } QUEUE; 55
  56. 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); 56
  57. Queue – Sử dụng DSLK bool InitQueue(QUEUE &q) { q.NumItems = 0; q.pFront = q.pRear = NULL; return true; } 57
  58. Queue – Sử dụng DSLK bool IsEmpty(const QUEUE& q) { return (q.NumItems==0); } 58
  59. Queue – Sử dụng DSLK bool IsFull(const QUEUE &q) { PNODE tmp = new NODE; if (tmp==NULL) return true; delete tmp; return false; } 59
  60. 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; } 60
  61. 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; } 61