Cấu trúc dữ liệu ngăn xếp 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 | 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ữ | 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 tượng bất kỳ Bổ sung và lấy ra các phần tử theo kiểu “Vào sau ra trước” – “Last In First Out” Các phép toán chính: push(Object o): bổ sung đối tượng o vào Stack pop(): lấy ra và trả lại phần tử được bổ sung vào cuối cùng của Stack Các phép toán bổ trợ top() trả lại tham chiếu đến phần tử được bổ sung vào cuối cùng của Stack Size(): trả lại số phần tử hiện lưu trữ trong Stack isEmpty(): trả lại giá trị kiểu boolean để xác định Stack có lưu trữ phần tử nào hay không 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 tiếp Lưu lại các trang Web đã thăm trong một trình duyệt Thứ tự Undo trong một trình soạn thảo Lưu chữ các biến khi một hàm gọi tới hàm khác, và hàm được gọi lại gọi tới hàm khác, và cứ tiếp tục như
