Em được học về Danh sách liên kết, sử dụng struct nhưng em ko rõ lắm về Queue và stack hay danh sách liên kết thì có sự khác nhau như thế nào. Mong ae chỉ bảo 
.
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.
5 Likes
Ở Queue, tại sao lại là ghi vào đầu và lấy ra ở đỉnh mà không phải là ghi vào đỉnh, lấy ra ở đầu.
1 Like
À ừ đúng rồi, trong máy tính thì nó lấy ra ở đầu và ghi vào đỉnh 
Còn về nguyên tắc thì ghi với đọc ở đâu không quan trọng, miễn là thoả mãn First in first out thì gọi là queue được rồi. Nếu Push kiểu stack thì Pop ở đầu, nếu Pop kiểu stack thì Push ở đầu.
Nếu hiểu cái nào có trước là đầu khối dữ liệu thì là ghi ở đỉnh và đọc ở đầu khối.
1 Like
Mình hỏi để bạn hoàn thiện câu trả lời thôi mà
2 Likes
khác nhau ở cách cài đặt
Cho em hỏi mình có thể dùng Queue để lưu các kí tự chữ cái được không hay chỉ là số thôi ạ ?
Được. Queue chỉ là cấu trúc dữ liệu, còn kiểu của dữ liệu có thể là bất cứ cái gì cũng được.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?