Stack [ngăn xếp] là một cấu trúc dữ liệu danh sách, trong đó việc thêm và lấy các phần tử được thực hiện theo quy tắc FILO [Fist-In/Last-Out], có nghĩa là phần tử nào được đưa vào đầu tiên thì sẽ được lấy ra sau cùng. Nguyên tắc này cũng được gọi là LIFO [Last-IN/First-Out], có nghĩa là phần tử nào được đưa vào sau cùng thì sẽ được lấy ra trước tiên.
Hãy tưởng tượng cấu trúc stack như một ngăn bàn chật hẹp, trong đó các đồ vật được đưa vào lần lượt, đồ vật nào được đưa vào trước thì nằm ở trong cùng, đồ vật nào được đưa vào sau thì nằm ở bên ngoài. Như vậy, khi lấy các đồ vật ra thì chúng ta phải lấy các đồ vật ở bên ngoài trước, rồi lần lượt như vậy cho đến khi lấy được các đồ vật ở bên trong.
Các thao tác của Stack
Các thao tác thông dụng của Stack bao gồm:
- init – create the stack.
- push – add an item to the top of the stack.
- pop – remove the last item added to the top of the stack.
- top – look at the item on the top of the stack without removing it.
- isEmpty – return whether the stack contains no more items.
Chúng ta cũng có thể đặt ra một giới hạn số lượng phần tử cho Stack, khi có nhiều hơn số lượng phần tử được thêm vào trong Stack thì sẽ tung ra một thông báo rằng đã bị “tràn” so với dung lượng đang có. Đến đây, chúng ta nhớ đến tại sao lại có trang web tên là “Stack Overflow” để dành cho các Lập trình viên hỗ trợ nhau trong trường hợp bị “tràn” bộ nhớ.
Triển khai Stack
Sau đây là một triển khai đơn giản của cấu trúc Stack: