So sánh việc triển khai Stack dựa trên mảng (Array) và dựa trên Linked List?

Có những khác biệt quan trọng giữa việc triển khai Stack dựa trên mảng và Linked List:

1. Độ phức tạp thời gian:

   • Dựa trên mảng: Thêm và xóa phần tử ở đỉnh Stack có thể là O(1) nếu có đủ không gian, nhưng nếu mảng đầy và cần phải thay đổi kích thước, thì thời gian có thể là O(n) vì việc sao chép dữ liệu sang mảng mới.
   • Dựa trên Linked List: Thêm và xóa phần tử ở đỉnh Stack thường là O(1) vì chỉ cần thay đổi con trỏ, không cần phải sao chép dữ liệu.

2. Khả năng mở rộng:

   • Dựa trên mảng: Có thể cần phải thay đổi kích thước mảng khi ...