Tóm tắt¶

Điểm lại trọng tâm¶

Ngăn xếp là một cấu trúc dữ liệu tuân theo nguyên lý LIFO và có thể được triển khai bằng mảng hoặc danh sách liên kết.
Về mặt hiệu suất thời gian, cách triển khai ngăn xếp bằng mảng có hiệu suất trung bình cao hơn, nhưng khi mở rộng mảng, độ phức tạp thời gian của một thao tác đẩy vào sẽ giảm xuống thành \(O(n)\). Ngược lại, cách triển khai ngăn xếp bằng danh sách liên kết mang lại hiệu suất ổn định hơn.
Về mặt hiệu suất không gian, cách triển khai ngăn xếp bằng mảng có thể dẫn đến mức độ lãng phí không gian nhất định. Tuy nhiên, cần lưu ý rằng không gian bộ nhớ bị chiếm dụng bởi các nút danh sách liên kết lớn hơn so với các phần tử của mảng.
Hàng đợi là một cấu trúc dữ liệu tuân theo nguyên lý FIFO và cũng có thể được triển khai bằng mảng hoặc danh sách liên kết. Các kết luận so sánh về hiệu suất thời gian và hiệu suất không gian đối với hàng đợi tương tự như đối với ngăn xếp đã đề cập ở trên.
Hàng đợi hai đầu là một hàng đợi có tính linh hoạt cao hơn, cho phép thêm và loại bỏ các phần tử ở cả hai đầu.

Q & A¶

Q: Tính năng quay lại (backward) và tiến tới (forward) của trình duyệt có được triển khai bằng danh sách liên kết đôi không?

Hành vi quay lại và tiến tới của trình duyệt thực chất là một ứng dụng của "ngăn xếp". Khi người dùng truy cập một trang mới, trang đó sẽ được thêm vào đỉnh ngăn xếp; khi người dùng nhấp vào nút quay lại, trang đó sẽ được lấy ra từ đỉnh ngăn xếp. Hàng đợi hai đầu có thể hỗ trợ một số thao tác bổ sung một cách thuận tiện, như đã đề cập trong phần "Hàng đợi hai đầu".

Q: Sau khi lấy ra khỏi ngăn xếp, chúng ta có cần giải phóng bộ nhớ của nút được lấy ra không?

Nếu nút được lấy ra vẫn cần thiết sau này, thì không cần giải phóng bộ nhớ. Nếu nó không được sử dụng sau đó, các ngôn ngữ như Java và Python có cơ chế tự động thu gom rác (garbage collection), nên không yêu cầu giải phóng bộ nhớ thủ công; còn trong C và C++, việc giải phóng bộ nhớ thủ công là cần thiết.

Q: Hàng đợi hai đầu trông giống như hai ngăn xếp được ghép lại với nhau. Mục đích của nó là gì?

Hàng đợi hai đầu giống như sự kết hợp của một ngăn xếp và một hàng đợi, hoặc hai ngăn xếp được ghép lại với nhau. Nó kết hợp logic của cả hai, do đó có thể hỗ trợ tất cả các ứng dụng của ngăn xếp và hàng đợi đồng thời mang lại tính linh hoạt cao hơn.

Q: Hoàn tác (undo) và làm lại (redo) được triển khai cụ thể như thế nào?

Sử dụng hai ngăn xếp: ngăn xếp A cho hoàn tác và ngăn xếp B cho làm lại.

Mỗi khi người dùng thực hiện một thao tác, đẩy thao tác này vào ngăn xếp A và xóa sạch ngăn xếp B.
Khi người dùng thực hiện "hoàn tác", lấy thao tác gần đây nhất ra khỏi ngăn xếp A và đẩy nó vào ngăn xếp B.
Khi người dùng thực hiện "làm lại", lấy thao tác gần đây nhất ra khỏi ngăn xếp B và đẩy nó vào ngăn xếp A.