Stack – Ngăn xếp là một cấu trúc dữ liệu đơn giản được sử dụng để lưu trữ dữ liệu. Trong một ngăn xếp, thứ tự của dữ liệu là điều quan trọng. Ta có thể tưởng tượng một đống đĩa trong quán ăn tự phục vụ là một ví dụ điển hình về stack. Khi chúng ta thêm đĩa vào stack, chúng sẽ được đặt lên trên cùng và khi cần sử dụng, chúng sẽ được lấy từ trên cùng. Tấm đầu tiên được đặt trên stack sẽ là tấm cuối cùng được sử dụng.
Stack là một danh sách có thứ tự trong đó việc chèn và xóa được thực hiện ở một đầu, được gọi là đỉnh. Phần tử cuối cùng được chèn là phần tử đầu tiên sẽ bị xóa. Do đó, nó được gọi là Last in First out (LIFO) hoặc First in Last out (FILO) list. Khi một phần tử được chèn vào một stack, chúng ta gọi đó là thao tác “push” và khi một phần tử bị xóa khỏi stack, chúng ta gọi đó là thao tác “pop”. Việc cố gắng pop một stack trống sẽ gây ra một ngoại lệ gọi là “underflow” và việc cố gắng đẩy một phần tử vào một stack đầy sẽ gây ra một ngoại lệ gọi là “overflow”. (Bạn có thể thấy việc đặt tên Stack Overflow cho trang web nổi tiếng có lẽ xuất phát từ đây 😁) Khi xảy ra các trường hợp đặc biệt này, chúng ta gọi chúng là ngoại lệ.
Stack có nhiều ứng dụng quan trọng. Ví dụ như việc cân bằng ký hiệu, chuyển đổi từ trung tố sang hậu tố, tính toán biểu thức hậu tố, triển khai cuộc gọi hàm (bao gồm đệ quy), tìm các xấp xỉ trên thị trường chứng khoán, lịch sử duyệt trang trong trình duyệt web, hoàn tác trong trình soạn thảo văn bản, khớp thẻ trong HTML và XML, …
Có nhiều cách để triển khai Stack. Một trong những phương pháp phổ biến là sử dụng một mảng thông thường, một phương pháp khác là sử dụng một mảng động, và một phương pháp nữa là sử dụng danh sách liên kết.
Mỗi phương pháp triển khai Stack có những đặc điểm riêng và ứng dụng phù hợp. Triển khai Stack dựa trên mảng thông thường đơn giản nhưng có giới hạn về kích thước và gây tốn chi phí trong việc mở rộng. Triển khai Stack dựa trên mảng động giải quyết vấn đề về kích thước nhưng vẫn còn một số vấn đề về hiệu năng. Triển khai Stack dựa trên danh sách liên kết linh hoạt và dễ dàng mở rộng, nhưng đòi hỏi thêm không gian và thời gian để xử lý các tham chiếu.
Để hiểu rõ hơn về cấu trúc ngăn xếp và triển khai, bạn có thể tham khảo thêm tại dnulib.edu.vn.
