›

Bài giảng Cấu trúc dữ liệu và giải thuật - Ngăn xếp - Đào Nam Anh

pdf 69 trang huongle 4061
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Ngăn xếp - Đào Nam Anh", để 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:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_ngan_xep_dao_nam_an.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Ngăn xếp - Đào Nam Anh

  1. DATA STRUCTURE AND ALGORITHM Stack CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NGĂN XẾP Dr. Dao Nam Anh Data Structure and Algorithm 1
  2. Outline – Nội dung • Stack - Ngăn xếp  Khái niệm Stack  Các thao tác trên Stack  Hiện thực Stack  Ứng dụng của Stack Data Structure and Algorithm 2
  3. Resource - Reference Slides of James Joshi , and Nor Bahiah Hj Ahmad, edit by Dao Nam Anh. Major Reference: • Robert Sedgewick, and Kevin Wayne, “Algorithms” Princeton University, 2011, Addison Wesley • Algorithm in C (Parts 1-5 Bundle)- Third Edition by Robert Sedgewick, Addison-Wesley • Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường. • Giải thuật và lập trình, Lê Minh Hoàng, Đại Học Sư Phạm, 2002 Data Structure and Algorithm 3
  4. Khái niệm Stack • 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) • 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 Data Structure and Algorithm 4
  5. Khái niệm Stack • 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) • 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 Data Structure and Algorithm 5
  6. Khái niệm Stack • Ví dụ: Chồng sách, chồng đĩa • LAST IN FIRST OUT (LIFO) data structure. Slide of Nor Bahiah Hj Ahmad, Software Engineering Department, FSKSM Data Structure and Algorithm 6
  7. Các thao tác Stack • 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 push Data Structure and Algorithm 7
  8. Các thao tác Stack • 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 push Data Structure and Algorithm 8
  9. Các thao tác Stack • 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 Data Structure and Algorithm 9
  10. Các thao tác Stack • 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 pop Data Structure and Algorithm 10
  11. Các thao tác Stack • 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 pop Data Structure and Algorithm 11
  12. Các thao tác Stack • 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 pop push Slide of James Joshi Data Structure and Algorithm 12
  13. Các thao tác Stack khác 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 Data Structure and Algorithm 13
  14. Stack implementation - Triển khai ngăn xếp • Ngăn xếp là cấu trúc dữ liệu • Đối tượng có thể là Integer, Double, String, hoặc, Employee, Student • Triển khai ngăn xếp như thế nào? • Bằng mảng hoặc bằng danh sách liên kết • Stack is an abstract data structure • Item can be Integer, Double, String, and also can be any data type, such as Employee, Student • How to implement a general stack for all those types?  We can implement stack using array or linked list. Data Structure and Algorithm 14
  15. Stack implementation - Triển khai ngăn xếp Array – mảng • Kích thước cố định • Kiểm tra còn chỗ không: isFull( ). • Cần biến chỉ vị trí “top of a stack”. • Rỗng khi Top = –1 Linked List – Danh sách liên kết • Kích thước linh hoạt • Cần con trỏ (pointer), trỏ về đỉnh ngăn xếp (top of stack). Data Structure and Algorithm 15
  16. Array Implementation of Stack Triển khai ngăn xếp bằng mảng Data Structure and Algorithm 16
  17. Array Implementation of Stack – Triển khai ngăn xếp bằng mảng Thao tác trên Stack • createStack() • push(item) • pop( ) top = 2 • isEmpty( ) • isFull( ) • stackTop() Data Structure and Algorithm 17
  18. Push() and pop() operations stack empty stack empty Data Structure and Algorithm 18
  19. Array Implementation of Stack – Triển khai ngăn xếp bằng mảng Các hàm 1. Stack Empty : khi top bằng -1. 2. Push: Xếp vào top = top + 1; stack[top] = newitem; 3. Pop: Lấy ra Item = stack[top]; hoặc là stackTop(); top = top – 1; Data Structure and Algorithm 19
  20. Array Implementation of Stack – Triển khai ngăn xếp bằng mảng Khai báo Stack: const int size = 100; class stack { private : // data declaration int top ; char data[size] ; public : // function declaration void createStack(); void push(char) ; // insert operation void pop() ; // delete operation char stackTop() ; // get top value bool isFull() ; // check if stack is Full bool isEmpty(); // check if stack is empty } ; Data Structure and Algorithm 20
  21. Array Implementation of Stack – Triển khai ngăn xếp bằng mảng • Kích thước:100. • Khai báo: stack aStack; Data Structure and Algorithm 21
  22. Array Implementation of Stack – Triển khai ngăn xếp bằng mảng createStack() void stack:: createStack(); { top = -1; } Data Structure and Algorithm 22
  23. Array Implementation of Stack – Triển khai ngăn xếp bằng mảng isFull() bool stack::isFull() { return (top == size-1 ); } Data Structure and Algorithm 23
  24. Array Implementation of Stack – Triển khai ngăn xếp bằng mảng bool isEmpty() bool stack::isEmpty() { return ( top == -1 ); } Data Structure and Algorithm 24
  25. Array Implementation of Stack – Triển khai ngăn xếp bằng mảng push(newItem) operation : Insert item onto stack  Top will be increased by 1. top = top + 1;  New item will be inserted at the top data[Top] = newItem; before push() after push() Data Structure and Algorithm 25
  26. Array Implementation of Stack – Triển khai ngăn xếp bằng mảng void stack::push(char newitem) { if (isFull()) // check whether stack is full cout << “Sorry,Cannot push item. Stack is now full!"<< endl; else { top = top + 1 // Top point to next index data[top] = newitem; //assign new item at top }//end else }//end push() Data Structure and Algorithm 26
  27. Array Implementation of Stack – Triển khai ngăn xếp bằng mảng pop() Operation • isEmpty() kiểm tra có ngăn nào không. • pop() giảm giá trị của top 1: top = top - 1; Before pop() after pop() Data Structure and Algorithm 27
  28. Array Implementation of Stack – Triển khai ngăn xếp bằng mảng void stack::pop() { char item; if ( isEmpty() ) cout << “Sorry, Cannot pop item. Stack is empty!” << endl; else { //display value at top to be deleted cout << “Popped value :” << data[top]; top = top – 1; // top will hold to new index }// end if }//end pop Data Structure and Algorithm 28
  29. Array Implementation of Stack – Triển khai ngăn xếp bằng mảng stackTop() : trả giá trị char stackTop() { //function to get top value if (isEmpty()) cout <<“Sorry, stack is empty!”<< endl; else return data[top]; } // end stackTop Data Structure and Algorithm 29
  30. Array Implementation of Stack – Triển khai ngăn xếp bằng mảng Nhận xét: • Các thao tác trên đều làm việc với chi phí O(l) • 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ớ Data Structure and Algorithm 30
  31. Linked List Implementation of Stack Triển khai Ngăn xếp bằng danh sách liên kết Data Structure and Algorithm 31
  32. Linked List Implementation of Stack Triển khai Ngăn xếp bằng danh sách liên kết • 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) • Khai báo các cấu trúc: Data Structure and Algorithm 32
  33. Linked List Implementation of Stack Triển khai Ngăn xếp bằng danh sách liên kết • createStack() – initialize top • push(char) – insert item onto stack • pop() – delete item from stack • isEmpty() – check whether a stack is empty. • stackTop() – get item at top isFull() – không cần thiết Data Structure and Algorithm 33
  34. Linked List Implementation of Stack Triển khai Ngăn xếp bằng danh sách liên kết class nodeStack { int data; nodeStack *next; }; class stack { private: // pengisytiharan ahli data nodeStack *top; public : // pengisytiharan ahli fungsi void createStack(); // set Top to NULL void push(int) ; // insert item into stack void pop() ; // delete item from stack int stackTop() ; // get content at top stack bool isEmpty(); // check whether stack is empty }; Data Structure and Algorithm 34
  35. Linked List Implementation of Stack Triển khai Ngăn xếp bằng danh sách liên kết • Creating a stack will initialize top to NULL - showing that currently, there is no node in the stack. void stack::createStack() { top = NULL; } • Is Empty() stack will return true if stack is empty, top is NULL. bool stack::isEmpty() { return (top == NULL); } Data Structure and Algorithm 35
  36. push() operations • 2 khả năng:  Khi ngăn xếp rỗng.  Khi ngăn xếp không rỗng. Data Structure and Algorithm 36
  37. push() to empty stack STEP 1 : newnode-> next = head; STEP 2 : head = newnode; Data Structure and Algorithm 37
  38. push()to non-empty stack STEP 1 : newnode-> next = head; STEP 2 : head = newnode; Data Structure and Algorithm 38
  39. Push() operations void stack::push(int newitem) { // create newnode nodeStack *newnode; newnode = new (nodeStack); if( newnode == NULL) cout data = newitem; newnode->next = head; head = newnode; }// end if } //end push operation Data Structure and Algorithm 39
  40. Delete item from stack (pop) STEP 1 : delnode = head; STEP 2 : head = delnode -> next; or head = head->next;STEP 3 : delete(delnode); Data Structure and Algorithm 40
  41. Pop() operation void stack::pop() { nodeStack *delnode; if (isEmpty()) cout next; delete(delnode); }// end else } // end pop Data Structure and Algorithm 41
  42. Check item at top stack int stack::stackTop() { if (isEmpty()) cout data; } // end check item at top Data Structure and Algorithm 42
  43. Linked List Implementation of Stack Triển khai Ngăn xếp bằng danh sách liên kết What we have learned so far . • Stack is a LIFO data structure • Can be implemented using array and link list • Structure of a stack using array and link list Basic Operation for a stack • createStack(),Push(),Pop() • stackTop(),isEmpty(),isFull() Data Structure and Algorithm 43
  44. Application of Stack - Ứng dụng ngăn xếp Data Structure and Algorithm 44
  45. Application of Stack - Ứng dụng ngăn xếp 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ữ: • 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 -Backtracking) • Khử đệ qui • Ứng dụng trong các bài toán tính toán biểu thức (Algebraic expressions) Data Structure and Algorithm 45
  46. Expression Notations Infix: Normal, use “()” 1 + 2 * 3 (4+5)*6 RPN (Postfix): Operator last, no “()” 1 2 3 * + 4 5 + 6 * Prefix: Operator first, no “()” + 1 * 2 3 * + 4 5 6 Data Structure and Algorithm 46
  47. Reverse Polish Notation (RPN) • RPN, also known as postfix notation, was invented by Australian philosopher and computer scientist Charles Hamblin in the mid-1950s. Data Structure and Algorithm 47
  48. Ví dụ 1 RPN • Hãy tính biểu thức sau đây: 1 + 4 * 3 = ? Kết quả là 13 hay 15? 13 – bởi theo thứ tự các phép tính Slide of Wanda M. Kunkle Data Structure and Algorithm 48
  49. Ví dụ 1 RPN • RPN chuyển các phép tính sang phải 1 + 4 * 3 1 4 3 * + • Thực hiện: 1. 1 4 3 * + 2. 1 12 + 3. 13 Data Structure and Algorithm 49
  50. Ví dụ 2 RPN • (4 + 5) / (1 + 2)  Chuyển sang RPN có dạng như thế nào? Data Structure and Algorithm 50
  51. Ví dụ 2 RPN • (4 + 5) / (1 + 2)  Chuyển sang RPN có dạng như thế nào? » 4 5 + 1 2 + / Data Structure and Algorithm 51
  52. Ví dụ 2 RPN • (4 + 5) / (1 + 2)  Chuyển sang RPN có dạng như thế nào? » 4 5 + 1 2 + / » 9 1 2 + / » 93 / » 3 Data Structure and Algorithm 52
  53. Ví dụ 3 RPN • [(4 + 5) * (2 + 3) + 6] / (8 + 7)  Chuyển sang RPN có dạng như thế nào? Data Structure and Algorithm 53
  54. Ví dụ 3 RPN • [(4 + 5) * (2 + 3) + 6] / (8 + 7)  Chuyển sang RPN có dạng như thế nào? » 4 5 + 2 3 + * 6 + 8 7 + / Data Structure and Algorithm 54
  55. Use Stack for Parsing RPN Expressions Sử dụng ngăn xếp trong RPN • Viết chương trình thực hiện 4 * (3 + 4) là khó. • Viết chương trình thực hiện 2 3 4 + * là dễ hơn.  Sử dụng Stack – ngăn xếp. Data Structure and Algorithm 55
  56. Use Stack for Parsing RPN Expressions Sử dụng ngăn xếp trong RPN • Chương trình tính RPN sử dụng ngăn xếp 2 3 4 + * 2 Data Structure and Algorithm 56
  57. Use Stack for Parsing RPN Expressions Sử dụng ngăn xếp trong RPN • Chương trình tính RPN sử dụng ngăn xếp 2 3 4 + * 3 2 2 Data Structure and Algorithm 57
  58. Use Stack for Parsing RPN Expressions Sử dụng ngăn xếp trong RPN • Chương trình tính RPN sử dụng ngăn xếp 2 3 4 + * 4 3 3 2 2 2 Data Structure and Algorithm 58
  59. Use Stack for Parsing RPN Expressions Sử dụng ngăn xếp trong RPN • Chương trình tính RPN sử dụng ngăn xếp 2 3 4 + * + 4 4 3 3 3 2 2 2 2 Data Structure and Algorithm 59
  60. Use Stack for Parsing RPN Expressions Sử dụng ngăn xếp trong RPN • Chương trình tính RPN sử dụng ngăn xếp 2 3 4 + * + 4 4 3 3 3 7 2 2 2 2 2 Data Structure and Algorithm 60
  61. Use Stack for Parsing RPN Expressions Sử dụng ngăn xếp trong RPN • Chương trình tính RPN sử dụng ngăn xếp 2 3 4 + * + * 4 4 3 3 3 7 7 2 2 2 2 2 2 Data Structure and Algorithm 61
  62. Use Stack for Parsing RPN Expressions Sử dụng ngăn xếp trong RPN • Chương trình tính RPN sử dụng ngăn xếp 2 3 4 + * + * 4 4 3 3 3 7 7 2 2 2 2 2 2 14 Data Structure and Algorithm 62
  63. Use Stack for Parsing RPN Expressions Sử dụng ngăn xếp trong RPN • Chương trình tính RPN sử dụng ngăn xếp 2 3 4 + * + * 4 4 3 3 3 7 7 2 2 2 2 2 2 14 Data Structure and Algorithm 63
  64. Use Stack for Parsing RPN Expressions Sử dụng ngăn xếp trong RPN • Chương trình tính RPN sử dụng ngăn xếp 2 3 4 + * + * 4 4 3 3 3 7 7 2 2 2 2 2 2 14 Data Structure and Algorithm 64
  65. Use Stack for Parsing RPN Expressions Sử dụng ngăn xếp trong RPN • Chương trình tính RPN sử dụng ngăn xếp 2 3 4 + * + * 4 4 3 3 3 7 7 2 2 2 2 2 2 14 Data Structure and Algorithm 65
  66. Use Stack for Parsing RPN Expressions Sử dụng ngăn xếp trong RPN • Chương trình tính RPN sử dụng ngăn xếp 2 3 4 + * + * 4 4 3 3 3 7 7 2 2 2 2 2 2 14 Data Structure and Algorithm 66
  67. Use Stack for Parsing RPN Expressions Sử dụng ngăn xếp trong RPN • Chương trình tính RPN sử dụng ngăn xếp 2 3 4 + * + * 4 4 3 3 3 7 7 2 2 2 2 2 2 14 Data Structure and Algorithm 67
  68. Thuật toán 2 ngăn xếp của Dijkstra • Thuật toán 2 ngăn xếp của Dijkstra Data Structure and Algorithm 68
  69. Discussion – Câu hỏi • structure-algorithm Data Structure and Algorithm 69