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; ấ
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:
ả
c đ nh nghĩa ngăn
ượ
ị
Trình bày đ 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 p
ụ
ế
I/ Đ nh nghĩa
ị
ế
ừ ượ
ộ ấ
c th c hi n ệ ự c đ a vào ư
Stack (ngăn x p) là m t c u trúc tr u t theo c ch LIFO (Last In First Out): ph n t ế ngăn x p sau cùng s đ
ng, đ ượ đ ầ ử ượ c tiên.
c l y ra tr
ẽ ượ ấ
ơ ế
ướ
c cài đ t trên c s m ng (bao g m nhi u ph n
ượ
ơ ở ả
ề
ầ
ặ
ồ
- Stack đ .ử 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)
ọ
ẽ
ế
ế II/ Cài đ t Stack (ngăn x p)
ặ
và 1 bi n ch s top
ỉ ố
ế
S d ng m ng S đ ch a các ph n t ả đ 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;
1. Khai báo c u trúc ngăn x p ế ấ
ế 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);
}
vào ngăn x p (Stack) Đ a m t ph n t ộ ầ ử ư ế
void Push(stack &s, int x) {
s.top++; s.nodes[s.top]=x;
}
ra kh i ngăn x p (Stack) ấ ỏ ế
L y m t ph n t ầ ử ộ int Pop(stack &s) {
int x; x=s.nodes[s.top]; s.top --; return x;
}
BÀI T P Ậ
t ch ng trình áp d ng Stack ngăn x p đ đ i m t ươ ể ổ ế ộ
1. Vi ế s nguyên n ra d ng nh phân. ố ụ ị ạ
2. Có th áp d ng Stack (ngăn x p) đ kh đ qui. ử ệ ụ ế ể ể
