Tiểu Luận thảo luận cấu trúc dữ liệu và giải thuật, Đề tài: Ứng dụng của Stack- Ngăn xếp

Đề tài: Ứng dụng của Stack- Ngăn xếp
Phần I: Giới thiệu về ngăn xếp
1. Khái niệm
Ngăn xếp là một dạng đặc biệt của danh sách mà việc bổ sung hay loại bỏ một phần tử đều được thực hiện ở một đầu của danh sách gọi là đỉnh. Nói cách khác, ngăn xếp là một cấu trúc dữ liệu có 2 thao tác cơ bản: bổ sung (push) và loại bỏ (pop), trong đó loại bỏ sẽ tiến hành loại phần tử mới nhất được đưa vào danh sách. Chính vì tính chất này mà ngăn xếp còn được gọi kiểu dữ liệu có nguyên tắc LIFO (Last in first out – vào sau ra trước)
2. Các tác vụ trên ngăn xếp
a) Initialize
Chức năng: Khởi động ngăn xếp
Dữ liệu nhập: Không
Dữ liệu xuất: stack top về vị trí khởi đầu.
b) Empty
Chức năng kiểm tra ngăn xếp có bị rỗng không.
Dữ liệu nhập: Không
Dữ liệu xuất: True or False (True: khi ngăn xếp rỗng, False: ngăn xếp không bị rỗng).
c) Pusth
Chức năng: thêm nút mới tại đỉnh ngăn xếp
Dữ liệu nhập: nút mới.
Dữ liệu xuất: không
d) Pop
Chức năng: xóa nút tại đỉnh ngăn xếp.
Dữ liệu nhập: Không.
Điều kiện: stack không bị rỗng.
Dữ liệu xuất: nút bị xóa.
e) Stacktop:
Chức năng: truy xuất nút tại đỉnh ngăn xếp.
Dữ liệu nhập: Không.
Điều kiện: stack không bị rỗng.
Dữ liệu xuất: nút tại đỉnh ngăn xếp.
f) Stacksize
Chức năng: xác định số nút hiện có trong ngăn xếp.
Dữ liệu: Không.
Dữ liệu xuất: số nút hiện có trong ngăn xếp
g) Clearstack
Chức năng: xóa tất cả các nút ở trong ngăn xếp.
Dữ liệu nhập: không.
Dữ liệu xuất:stack top về vị trí khởi đầu.
h) Copystack:
Chức năng: copy ngăn xếp thành ngăn xếp mới.
Dữ liệu nhập: stack nguồn.
Dữ liệu xuất: ngăn xếp mới giống ngăn xếp cũ.

3. Phương pháp cài đặt ngăn xếp
Có rất nhiều cách cài đặt một ngăn xếp nhưng đơn giản cũng như để dễ hình dung nhất là cài đặt bằng mảng hay còn gọi là cài đặt theo kiểu kế tiếp. Ngoài ra còn nhiều cách cài đặt khác như cài đặt bằng Danh sách liên kết (DSLK đơn, DSLK vòng, DSLK kép, DSLK vòng+kép).