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

Data Structure and Algorithm 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 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 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 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 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 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 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 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 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 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 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 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 push pop Slide of James Joshi Data Structure and Algorithm 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 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 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 16 Array Implementation of Stack Triển khai ngăn xếp bằng mảng Data Structure and Algorithm 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( ) • isEmpty( ) • isFull( ) • stackTop() top = 2 Data Structure and Algorithm 18 Push() and pop() operations stack empty stack empty Data Structure and Algorithm 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 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 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 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 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 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 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 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 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 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 29 Array Implementation of Stack – Triển khai ngăn xếp bằng mảng char stackTop() { //function to get top value if (isEmpty()) cout <<“Sorry, stack is empty!”<< endl; else return data[top]; } // end stackTop stackTop() : trả giá trị Data Structure and Algorithm 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 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 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 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 34 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 }; 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 35 • Creating a stack will initialize top to NULL - showing that currently, there is no node in the stack. • Is Empty() stack will return true if stack is empty, top is NULL. void stack::createStack() { top = NULL; } bool stack::isEmpty() { return (top == NULL); } 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 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 37 push() to empty stack STEP 1 : newnode-> next = head; STEP 2 : head = newnode; Data Structure and Algorithm 38 push()to non-empty stack STEP 1 : newnode-> next = head; STEP 2 : head = newnode; Data Structure and Algorithm 39 Push() operations void stack::push(int newitem) { // create newnode nodeStack *newnode; newnode = new (nodeStack); if( newnode == NULL) cout << “Cannot allocate memory” << endl; else // add to empty stack, or to front stack { newnode->data = newitem; newnode->next = head; head = newnode; }// end if } //end push operation Data Structure and Algorithm 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 41 Pop() operation void stack::pop() { nodeStack *delnode; if (isEmpty()) cout <<“Sorry, Cannot pop item from stack.Stack is still empty!” <<endl; else { delnode = head; cout << “Item to be popped from stack is: ” << stackTop()<<endl; head = delnode->next; delete(delnode); }// end else } // end pop Data Structure and Algorithm 42 Check item at top stack int stack::stackTop() { if (isEmpty()) cout <<“Sorry,Stack is still empty!” <<endl; else return head->data; } // end check item at top Data Structure and Algorithm 43 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() 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 44 Application of Stack - Ứng dụng ngăn xếp Data Structure and Algorithm 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 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 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 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 49 • 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 Ví dụ 1 RPN Data Structure and Algorithm 50 Ví dụ 2 RPN • (4 + 5) / (1 + 2) Chuyển sang RPN có dạng như thế nào? Data Structure and Algorithm 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 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 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 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 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 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 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 + * 2 3 2 Data Structure and Algorithm 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 + * 2 3 2 4 3 2 Data Structure and Algorithm 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 + * 2 3 2 4 3 2 4 3 2 + Data Structure and Algorithm 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 + * 2 3 2 4 3 2 4 3 2 7 2 + Data Structure and Algorithm 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 + * 2 3 2 4 3 2 4 3 2 7 2 7 2 + * Data Structure and Algorithm 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 + * 2 3 2 4 3 2 4 3 2 7 2 7 2 14 + * Data Structure and Algorithm 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 + * 2 3 2 4 3 2 4 3 2 7 2 7 2 14 + * Data Structure and Algorithm 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 + * 2 3 2 4 3 2 4 3 2 7 2 7 2 14 + * Data Structure and Algorithm 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 + * 2 3 2 4 3 2 4 3 2 7 2 7 2 14 + * Data Structure and Algorithm 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 + * 2 3 2 4 3 2 4 3 2 7 2 7 2 14 + * Data Structure and Algorithm 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 + * 2 3 2 4 3 2 4 3 2 7 2 7 2 14 + * Data Structure and Algorithm 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 69 Discussion – Câu hỏi • https://sites.google.com/site/daonamanhedu/data- structure-algorithm