Xem mẫu
CHƯƠNG 5
KIỂU NGĂN XẾP, HÀNG ĐỢI, ĐỆ QUY
GV Th.S. Thiều Quang Trung
Bộ môn Khoa học cơ bản
Trường Cao đẳng Kinh tế Đối ngoại
Nội dung
1
2
3
4
5
6
• Khái niệm ngăn xếp
• Phương pháp xây dựng stack
• Các thao tác cơ bản trên stack
• Kiểu queue - hàng đợi
• Các thao tác cơ bản trên queue
• Đệ qui và các bài toán đệ qui
GV. Thiều Quang Trung
2
Ngăn xếp - Định nghĩa
• Stack là 1 cấu trúc:
– Gồm nhiều phần tử
– Hoạt động theo cơ chế “Vào sau – Ra trước”
(LIFO – Last In, First Out)
Đỉnh
ngăn
xếp
GV. Thiều Quang Trung
3
Thao tác cơ bản trên Stack
•
•
•
•
•
InitStack: khởi tạo Stack rỗng
IsEmpty: kiểm tra Stack rỗng?
Push
IsFull: kiểm tra Stack đầy?
Push: thêm 1 phần tử vào Stack
Pop: lấy ra 1 phần tử khỏi Stack
GV. Thiều Quang Trung
Pop
4
PUSH
Thao tác thêm - Push vào Stack
Top
GV. Thiều Quang Trung
5
nguon tai.lieu . vn
KIỂU NGĂN XẾP, HÀNG ĐỢI, ĐỆ QUY
GV Th.S. Thiều Quang Trung
Bộ môn Khoa học cơ bản
Trường Cao đẳng Kinh tế Đối ngoại
Nội dung
1
2
3
4
5
6
• Khái niệm ngăn xếp
• Phương pháp xây dựng stack
• Các thao tác cơ bản trên stack
• Kiểu queue - hàng đợi
• Các thao tác cơ bản trên queue
• Đệ qui và các bài toán đệ qui
GV. Thiều Quang Trung
2
Ngăn xếp - Định nghĩa
• Stack là 1 cấu trúc:
– Gồm nhiều phần tử
– Hoạt động theo cơ chế “Vào sau – Ra trước”
(LIFO – Last In, First Out)
Đỉnh
ngăn
xếp
GV. Thiều Quang Trung
3
Thao tác cơ bản trên Stack
•
•
•
•
•
InitStack: khởi tạo Stack rỗng
IsEmpty: kiểm tra Stack rỗng?
Push
IsFull: kiểm tra Stack đầy?
Push: thêm 1 phần tử vào Stack
Pop: lấy ra 1 phần tử khỏi Stack
GV. Thiều Quang Trung
Pop
4
PUSH
Thao tác thêm - Push vào Stack
Top
GV. Thiều Quang Trung
5