使用链表能达到最优设计目标：

  1. 可以处理任意类型的数据
  2. 所需的空间总是和集合的大小成正比
  3. 操作所需的时间总是和集合的大小无关

在下面的实现代码中能看到队列和栈的区别，栈由于是后进先出，所以只涉及头部，操控一个first变量即可。队列是先进先出，所以要操控first和last两个Node变量。

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Queue<Item> {
  private Node first;
  private Node last;
  private int N;
  private class Node {
    Item item;
    Node next;
  }
  public boolean isEmpty() {
    return first == null;
  }
  public int size() {
    return N;
  }
  public void enqueue(Item item) {
    Node oldlast = last;
    last = new Node();
    last.item = item;
    last.next = null;
    if (isEmpty()) {
      first = last;
    } else {
      oldlast.next = last;
    }
    N++;
  }
  public Item dequeue() {
    Item item = first.item;
    first = first.next;
    if (isEmpty()) {
      last = null;
    }
    N--;
    return item;
  }
  public static void main(String[] args) {
    Queue<String> q = new Queue<String>();
    while (!StdIn.isEmpty()) {
      String item = StdIn.readString();
      if (!item.equals("-")) {
        q.enquequ(item);
      } else if (!q.isEmpty()) {
        StdOut.print(q.dequeue() + " ");
      }
    }
    StdOut.println("(" + q.size() + " left on queue");
}

参考

  • 《算法》p95