Suppose we are implementing a stack using a singly linked list where the head of the list is treated as the top of the stack. Specify the correct implementation of pop() method of the stack. (Choose the most suitable one)

Đáp án đúng: "Object pop() { if(isEmpty()) return(null); Node p = head; head=head.next;

if(head==null) tail=null;
return(p.info);

}". Phép lấy ra phải giữ nút đỉnh vào biến p trước khi dời head rồi trả về p.info, và khi head trở thành null tức danh sách vừa hết thì phải xoá luôn tail để hai con trỏ không còn chỉ vào nút đã bỏ. Bản "Object pop() { if(isEmpty()) return(null); Node p = head; head=head.next;

if(head==tail) tail=null;
return(p.info);

}" kiểm sai điều kiện: khi danh sách còn đúng một nút thì head và tail trùng nhau một cách hợp lệ, xoá tail lúc đó làm hỏng một danh sách chưa rỗng. Bản "Object pop() { if(isEmpty()) return(null); Node p = head; head=head.next; return(p.info); }" trả về đúng giá trị nhưng bỏ quên tail, nên khi ngăn xếp rỗng tail vẫn trỏ vào nút đã bị loại. Bản "Object pop() { if(isEmpty()) return(null); head=head.next;

if(head.next==null) tail=null;
return(head.info);

}" dời head trước rồi trả head.info nên trả về phần tử thứ hai chứ không phải đỉnh vừa lấy, và khi danh sách chỉ có một nút thì head thành null nên head.next gây lỗi con trỏ rỗng.