数据结构之双端队列

一:定义

双端队列是一种具有队列和栈性质的数据结构，即可在线性表的两端进行插入和删除等操作

二:.Java API中的Deque

知道了双端队列的定义，下面我们来了解一下Java API中的Deque类，知道双端队列是如何创建以及使用的

双端队列的创建以及使用

可以看到Deque类是一个接口，实现一个接口我们要重写接口中的所有方法。但Deque同时也实现了LinkedList类，因此创建Deque类我们可以newLinkedList类。

三:代码实现

知道了如何使用双端队列，下面我们就来实现一下其中的各个方法吧。下面将基于链表实现
基于链表
双端队列的添加方法(头部,尾部)，我们需要知道要插入位置的头节点以及尾节点，因此使用双向环形链表实现要方便许多
如图所示便为一个双向循环链表

1.节点的创建

创建一个双向循环链表节点，我们需要一个指向前一个节点的指针(pre)以及指向后面节点的指针( next)

2.双端队列的创建
我们需要一个头部哨兵节点sentinel,方便我们获取队首元素(sentinel.next)以及队尾元素(sentinel. pre)

3. addFirst 将指定元素插入此双端队列的开头

思路:向队列头部添加元素，首先我们需要获取哨兵节点sentinel以及头部节点( sentinel.next)，再创建一个新节点，更新对应的指针即可

4. addLast 将指定元素插入此双端队列的尾部

5. pollFirst 获取并移除此双端队列的第一个元素

6.pollLast 获取并移除此双端队列的最后一个元素

peekFirst 获取,但不移除此双端队列的第一个元素
思路:直接返回队首元素( sentinel.next.val)
peekLast 获取,但不移除此双端队列的最后一个元素
思路:直接返回队尾元素( sentinel.pre.val)