Vậy Stack là gì và có những thao tác cơ bản nào? Hãy cùng tìm hiểu chi tiết trong bài viết dưới đây.
1. Stack là gì?
Stack (ngăn xếp) là cấu trúc dữ liệu cho phép thêm và lấy phần tử thông qua một đầu duy nhất, thường được gọi là Top (đỉnh ngăn xếp).
Stack hoạt động theo nguyên tắc LIFO (Last In, First Out). Điều này có nghĩa phần tử được đưa vào cuối cùng sẽ là phần tử được lấy ra đầu tiên.
Ví dụ, khi xếp các quyển sách chồng lên nhau, bạn thường phải lấy quyển sách trên cùng ra trước. Các phần tử trong Stack cũng hoạt động tương tự như vậy.
<AsyncImage query="stack data structure LIFO push pop top clear educational diagram" aspectRatio="16:9" width="100%" />
2. Những thao tác cơ bản trên Stack
Stack cung cấp một số thao tác cơ bản để quản lý và truy xuất dữ liệu.
2.1. Push – Thêm phần tử
Push là thao tác đưa một phần tử mới vào đỉnh Stack. Sau khi thêm, phần tử vừa được đưa vào sẽ trở thành phần tử ở vị trí Top.
Ví dụ: Stack đang có các phần tử A, B. Khi thực hiện Push(C), Stack sẽ có thứ tự A, B, C và C nằm trên cùng.
2.2. Pop – Lấy phần tử
Pop là thao tác loại bỏ phần tử nằm trên cùng của Stack. Phần tử được lấy ra chính là phần tử được thêm vào gần nhất.
Ví dụ: Stack đang có A, B, C. Khi thực hiện Pop(), phần tử C sẽ bị loại bỏ, Stack chỉ còn A và B.
Nếu Stack không có phần tử nào mà vẫn thực hiện Pop, chương trình có thể phát sinh lỗi Underflow nếu không kiểm tra trước.
2.3. Peek – Xem phần tử trên cùng
Peek cho phép xem giá trị của phần tử nằm ở đỉnh Stack mà không xóa phần tử đó.
Ví dụ: Stack có các phần tử A, B, C. Khi thực hiện Peek(), kết quả trả về là C nhưng Stack vẫn giữ nguyên dữ liệu.
2.4. IsEmpty – Kiểm tra Stack rỗng
IsEmpty được sử dụng để xác định Stack có đang chứa phần tử nào hay không.
Thao tác này thường được sử dụng trước khi gọi Pop hoặc Peek để tránh lỗi khi Stack rỗng.
2.5. IsFull – Kiểm tra Stack đầy
IsFull dùng để kiểm tra Stack đã đạt đến giới hạn dung lượng hay chưa. Thao tác này thường áp dụng với Stack được triển khai bằng mảng có kích thước cố định.
Nếu Stack được triển khai bằng cấu trúc dữ liệu có khả năng mở rộng như danh sách liên kết, việc kiểm tra đầy thường không cần thiết theo cách tương tự.
3. Cách triển khai Stack trong lập trình
Stack có thể được xây dựng bằng nhiều phương pháp khác nhau, phổ biến nhất là sử dụng mảng hoặc danh sách liên kết.
3.1. Triển khai Stack bằng mảng
Với phương pháp này, các phần tử được lưu trữ trong một mảng và sử dụng biến Top để xác định vị trí phần tử trên cùng.
Ưu điểm:
Nhược điểm:
3.2. Triển khai Stack bằng danh sách liên kết
Danh sách liên kết sử dụng các Node để lưu trữ dữ liệu. Mỗi Node chứa giá trị và liên kết đến Node tiếp theo.
Khi thêm hoặc xóa phần tử, chương trình thao tác trực tiếp tại Node đầu danh sách.
Ưu điểm:
Nhược điểm:
4. Ứng dụng thực tế của Stack
Stack được sử dụng trong nhiều bài toán lập trình và ứng dụng thực tế:
5. Độ phức tạp của các thao tác trên Stack
Đối với cách triển khai Stack thông thường bằng mảng hoặc danh sách liên kết, độ phức tạp của các thao tác cơ bản như sau:
|
Thao tác |
Độ phức tạp |
|
Push |
O(1) |
|
Pop |
O(1) |
|
Peek |
O(1) |
|
IsEmpty |
O(1) |
|
IsFull |
O(1) |
Các thao tác trên thường có độ phức tạp thời gian O(1) vì chỉ cần truy cập hoặc thay đổi phần tử ở đỉnh Stack.