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

Đáp án đúng: "

void enqueue(Object x) {
  Node p = new Node(x);
  p.next = null;
  if(isEmpty()) head = tail = p;
  else {
    tail.next = p;
    tail = p;
  }
}

". Thêm vào đuôi hàng đợi phải xử lý hai tình huống: khi danh sách rỗng chưa có tail nào để nối vào nên cả head và tail cùng trỏ vào nút mới; khi đã có phần tử thì nối tail.next = p để nút mới vào sau cùng rồi dời tail = p để đuôi luôn là nút cuối thật. Bản này làm đủ cả hai, còn p.next = null giữ cho đuôi kết thúc đúng. Phương án "

void enqueue(Object x) {
  Node p = new Node(x);
  p.next = null;
  tail.next = p;
  tail = p;
}

" bỏ hẳn nhánh rỗng, nên khi hàng đợi chưa có gì thì tail là null và lệnh tail.next gây lỗi truy cập null. Phương án "

void enqueue(Object x) {
  Node p = new Node(x);
  p.next = null;
  if(isEmpty()) head = tail = p;
  else tail.next = p;
}

" nối đúng nhưng quên dời tail, nên lần thêm sau lại nối vào đúng nút cũ và phần tử vừa thêm trước đó bị mất khỏi chuỗi. Phương án "

void enqueue(Object x) {
  Node p = new Node(x);
  p.next = null;
  if(isEmpty()) head = tail = p;
  else tail = p;
}

" chỉ dời tail mà không nối tail.next, nên nút mới trôi ra ngoài danh sách và đi từ head sẽ không bao giờ tới được nó.