Queue链表实现的注意点

Queue的链表实现

// 队列的链表实现

import java.util.NoSuchElementException;
public class Queue<Item> {
  private Node first;
  private Node last;
  private int N = 0;
  private class Node {
    Item item;
    Node next;
  }

  public boolean isEmpty() { return first == null;}
  public int     size()    { return N; }
  public void enqueue(Item e) {   // 在尾部添加元素O(1)
    Node oldLast = last;
    last = new Node();
    last.item = e;
    last.next = null;
    if (isEmpty()) first = last;          // 别忘, 如果为first = null, first指向last引用
    else           oldLast.next = last;   // 别忘, 新结点的上一个结点与新结点的链
    ++N;                                  // 别忘, 改变计数
  }

  public Item dequeue() {        // 在头部删除
    if (isEmpty()) throw new NoSuchElementException("Queue underflow");
    Item e = first.item;
    first = first.next;
    if (isEmpty()) last = null;          // 别忘, 删除后链表空, first=first.next=null, last=null;
    // 如果删除之前只有一个结点, 删除之后链表空了
    --N;                                 // 别忘, 改变计数
    return e;
  }
}

Queue链表实现的注意点

注意如下几个:
enqueue尾部插入

• 1, 旧尾结点用一个Node保存, last指向新的引用
• 2, last结点指向下一个null结点
• 3, 判空，if (first == null) first = last;
• 4, 非空, 上旧尾结点与新尾结点链接

dequeue头部删除

• 1, 判空, 抛出异常
• 2, 保留返回值, first = first.next;删除结点
• 3, 判空, last = null; 若删除前只剩一个结点, first.next为空,