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

Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com Cấu trúc dữ liệu và giải thuật Bài 9: Ngăn xếp - Stacks PhD Ngo Huu Phuc, Le Quy Don Technical University1 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ồng PhD Ngo Huu Phuc, Le Quy Don Technical University2 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. PhD Ngo Huu Phuc, Le Quy Don Technical University3 9.1. Khái niệm về stacks (2/7) PhD Ngo Huu Phuc, Le Quy Don Technical University4 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. PhD Ngo Huu Phuc, Le Quy Don Technical University5 9.1. Khái niệm về stacks (3/7) PhD Ngo Huu Phuc, Le Quy Don Technical University6 9.1. Khái niệm về stacks (4/7) Có 3 thao tác chính của stack:  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ì? PhD Ngo Huu Phuc, Le Quy Don Technical University7 Push Pop 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. PhD Ngo Huu Phuc, Le Quy Don Technical University8 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. PhD Ngo Huu Phuc, Le Quy Don Technical University9 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  MakeEmpty PhD Ngo Huu Phuc, Le Quy Don Technical University10 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; PhD Ngo Huu Phuc, Le Quy Don Technical University11 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. PhD Ngo Huu Phuc, Le Quy Don Technical University12 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] = stack[0] + 1; stack[stack[0]] = value; } else { printf("Khong the them vao STACK\n"); getch(); } } PhD Ngo Huu Phuc, Le Quy Don Technical University13 9.2. Thao tác cơ bản của stack (4/9) Thao tác Pop (item: ItemType)  Chức năng: Lấy phần tử ở đỉnh của Stack và trả lại cho lời gọi hàm.  Điều kiện: Stack đã được khởi tạo và không rỗng.  Kết quả: Phần tử ở đỉnh của Stack được trả lại cho lời gọi hàm và số phần tử trong Stack giảm đi 1. PhD Ngo Huu Phuc, Le Quy Don Technical University14 9.2. Thao tác cơ bản của stack (5/9) Ví dụ về hàm pop: int pop(int stack[]) { int value; if(stack[0] > 0 ) { value = stack[stack[0]]; stack[0] = stack[0] - 1; } else { printf("STACK rong\n"); value = -32768; } return value; } PhD Ngo Huu Phuc, Le Quy Don Technical University15 9.2. Thao tác cơ bản của stack (7/9) Thao tác Peek:  Chức năng: Lấy giá trị tại đỉnh của Stack nhưng không loại phần tử ở đỉnh của Stack.  Điều kiện: Stack đã được khởi tạo và không rỗng.  Kết quả: Giá trị tại đỉnh của Stack được trả về cho lời gọi hàm, Stack không thay đổi. PhD Ngo Huu Phuc, Le Quy Don Technical University16 9.2. Thao tác cơ bản của stack (8/9) Ví dụ về hàm Peek int peek(int stack[]) { if(stack[0]>0) return stack[stack[0]]; else { printf("STACK rong\n"); return -32768; } } PhD Ngo Huu Phuc, Le Quy Don Technical University17 9.3. Các thao tác khác của stacks (1/9)  Thao tác isEmpty: Kiểm tra xem Stack có rỗng không?  Thao tác isFull: Kiểm tra xem Stack đã đầy chưa?  Thao tác makeEmpty: Làm rỗng Stack.  Xây dựng hàm Push sử dụng thao tác isFull.  Xây dựng hàm Pop sử dụng thao tác isEmpty.  Xây dựng hàm Peek sử dụng thao tác isEmpty. PhD Ngo Huu Phuc, Le Quy Don Technical University18 9.3. Các thao tác khác của stacks (2/9) Thao tác isEmpty:  Kiểm tra xem Stack có rỗng không?  Nếu rỗng hàm trả về 1, nếu không hàm trả về 0. int isEmpty(int stack[]) { if(stack[0]==0) return 1; else return 0; } PhD Ngo Huu Phuc, Le Quy Don Technical University19 9.3. Các thao tác khác của stacks (3/9) Thao tác isFull:  Kiểm tra xem Stack đã đầy chưa?  Nếu đã đầy, hàm trả về 1; nếu chưa đầy, hàm trả về 0. int isFull(int stack[]) { if(stack[0]==MAXSIZE-1) return 1; else return 0; } PhD Ngo Huu Phuc, Le Quy Don Technical University20 9.3. Các thao tác khác của stacks (4/9) Thao tác makeEmpty:  Làm rỗng Stack.  Đưa số phần tử trong Stack về 0. void makeEmpty(int stack[]) { stack[0]=0; } PhD Ngo Huu Phuc, Le Quy Don Technical University21 9.3. Các thao tác khác của stacks (5/9) Xây dựng hàm Push sử dụng thao tác isFull: void push2(int stack[], int value) { if(!isFull(stack)) { stack[0] = stack[0] + 1; stack[stack[0]] = value; } else { printf("Khong the them vao STACK\n"); getch(); } } PhD Ngo Huu Phuc, Le Quy Don Technical University22 9.3. Các thao tác khác của stacks (6/9) Xây dựng hàm Pop sử dụng thao tác isEmpty. int pop2(int stack[]) { int value; if(!isEmpty(stack)) { value = stack[stack[0]]; stack[0] = stack[0] - 1; } else { printf("STACK rong\n"); value = -32768; } return value; } PhD Ngo Huu Phuc, Le Quy Don Technical University23 9.3. Các thao tác khác của stacks (8/9) Xây dựng hàm Peek sử dụng thao tác isEmpty. int peek2(int stack[]) { if(!isEmpty(stack)) return stack[stack[0]]; else { printf("STACK rong\n"); return -32768; } } PhD Ngo Huu Phuc, Le Quy Don Technical University24