tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Bài 7 - Hoàng Thị Điệp

Bài giảng "Cấu trúc dữ liệu và giải thuật - Bài 7: Hàng đợi" cung cấp cho người học các kiến thức cơ bản về hàng đợi, KDLTT hàng đợi, giao diện C++ của KDLTT hàng đợi, cài đặt hàng đợi bởi mảng,. nội dung chi tiết. | HK I, 2012-2013 Bài 6: Ngăn xếp Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Nguồn tham khảo chính: Tổng quan Cấu trúc dữ liệu Không tuyến tính Tuyến tính Truy cập ngẫu nhiên/trực tiếp diepht@vnu Truy cập tuần tự Tập hợp (Set) Thành phần đồng nhất Thành phần không đồng nhất Tổng quát Vào-trước-ratrước Vào-sau-ratrước Mảng (Array) Bản ghi (Record) Danh sách liên kết (List) Hàng đợi (Queue) Ngăn xếp (Stack) INT2203/w07 2 Ngăn xếp • Ngăn xếp là gì? – Là một danh sách nhưng các phép toán chỉ được thực hiện ở một đỉnh của danh sách. • Tính chất – Vào trước ra sau (First In Last Out: FILO) diepht@vnu INT2203/w07 3 KDLTT ngăn xếp • Trừu tượng hóa cấu trúc ngăn xếp Đặc tả dữ liệu – A = (a0, a1, , an) trong đó an là đỉnh ngăn xếp – Đặc tả các phép toán 1. Thêm phần tử x vào đỉnh ngăn xếp: push(x) 2. Loại phần tử ở đỉnh ngăn xếp: pop() 3. Kiểm tra ngăn xếp có rỗng hay không: isEmpty() 4. Kiểm tra ngăn xếp có đầy hay không: isFull() 5. Đếm số phần tử của ngăn xếp: size() 6. Trả về phần tử ở đỉnh ngăn xếp: top() diepht@vnu INT2203/w07 4 Giao diện C++ của KDLTT ngăn xếp template class Stack { public: int size(); bool isEmpty(); Object& top() throw(EmptyStackException); void push(Object o); Object .