Ngăn xếp (Stack) là cấu trúc dữ liệu LIFO (Last In First Out). Có ứng dụng quan trọng:
- Xử lý biểu thức (Expression Handling)
- Chuyển trung tố sang hậu tố hoặc tiền tố (Infix to Postfix/Prefix) − Ngăn xếp dùng để chuyển đổi. Biểu thức hậu tố/tiền tố dùng trong máy tính, không cần thứ tự toán tử và ngoặc.
- Đánh giá hậu tố/tiền tố (Postfix/Prefix Evaluation) − Sau chuyển đổi, cần đánh giá biểu thức để ra kết quả, cũng cần ngăn xếp.
- Thủ tục Quay lui (Backtracking) − Quay lui là kỹ thuật thiết kế thuật toán. Đi vào một đường, nếu không hiệu quả, quay lại trạng thái trước. Cần lưu trạng thái trước → dùng ngăn xếp. Ví dụ: Mã di tuân, N hậu.
- Gọi hàm và trả về (Function call and return) − Khi gọi hàm từ hàm khác, lưu địa chỉ program counter vào ngăn xếp, nhảy vào hàm. Sau khi xong, lấy địa chỉ ra gán vào program counter để tiếp tục.