Bài 1: Ngăn xếp (Stack)

Sau bài học này, sinh viên cókhả năng:.Trình bày được định nghĩa ngănxếp (Stack).Cài đặt được ngăn xếp. Vận dụng ngăn xếp vào các bàitoán (đổi cơ số nhị phân, khử đệqui,...)
Nội dung trích xuất từ tài liệu:
Bài 1: Ngăn xếp (Stack) Câu hỏi kiểm traTrì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;Bai 1. NGĂN XẾP (STACK) ̀ CBGD: Trần Việt Khánh • 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)MỤC TIÊU  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,...) I/ Định nghĩa II/ Cài đặt Stack (ngăn xếp)NỘI DUNG 1. Khai báo cấu trúc của một ngăn xếp 2. Các tác vụ trên ngăn xếpI/ Định nghĩaStack (ngăn xếp) là một cấu trúc trừu tượng, được thực hiệntheo cơ chế LIFO (Last In First Out): phần tử được đưa vàongă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ầntử.- 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) II/ Cài đặt Stack (ngăn xếp) 1. Khai báo cấu trúc ngăn xếpSử 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. // Khai báo cấu trúc của một Stack typedef struct { int top; int nodes[MAXSIZE]; } stack; 2. Các tác vụ trên Stack (ngăn xếp)• Khởi tạo ngăn xếp rỗng void CreateStack(stack &s) { s.top=-1; }• 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; } BÀI TẬP1. 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.