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

"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 9: Ngăn xếp - Stacks" thông tin đến các bạn kiến thức về khái niệm về stacks, các thao tác chính của stacks, các thao tác khác của stacks.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 9: Ngăn xếp - Stacks Cấu trúc dữ liệu và giải thuật Bài 9: Ngăn xếp - Stacks Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com1 PhD Ngo Huu Phuc, Le Quy Don Technical University Bài 9. Ngăn xếp Nội dung: 9.1. Khái niệm về stacks (7) 9.2. Các thao tác chính của stacks (9) 9.3. Các thao tác khác của stacks (9) Tham khảo: 1. Data structures and Algorithms Stacks.htm 2. Kyle Loudon Mastering Algorithms, Chapter 6 Stacks and Queues 3. Elliz Horowitz – Fundamentals of Data Structures, Chapter 3 Stacks and Queues 4. Deshpande Kakle – C and Data Structures, Chapter 19. Stacks and Queues 5. Bài giảng TS Nguyễn Nam Hồng2 PhD Ngo Huu Phuc, Le Quy Don Technical University 9.1. Khái niệm về stacks (1/7)  Có thể hình dung stack như một chồng đĩa. Với chồng đĩa này, có thể nhìn thấy chiếc đĩa ở trên cùng, các đĩa còn lại chưa nhìn thấy được.  Khi thêm một đĩa vào chồng đĩa (pushed), chiếc đĩa này ở đỉnh của stack, có thể nhìn thấy.  Khi lấy di một đĩa từ stack (popped), có thể sử dụng đĩa này, chiếc đĩa kế tiếp trở thành đỉnh của stack.3 PhD Ngo Huu Phuc, Le Quy Don Technical University 9.1. Khái niệm về stacks (2/7)4 PhD Ngo Huu Phuc, Le Quy Don Technical University 9.1. Khái niệm về stacks (3/7)  Nguyên lý cơ bản của stack là Last In First Out (LIFO), có nghĩa vào sau ra trước.  Với nguyên lý đó, chỉ có chiếc đĩa trên cùng stack mới có thể nhìn thấy. Muốn nhìn thấy chiếc đĩa thứ 3, cần lấy ra khỏi stack các đĩa thứ nhất và thứ 2.5 PhD Ngo Huu Phuc, Le Quy Don Technical University 9.1. Khái niệm về stacks (3/7)6 PhD Ngo Huu Phuc, Le Quy Don Technical University 9.1. Khái niệm về stacks (4/7) Có 3 thao tác chính của stack: Push Pop  Push Đưa một phần tử vào đỉnh của stack.  Pop Lấy từ đỉnh của stack một phần tử.  Peek Xem đỉnh của stack chứa nội dung là gì?7 PhD Ngo Huu Phuc, Le Quy Don Technical University 9.1. Khái niệm về stacks (5/7) Một số ứng dụng của stack:  Ứng dụng trực tiếp:  Ứng dụng nổi bật của stack là stack cho chương trình, chương trình sử dụng stack để gọi hàm.  Trong trình duyệt WEB, các trang đã xem được lưu trong stack.  Trong trình soạn thảo văn bản, thao tác Undo được lưu trong stack.  Ứng dụng gián tiếp:  Cấu trúc dữ liệu bổ trợ cho thuật toán khác.  Một thành phần của cấu trúc dữ liệu khác.8 PhD Ngo Huu Phuc, Le Quy Don Technical University 9.1. Khái niệm về stacks (6/7) Thực thi và giới hạn của stack.  Thực thi.  Gọi n là số ô nhớ cho stack.  Không gian có thể sử dụng đối với stack là O(n).  Với mỗi thao tác, độ phức tạp là O(1)  Giới hạn.  Kích thước tối đa của stack được định nghĩa trước, không thể thay đổi (nếu dùng mảng).  Nếu stack đã đầy, không PUSH được phần tử mới vào stack. Nếu stack rỗng, thao tác POP cho kết quả rỗng.9 PhD Ngo Huu Phuc, Le Quy Don Technical University 9.1. Khái niệm về stacks (7/7) Đối với stack cần:  Định nghĩa stack:  MAXSIZE: Số phần tử tối đa của stack (nếu dùng mảng).  ItemType: Kiểu dữ liệu cho stack.  Thao tác chính:  Push  Pop  Peek  Thao tác khác:  IsEmpty  IsFull  MakeEmpty10 PhD Ngo Huu Phuc, Le Quy Don Technical University 9.2. Thao tác cơ bản của stack (1/9)  Trước hết, định nghĩa kích thước cho stack: Ví dụ: #define MAXSIZE 100  Có thể sử dụng stack để lưu bất kỳ kiểu dữ liệu nào, do đó cần định nghĩa kiểu dữ liệu cho stack: Ví dụ: int stack[MAXSIZE];  Có thể dùng một con trỏ để xác định đỉnh của stack hoặc đơn giản hơn, dùng phần tử mảng đầu tiên của stack để lưu số phần đã có trong stack: Ví dụ: stack[0] = 0;11 PhD Ngo Huu Phuc, Le Quy Don Technical University 9.2. Thao tác cơ bản của stack (2/9) Thao tác Push (newItem: ItemType)  Chức năng: Thêm một phần tử vào đỉnh của Stack.  Điều kiện thực hiện: Stack đã được khởi tạo và chưa đầy.  Kết quả: Nếu thêm thành công, newItem sẽ ở đỉnh của Stack.12 PhD Ngo Huu Phuc, Le Quy Don Technical University 9.2. Thao tác cơ bản của stack (3/9) Ví dụ về hàm push: void push(int stack[], int value) { if(stack[0] < MAXSIZE-1 ) { stack[0] = ...