tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp

Bài giảng "Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp" cung cấp cho người học các kiến thức: Stack, các vấn đề cần nghiên cứu, cấu trúc dữ liệu trừu tượng, cấu trúc dữ liệu trừu tượng Stack,. . | Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp Bài 8. Cấu trúc dữ liệu ngăn xếp Stack Stack là cách tổ chức lưu trữ các đối tượng dưới dạng một danh sách tuyến tính mà việc bổ sung đối tượng và lấy các đối tượng ra được thực hiện ở cùng một đầu của danh sách. Stack được gọi là danh sách kiểu LIFO (Last In First Out - vào sau ra trước) Các vấn đề cần nghiên cứu Cấu trúc dữ liệu trừu tượng Stack (ADT Stack) Những ứng dụng của Stack Cài đặt Stack dựa trên mảng Sự phát triển stack dựa trên mảng Cấu trúc dữ liệu trừu tượng (ADT- Abtract Data Type) Các thành phần của một ADT Dữ liệu được lưu trữ Các phép toán trên dữ liệu Các điều kiện xảy ra lỗi kết hợp với các phép toán Ví dụ: Mô hình ADT của một hệ thống kho hàng đơn giản - Dữ liệu được lưu trữ theo phiếu mua/bán - Các phép toán: + Hóa đơn buy(kho, số lượng, giá) + Hóa đơn sell(kho, số lượng, giá) + void cancel(Số hóa đơn) //Số hóa đơn Điều kiện lỗi: - Mua/bán một mặt hàng không có trong kho - Hủy bỏ một phiếu mà phiếu không tồn tại Cấu trúc dữ liệu trừu tượng Stack Stack ADT lưu trữ các đối Các phép toán bổ trợ tượng bất kỳ top() trả lại tham chiếu đến Bổ sung và lấy ra các phần phần tử được bổ sung vào tử theo kiểu “Vào sau ra cuối cùng của Stack trước” – “Last In First Out” size(): trả lại số phần tử Các phép toán chính: hiện lưu trữ trong Stack push(Object o): bổ sung đối isEmpty(): trả lại giá trị kiểu tượng o vào Stack boolean để xác định Stack pop(): lấy ra và trả lại phần có lưu trữ phần tử nào hay tử được bổ sung vào cuối không cùng của Stack Các trường hợp ngoại lệ Ngoại lệ: là việc thực hiện một phép toán mà trong trường hợp đó nó không thể thực hiện Với Stack ADT thì phép toán pop và top không thể thực hiện được nếu Stack rỗng Khi thực hiện phép toán pop hoặc top trên một Stack rỗng thi dẫn đễn ngoại lệ Stack rỗng Một số ứng dụng của Stack Các ứng dụng trực