Hỏi Về Sự Khác Nhau Giữa Danh Sách Liên Kết, Stack Và Queue

ListArray (Danh sách) ListNode (Danh sách liên kết) Stack (Xếp chồng) Queue (Hàng đợi)

4 cách máy tính lưu trữ dữ liệu vào các ô nhớ (trong RAM, trong ổ, trong CPU…), trong đó 3 cách sau thì kích thước khối dữ liệu có thể thay đổi.

*Xét một ListArray: Kích thước được khai báo từ trước, sử dụng các ô nhờ từ vị trí bắt đầu (đã khai báo) đến vị trí kết thúc (đã khai báo). Có thể nói là trong ListArray thì mỗi phần tử của khối đã được cấp phát một giá trị nào đó, ta chỉ có thể thay đổi giá trị chứ không cấp phát hay thu hổi được một vài ô, trừ khi thu hồi cả ListArray

*Xét một ListNode: Hoàn toàn không biết trước được khối dữ liệu có kích thước như thế nào, mà chỉ biết vị trí của ô nhớ đầu tiên. Ô nhớ đầu tiên sẽ lưu trữ dữ liệu của mình và địa chỉ ô nhớ tiếp theo. Nếu có một ô nhớ nào đó mà địa chỉ ô nhớ tiếp theo là NULL thì coi như đó là ô nhớ cuối cùng của khối dữ liệu. Như vậy, ta thấy ListNode không dùng các ô nhớ liền kề nhau mà các ô nhớ ở đâu cũng được, miễn là chúng có địa chỉ. Muốn thêm một ô nhớ vào một vị trí, ta thay đổi địa chỉ liên kết của ô nhớ đó và ô nhớ đại diện cho Node trước nó là được. Tương tự với xoá ô nhớ.

*Xét một Stack: Ô nhớ đầu tiên của Stack sẽ ghi thông tin về kích thước stack. Mỗi stack sẽ lưu dữ liệu vào các stack liền kề ô nhớ đầu tiên. Stack thì không thể thêm được vào vị trí bất kỳ mà chỉ thêm được vào đỉnh của Stack bằng cách gán giá trị ô nhớ bên cạnh ô đỉnh và tăng kích thước stack thêm 1. Đọc thì tử đỉnh stack xuống. Cho nên stack chỉ có 2 hàm là Push và Pop để ghi và đọc dữ liệu thôi

*Xét một Queue: Queue khá giống stack ở hàm Pop, nhưng hàm Push để ghi dữ liệu vào thì khác một chút. Trước khi ghi dữ liệu, toàn bộ các ô nhớ thuộc Q đều được gán giá trị bỏi ô ngay trước nó, và ô đầu tiên sẽ được gán giá trị mới, cho nên đối với Q thì đọc ở đỉnh khối dữ liệu nhưng ghi vào đầu khối dữ liệu.