一、队列的作用

队列是基于先进先出（FIFO）的集合。现实中类似的场景有在银行大厅排队、汽车过收费站排队等。队列的作用在于1）将数据保存在容器中，2）同时还保存了元素间相对顺序。

比如一个从文件中读取整数，并返回int数组的实现就可以用到队列，这样就不必提前知道文件大小：

1 public static int[] readInts(String name){
 2     In in = new In(Name);
 3     Queue<Integer> q = new Queue<Integer>();
 4     while(!in.isEmpty()) {
 5         q.enqueue(in.readInt());
 6     }
 7     
 8     int N = q.size();
 9     int[] a = new int[N];
10     for(int i =0; i < N; i++) {
11         a[i] = q.dequeue();
12     }
13     return a;
14 }

二、队列的实现

队列可以用1）链表 2）数组来实现。

1、链表实现：

algs4中实现方法：

1 public class Queue<Item> implements Iterable<Item> {
 2     private Node<Item> first;    // 指向对首
 3     private Node<Item> last;     // 指向队尾
 4     private int n;               // 元素数量
 5 
 6     // 静态内部类存储元素，及链表指针
 7     private static class Node<Item> {
 8         private Item item;
 9         private Node<Item> next;
10     }
11 
12     public Queue() {
13         first = null;
14         last  = null;
15         n = 0;
16     }
17 
18     public boolean isEmpty() {
19         return first == null;
20     }
21 
22     public int size() {
23         return n;
24     }
25 
26     // 返回对首
27     public Item peek() {
28         if (isEmpty()) throw new NoSuchElementException("Queue underflow");
29         return first.item;
30     }
31 
32     //入队
33     public void enqueue(Item item) {
34         Node<Item> oldlast = last;
35         last = new Node<Item>();
36         last.item = item;
37         last.next = null;
38         if (isEmpty()) first = last;
39         else           oldlast.next = last;
40         n++;
41     }
42     //出队
43     public Item dequeue() {
44         if (isEmpty()) throw new NoSuchElementException("Queue underflow");
45         Item item = first.item;
46         first = first.next;
47         n--;
48         if (isEmpty()) last = null;   // to avoid loitering
49         return item;
50     }
51 
52 
53     public Iterator<Item> iterator()  {
54         return new ListIterator<Item>(first);  
55     }
56 
57     
58     private class ListIterator<Item> implements Iterator<Item> {
59         private Node<Item> current;
60 
61         public ListIterator(Node<Item> first) {
62             current = first;
63         }
64 
65         public boolean hasNext()  { return current != null;                     }
66         public void remove()      { throw new UnsupportedOperationException();  }
67 
68         public Item next() {
69             if (!hasNext()) throw new NoSuchElementException();
70             Item item = current.item;
71             current = current.next; 
72             return item;
73         }
74     }
75 }

2、数组实现：

参考ArrayQueue实现，利用环形数组，（数组长度取模）：

注意：

1）head，tail含义，head：队首；tail队尾可加入的空位。

2）有意保留一个空单元

1 public class ArrayQueue<T> extends AbstractList<T> {
 2     public ArrayQueue(int capacity) {
 3         this.capacity = capacity + 1;
 4         this.queue = newArray(capacity + 1);
 5         this.head = 0;
 6         this.tail = 0;
 7     }
 8 
 9     public void resize(int newcapacity) {
10         int size = size();
11         if (newcapacity < size)
12             throw new IndexOutOfBoundsException("Resizing would lose data");
13         newcapacity++;
14         if (newcapacity == this.capacity)
15             return;
16         T[] newqueue = newArray(newcapacity);
17         for (int i = 0; i < size; i++)
18             newqueue[i] = get(i);
19         this.capacity = newcapacity;
20         this.queue = newqueue;
21         this.head = 0;
22         this.tail = size;
23     }
24 
25     @SuppressWarnings("unchecked")
26     private T[] newArray(int size) {
27         return (T[]) new Object[size];
28     }
29 
30     public boolean add(T o) {
31         queue[tail] = o;
32         int newtail = (tail + 1) % capacity;
33         if (newtail == head)
34             throw new IndexOutOfBoundsException("Queue full");
35         tail = newtail;
36         return true; // we did add something
37     }
38 
39     public T remove(int i) {
40         if (i != 0)
41             throw new IllegalArgumentException("Can only remove head of queue");
42         if (head == tail)
43             throw new IndexOutOfBoundsException("Queue empty");
44         T removed = queue[head];
45         queue[head] = null;
46         head = (head + 1) % capacity;
47         return removed;
48     }
49 
50     public T get(int i) {
51         int size = size();
52         if (i < 0 || i >= size) {
53             final String msg = "Index " + i + ", queue size " + size;
54             throw new IndexOutOfBoundsException(msg);
55         }
56         int index = (head + i) % capacity;
57         return queue[index];
58     }
59 
60     public int size() {
61         // Can't use % here because it's not mod: -3 % 2 is -1, not +1.
62         int diff = tail - head;
63         if (diff < 0)
64             diff += capacity;
65         return diff;
66     }
67 
68     private int capacity;
69     private T[] queue;
70     private int head;
71     private int tail;
72 }