Queue

Queue是一个很重要的接口。尤其是在并发编程中，比如像BlockingQueue就是继承自Queue接口的。Queue的实现也很多种多样，有最常见的ArrayDeque，LinkedList，这些是按插入顺序排序的。还有具有特殊功能的队列，比如优先级队列PriorityQueue。

先来看看Queue接口的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public interface Queue<E> extends Collection<E> {

    //将元素插入队列，总是返回true，如果失败，抛出异常
    //比如如果队列的容量不够了，抛出IllegalStateException
    boolean add(E e);

    //将元素插入队列，如果插入成功返回true，插入失败，返回false
    boolean offer(E e);

    //返回并移除队列的头部，如果队列为空，抛出NoSuchElementException
    E remove();

    //返回并移除队列的头部，如果队列为空，返回null
    E poll();

    //返回队列头部，如果队列为空，抛出NoSuchElementException
    E element();

    //返回队列的头部，如果队列为空，返回null
    E peek();
}

两种系列的操作：

首先要说的是，Queue的操作分为两个系列，一个是在失败时抛出异常，一个是在失败时返回特殊值(null或者false)。对于插入操作，后者是针对有空间限制的队列特有的，其他类型的队列在插入是不会出错的.

操作 失败时抛出异常 失败时返回特殊值
插入 add(e) offer(e)
删除 remove(e) poll(e)
获取 element(e) peek(e)

不一定是FIFO：

队列一般是按照先入先出(FIFO)的方式排序的，但是也不一定是。比如优先级队列和LIFO队列(栈)。Queue接口只是定义了插入了获取的方式，具体的实现，由底层决定。

最好不要插入null：

队列中最好插入null元素，虽然他的实现允许，比如LinkedList，但是因为poll方法使用null判断队列是否为空，所以在队列中插入null会引起歧义。

PS. 个人觉得，element这个函数名取得简直傻逼。

Deque

Queue是单端的操作。Deque是双端的操作。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
public interface Deque<E> extends Queue<E> {

    //在头部插入元素，如果空间不够，抛出IllegalStateException
    void addFirst(E e);

    //在尾部追加元素，如果空间不够，抛出IllegalStateException。和add等价
    void addLast(E e);

    //在头部插入元素，成功返回true，失败返回false
    boolean offerFirst(E e);

    //在尾部追加元素，成功返回true，失败返回false
    boolean offerLast(E e);

    //返回并删除头部元素，如果队列为空，抛出NoSuchElementException
    E removeFirst();

    //返回并删除尾部元素，如果队列为空，抛出NoSuchElementException
    E removeLast();

    //返回并删除头部元素，如果队列为空，返回null
    E pollFirst();

    //返回并删除尾部元素，如果队列为空，返回null
    E pollLast();

    //返回头部元素，如果队列为空，抛出NoSuchElementException。和element等价
    E getFirst();

    //返回尾部元素，如果队列为空，抛出NoSuchElementException
    E getLast();

    //返回头部元素，如果队列为空，，返回null
    E peekFirst();

    //返回尾部元素，如果队列为空，，返回null
    E peekLast();

    //删除从前往后第一个出现的相等元素
    boolean removeFirstOccurrence(Object o);

    //删除从后往前第一个出现的相等元素
    boolean removeLastOccurrence(Object o);

    // *** 队列相关方法 ***

    //和addLast等价
    boolean add(E e);

    //和offerLast等价
    boolean offer(E e);

    //和removeFirst等价
    E remove();

    //和pollFirst等价
    E poll();

    //和getFirst等价
    E element();

    //和peekFirst等价
    E peek();

    // *** 栈相关方法 ***

    //和addFirst等价
    void push(E e);

    //和removeFirst等价
    E pop();


    // *** Collection methods ***

    //和removeFirstOccurrence等价
    boolean remove(Object o);

    boolean contains(Object o);

    public int size();

    Iterator<E> iterator();

    Iterator<E> descendingIterator();

}

两种系列的操作：

和Queue一样，Deque也分为两种风格的操作。

操作 失败时抛出异常 失败时返回特殊值
插入 addFirst(e)/addLast(e) offerFirst(e)/offerLast(e)
删除 removeFirst(e)/removeLast(e) pollFirst(e)/pollLast(e)
获取 getFirst(e)/getLast(e) peekFirst(e)/peekLast(e)

Queue和Deque等价的方法：

因为Deque是继承自Queue的，而且Deque为了名义，所以函数名都是指定First/Last的，所以Queue中的方法，会和Deque中相应的方法等价：

Queue方法 等价的Deque方法
add(e) addLast(e)
offer(e) offerLast(e)
remove() removeFirst()
poll() pollFirst()
element() getFirst()
peek() peekFirst()

规则是：取头插尾

堆栈的方法：

Java集合除了失败的Stack类，并没有定义新的Stack方法，而是把Stack的方法定义在Deque里了。

Stack方法 等价的Deque方法 等价的Queue方法
push(e) addFirst(e) 无
pop() removeFirst() remove()
peek() peekFirst() peek()

因为Stack都是针对头部的操作，而Queue是取头插尾，所以只有取的方法有Queue接口对应的方法，push就没有了。

使用Deque来作为Stack：

1
Deque<Integer> stack = new ArrayDeque<Integer>();

最好不要插入null：

这一点和Queue一样。

PS. Deque继承自Queue，两套方法交杂在一起，Deque可以使用Queue中的方法，但是却很不名义，还是有些乱的。

参考资料