【java容器的刻意练习】【十】LinkedList的Deque

2020-02-13 本文已影响0人程序猿修仙传

这篇我们用LinkedList实现的deque接口。

大家都学过，Queue是队列，先进后出，就是从头部进，从尾巴出。

如果要头尾都可以进呢？这种队列叫双端队列（Double Ended Queue），学名Deque。

而Java集合提供了Deque接口来实现一个双端队列，它的功能是：

既可以把元素添加到队首，也可以添加到队尾；
既可以从队首获取元素，又可以从队尾获取。

来看看 Deque 功能函数：
添加元素到队首 addFirst(E e) / offerFirst(E e)
添加元素到队尾 addLast(E e) / offerLast(E e)
取队首元素并删除 E removeFirst() / E pollFirst()
取队尾元素并删除 E removeLast() / E pollLast()
取队首元素但不删除 E getFirst() / E peekFirst()
取队尾元素但不删除 E getLast() / E peekLast()

为什么会有2种实现相同功能函数？

添加元素的函数，主要区别为是否有返回值。如addXXX，无返回值；offerXXX都是返回true。
读取、删除元素的函数，主要区别为遇到空队列是否抛异常。如removeXXX、getXXX会抛异常；pollXXX、peakXXX不抛异常，但返回空对象。

看看下面源码就明白了。

    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

还有一点需要注意的，Deque接口实际上扩展自Queue：

public interface Deque<E> extends Queue<E>

因此，Queue提供的add()/offer()方法在Deque中也可以使用，但是，使用Deque，最好不要调用offer()，而是调用offerLast()。因为如果直接写deque.offer()，我们就需要思考，offer()实际上是offerLast()，我们明确地写上offerLast()，不需要思考就能一眼看出这是添加到队尾。

而且，LinkedList相当全面，它即是List，又是Queue，还是Deque。但是我们在使用的时候，总是用特定的接口来引用它，这是因为持有接口说明代码的抽象层次更高，而且接口本身定义的方法代表了特定的用途。

        // 不推荐的写法:
        LinkedList linkedList = new LinkedList<>();
        linkedList.offerLast(123);

        // 推荐的写法：
        Deque deque = new LinkedList<>();
        deque.offerLast(123);

可见面向抽象编程的一个原则就是：尽量持有接口，而不是具体的实现类。

结论：

Deque接口实现了一个双端队列（Double Ended Queue），它可以：

将元素添加到队尾或队首：addLast()/offerLast()/addFirst()/offerFirst()；

从队首／队尾获取元素并删除：removeFirst()/pollFirst()/removeLast()/pollLast()；

从队首／队尾获取元素但不删除：getFirst()/peekFirst()/getLast()/peekLast()；

总是调用xxxFirst()/xxxLast()以便与Queue的方法区分开；

当把LinkedList用作Deque时候，使用Deque引用。

【java容器的刻意练习】【十】LinkedList的Deque

猜你喜欢

热点阅读