Stack (Ngăn xếp)
Ngăn xếp (Stack) là một cấu trúc dữ liệu khá cơ bản trong lập trình, hoạt động theo nguyên tắc “LIFO” (Last-In-First-Out) - phần tử được thêm vào cuối cùng sẽ bị lấy ra đầu tiên. Vẫn mông lung nhỉ?
Quan sát hình phía dưới trong khoanh vùng màu đỏ, bạn chắc không xa lạ với 3 nút này ở góc trên, bên trái của trình duyệt. Trong đó có 2 nút go back và go forward. Mỗi nút này được cài đặt bằng một ngăn xếp đó, cụ thể (với nút go back):
- Mỗi webpage bạn từng truy cập sẽ được đưa vào ngăn xếp.
- Khi click go back, ngăn xếp sẽ trả ra (và xóa khỏi ngăn xếp) webpage gần nhất bạn từng truy cập.
Ngăn xếp (stack) là gì?
Trong khoa học máy tính, một ngăn xếp (còn gọi là bộ xếp chồng, tiếng Anh: Stack) là một cấu trúc dữ liệu trừu tượng hoạt động theo nguyên lý “vào sau ra trước” (Last In First Out (LIFO). Tức là, phần tử cuối cùng được chèn vào ngăn xếp sẽ là phần tử đầu tiên được lấy ra khỏi ngăn xếp.
Một ví dụ trực quan, bạn có một chồng sách và bạn để nó trong một cái hộp như hình phía dưới. Giả sử hộp này vừa khít các cuốn sách. Khi đó, bạn có các thao tác:
- Thêm một cuốn sách vào hộp (push)
- Lấy một cuốn sách khỏi hộp, bạn chỉ lấy được cuốn trên cùng(pop)
Như vậy, có 2 hành động duy nhất có thể thao tác với 1 ngăn xếp:
- Push: Thêm một phần tử vào đỉnh của ngăn xếp, và
- Pop: Lấy ra một phần tử đầu tiên ở đỉnh của ngăn xếp.
Chúng ta có thể có thêm các phương thức để kiểm tra kích thước của ngăn xếp:
- IsEmpty: Kiểm tra ngăn xếp trống hay không. Ngăn xếp trống là ngăn xếp không có phần tử nào.
- IsFull: Kiểm tra ngăn xếp đã đầy hay chưa. Thao tác này không phải lúc nào cũng có.
- Size: Lấy số lượng phần tử stack đang có.