Bài giảng Cấu trúc dữ liệu: Chương 5 - ThS. Thiều Quang Trung (2018)

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