"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 10: Ứng dụng của ngăn xếp" với những kiến thức đảo mảng, đảo chuỗi, chuyển đổi hệ số, bracket matching, balancing ACT. | Cấu trúc dữ liệu và giải thuật Bài 10 Ứng dụng của ngăn xếp Giảng viên TS. Ngo Huu Phuc Tel 0438 326 077 Mob 098 5696 580 Email ngohuuphuc76@ 1 PhD. Ngo Huu Phuc Le Quy Don Technical University Bài 10. Một vài ứng dụng của Stack Nội dung . Đảo mảng 3 . Đảo chuỗi 4 . Chuyển đổi hệ số 9 . Bracket Matching 5 . Balancing Act 4 Tham khảo 1. Data structures and Algorithms 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ồng 2 PhD. Ngo Huu Phuc Le Quy Don Technical University . Đảo mảng 1 3 Cho một mảng gồm một dãy các giá trị. Để đảo thứ tự các phần tử trong mảng sử dụng nguyên lý Last-In-First-Out của Stack. Ví dụ về hoạt động của đảo mảng 17 18 134 216 23 25 47 55 25 23 55 47 18 17 216 134 3 PhD. Ngo Huu Phuc Le Quy Don Technical University . Đảo mảng 2 3 Ý tưởng thực hiện giải thuật 1. Khởi tạo một Stack rỗng có kiểu số. 2. Với n phần tử của mảng lần lượt đưa vào Stack thông qua hàm Push Push a i in to Stack. 3. Lần lượt lấy ra từ Stack n phần tử và đưa vào trở lại mảng ban đầu Pop a item from nStack in to a i . 4. Kết thúc giải thuật. 4 PhD. Ngo Huu Phuc Le Quy Don Technical University . Đảo mảng 3 3 Ví dụ về đảo mảng void revArray int a int n int stack makeEmpty stack for int i 0 i . Đảo chuỗi 1 4 Cho một chuỗi gồm nhiều từ. Đảo chuỗi thực hiện việc đảo các từ trong chuỗi sử dụng ý tưởng Last-In-First-Out của Stack. Ví dụ về đảo chuỗi Tôi Tập Chăm Giỏi Làm Bài Học Thì Bài Làm Thì Học Tập Tôi Giỏi Chăm 6 PhD. Ngo Huu Phuc Le Quy Don Technical University . Đảo chuỗi 2 4 Ý tưởng xây dựng chương trình 1. Tạo một wStack rỗng. 2. Với mỗi từ mWord đọc được từ string đưa từ đó vào Stack Push mWord into wStack. 3. Đọc từ wStack cho đến hết thực hiện Pop a word from wStack into mWord. Concate mWord to the end of outp string. 4.
