Bài giảng Cấu trúc dữ liệu và giải thuật: Ngăn xếp và hàng đợi cung cấp cho người học các kiến thức về ngăn xếp, cài đặt ngăn xếp, các ứng dụng của ngăn xếp, định giá biểu thức hậu tố, ngăn xếp thời gian chạy, cài đặt hàng đợi, . | Ngăn xếp và Hàng đợi Stacks and Queues Nguyễn Mạnh Hiển hiennm@ 2 Nội dung 1. Ngăn xếp 2. Hàng đợi 3 1. Ngăn xếp 4 Ngăn xếp Một danh sách các phần tử theo kiểu vào sau ra trước LIFO Last In First Out Ba thao tác chính xảy ra ở đỉnh ngăn xếp và chỉ mất thời gian O 1 push Thêm phần tử. pop Xóa phần tử. top Trả về phần tử. pop và top có thể kết hợp thành một thao tác Các thao tác khác Lấy kích thước Kiểm tra rỗng 5 Cài đặt ngăn xếp cách 1 Cài đặt bằng danh sách liên kết đơn head Cài đặt các thao tác push e Gọi thao tác pushFront e của DSLK đơn. pop Gọi thao tác popFront của DSLK đơn. top Gọi thao tác front của DSLK đơn. 6 Cài đặt ngăn xếp cách 2 Cài đặt bằng mảng 0 1 2 3 4 5 6 7 8 theArray 2 8 3 5 topOfStack 3 Cài đặt các thao tác push e topOfStack theArray topOfStack e pop topOfStack-- top return theArray topOfStack 7 Một số ứng dụng của ngăn xếp Cân bằng thẻ tag trong trang HTML Định giá biểu thức hậu tố Ngăn xếp lời gọi hàm xem trong sách 8 Cân bằng thẻ trong trang HTML Kiểm tra hai yêu cầu sau đây 1. Mỗi thẻ mở phải có thẻ đóng tương ứng something 2. Hai cặp thẻ khác nhau có thể lồng nhau nhưng không được bắt chéo nhau something OK something Lỗi 9 Ban đầu ngăn xếp rỗng 10 Gặp thẻ mở thêm nó vào ngăn xếp 11 Gặp thẻ mở thêm nó vào ngăn xếp 12 Gặp thẻ mở thêm nó vào ngăn xếp 13 Gặp nội dung không làm gì cả 14 Gặp thẻ đóng lấy một thẻ ra khỏi ngăn xếp xem có khớp nhau không 15 Gặp thẻ đóng lấy một thẻ ra khỏi ngăn xếp xem có khớp nhau không Khi đã quét hết trang HTML và ngăn xếp rỗng trang HTML là chuẩn 16 Định giá biểu thức hậu tố Giả sử phải định giá biểu thức trung tố sau 4 99 1 06 5 99 6 99 1 06 Máy tính khoa học sẽ cho kết quả 18 69 đúng. Máy tính giản đơn tính tuần tự từ trái sang phải sẽ cho kết quả 19 37 sai. Nếu viết lại biểu thức trên dưới dạng hậu tố toán tử nằm sau các toán hạng của nó rồi áp dụng ngăn xếp ta chỉ cần tính tuần tự từ trái sang phải mà không cần quan tâm độ ưu tiên của các toán tử 4 99 1 06 5 99 6 99 1 06 Có thể dùng ngăn xếp để .
