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

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

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

}". Hàng đợi cài bằng danh sách liên kết đơn lấy phần tử ra ở đầu, nên trình tự phải là giữ lại nút đầu để còn đọc dữ liệu, dời head sang nút kế tiếp, và vì tail vẫn trỏ tới nút vừa bị tách khi hàng đợi thành rỗng, phải kiểm head bằng null để đặt tail về null. "Object dequeue() { if(isEmpty()) return(null); Node p = head; head=head.next;

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

}" so head với tail: với hàng đợi hai phần tử, sau khi dời head thì head và tail cùng trỏ nút cuối nên nó xoá tail trong khi hàng đợi vẫn còn một phần tử; còn khi hàng đợi chỉ còn một phần tử thì head thành null mà tail vẫn trỏ nút cũ nên không được dọn. "Object dequeue() { if(isEmpty()) return(null); Node p = head; head=head.next; return(p.info); }" trả về đúng giá trị nhưng không bao giờ dọn tail, nên khi hàng đợi rỗng tail còn treo ở nút đã bị tách và lần thêm vào sau đó sẽ nối phần tử mới vào chỗ không còn ai trỏ tới. "Object dequeue() { if(isEmpty()) return(null); head=head.next;

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

}" dời head trước khi đọc dữ liệu nên trả về phần tử thứ hai chứ không phải phần tử đầu, và khi hàng đợi chỉ còn một phần tử thì head thành null nên head.next gây lỗi truy cập null.