Phức hợp thời gian Stack
Cho thực thi dựa trên mảng của stack, các hoạt động push và pop lấy thời gian ổn định i.e.O(1) vì chỉ có một di
chuyển của con trỏ trong cả hai trường hợp.
Ứng dụng của cấu trúc dữ liệu Stack
Mặc dù stack là một cấu trúc dữ liệu đơn giản để thực thi, nó rất là mạnh mẽ. Các sử dụng phổ biến nhất của stack
là:
+ Đảo ngược một từ – Đặt tất cả các chữ trong một stack và lấy chúng ra. Vì trật tự LIFO của stack, bạn sẽ nhận các
chữ trong trật tự đảo ngược.
+ Trong các trình dịch – Các trình dịch sử dụng stack để tính toán giá trị của các biểu thức như 2 + 4 / 5 * (7 – 9)
bằng cách chuyển đổi biểu thức thành dạng có tiền tố hoặc hậu tố.
+ Trong các trình duyệt – Nút back trong một trình duyệt lưu tất cả các URLs bạn vừa ghé thăm trước kia trong stack.
Mỗi lần, bạn ghé thăm trong trang mới, nó được thêm vào đỉnh stack. Khi bạn ấn nút back, URL hiện tại được loại bỏ
từ stack và URL trước kia được truy cập.