Bài giảng bài 1: Ngăn xếp (Stack)

Câu hỏi kiểm tra Trình bày cách khai báo một cấu trúc ? Trả lời typedef struct { ……………… ……………… } tên_cấu_trúc; Bài 1. NGĂN XẾP (STACK) CBGD: Trần Việt Khánh MỤC TIÊU Sau bài học này, sinh viên có khả năng: Trình bày được định nghĩa ngăn xếp (Stack)  Cài đặt được ngăn xếp  Vận dụng ngăn xếp vào các bài toán (đổi cơ số nhị phân, khử đệ qui,...) NỘI DUNG I/ Định nghĩa II/ Cài đặt Stack (ngăn xếp) Khai báo cấu trúc của một ngăn xếp Các tác vụ trên ngăn xếp I/ Định nghĩa Stack (ngăn xếp) là một cấu trúc trừu tượng, được thực hiện theo cơ chế LIFO (Last In First Out): phần tử được đưa vào ngăn xếp sau cùng sẽ được lấy ra trước tiên. - Stack được cài đặt trên cơ sở mảng (bao gồm nhiều phần tử. - Chỉ số top để chỉ định các phần tử trong danh sách. Hình vẽ minh họa ngăn xếp (Stack) Sử dụng mảng S để chứa các phần tử và 1 biến chỉ số top để chỉ định các phần tử trong mảng S. II/ Cài đặt Stack (ngăn xếp) 1. Khai báo cấu trúc ngăn xếp // Khai báo cấu trúc của một Stack typedef struct { int top; int nodes[MAXSIZE]; } stack; Khởi tạo ngăn xếp rỗng void CreateStack(stack &s) { s.top=-1; } 2. Các tác vụ trên Stack (ngăn xếp) Kiểm tra ngăn xếp có bị rỗng không bool EmptyStack(stack s) { return ( s.top == -1); } Đưa một phần tử vào ngăn xếp (Stack) void Push(stack &s, int x) { s.top++; s.nodes[s.top]=x; } Lấy một phần tử ra khỏi ngăn xếp (Stack) int Pop(stack &s) { int x; x=s.nodes[s.top]; s.top --; return x; } Viết chương trình áp dụng Stack ngăn xếp để đổi một số nguyên n ra dạng nhị phân. 2. Có thể áp dụng Stack (ngăn xếp) để khử đệ qui. BÀI TẬP