Bài 4.1. Giới thiệu về stack

Stack là một kiểu dữ liệu trừu tượng. Nó là một cấu trúc dữ liệu được sử dụng phổ biến trong ngôn ngữ lập trình để giải quyết nhiều vấn đề từ cơ bản đến phức tạp.
Ví dụ về stack: chồng sách, chồng bát đĩa hay bộ quân bài đang xếp chồng lên nhau.
Dùng để xử lý biểu thức: chuyển đổi biểu thức trung tố-hậu tố và tính toán các biểu thức phép toán.
Sử dụng trong các thuật toán như quay lui.
Sử dụng để lưu trữ các lời gọi chương trình trong máy tính…

Stack chỉ hỗ trợ các thao tác ở trên đầu nó theo nguyên tắc LIFO: last in first out – vào sau ra trước.
Phần tử đầu stack gọi là phần tử top.
Khi ta thao tác với các phần tử của nó, ta chỉ có thể thao tác với phần tử trên đầu stack.
Hành động chèn thêm phần tử vào đầu stack, gọi là push.
Hành động xóa phần tử ở đầu stack gọi là pop.
Stack có thể được triển khai bằng mảng, danh sách liên kết.

push(data) – thêm phần tử mới vào đầu stack.
pop() – xóa phần tử ở đầu stack.
peek() – lấy phần tử đầu stack nhưng không xóa nó khỏi stack.
isFull() – kiểm tra xem stack đã đầy chưa. Áp dụng với stack triển khai bằng mảng.
isEmpty() – kiểm tra xem stack có rỗng không.
Khi thực hiện thêm mới phần tử vào stack, ta thường kiểm tra xem stack còn chỗ chứa không(với biến thể cài đặt bằng mảng).
Khi ta lấy hoặc xóa phần tử đầu stack, ta thường kiểm tra xem stack có rỗng không trước khi thực hiện.