Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Th.S Thiều Quang Trung

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 kiểu ngăn xếp, hàng đợi, đệ quy trình bày 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.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Th.S Thiều Quang Trung 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