Java容器队列(二)-Deque(双端队列)

1 如何理解“双端队列”

Deque 全称为double ended queue，即双向队列，相对于队列它提供了更强大的功能.它允许在队列两侧插入或删除元素。因此deque实现不仅仅能能作为队列【先进先出FIFO(first in first out)】使用，还能作为栈【后入先出LIFO(last in first out)使用】。

2 Java中双端队列“接口”

Deque中定义的方法主要分为四部分，第一部分就如Deque定义所言，提供两侧插入或删除的方法。第二部分是继承自Queue的实现。第三部分表示如果要基于此实现一个Stack，需要实现的方法。最后一部分是继承自Collection的方法

提供两侧插入或删除的方法

//在队首添加元素
void addFirst(E e);
//在队首添加元素
boolean offerFirst(E e);

//在队尾添加元素
void addLast(E e);
boolean offerLast(E e);

//删除队首元素
E removeFirst();
E pollFirst();

//删除队尾元素
E removeLast();
E pollLast();

//获取队首元素
E getFirst();
E peekFirst();

//获取队尾元素
E getLast();
E peekLast();

//删除队列中第一个发现o元素
boolean removeFirstOccurrence(Object o);
//删除队列中最后一个发现o元素
boolean removeLastOccurrence(Object o);

和队列一样这里添加、删除、查询这些个操作都提供了两种形式。在操作失败时直接抛出异常，而另一种则返回一个特殊的值

image

继承自Queue的方法

Deque 继承了父接口Queue所有方法，并对所有接口方法都可以通过自身定义两侧插入或删除的方法来实现.其对应关系如下：

image

对应源码

    public boolean add(E e) {
        addLast(e);
        return true;
    }

实现Stack接口

虽然Deque提供的addFirst()，removeFirst()方法足以实现Stack功能，但Deque还是提供了针对Stack方法操作名称相关的方法：

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

//与removeFirst()等价
E pop();

继承于Collection的方法

//顺序是从队首到队尾
Iterator<E> iterator();

//顺序是从队尾到队首
Iterator<E> descendingIterator();