双端队列ArrayDeque、LinkedList
热衷学习,热衷生活!😄
沉淀、分享、成长,让自己和他人都能有所收获!😄
一、前言
Stack栈:先进后出
Queue队列:先进先出
在Java里有一个Stack类,但是这个类已经不推荐使用了,而Queue是一个接口,当我们需要使用栈和队列时,推荐使用更加高效的ArrayDeque该类实现Deque接口,次选使用LinkedList。
二、总体介绍
要讲栈和队列,首先要讲Deque接口。Deque的含义是”double ended queue”,即双端队列,既可以当栈使用,也可以当队列使用。
下表列出Deque和Queue相对应的接口:
Queue 方法 | Deque 方法 | 说明 |
---|---|---|
add(e) |
addLast(e) |
向队尾插入元素,失败则抛出异常 |
offer(e) |
offerLast(e) |
向队尾插入元素,失败则返回false |
remove() |
removeFirst() |
获取并删除队首元素,失败则抛出异常 |
poll() |
pollFirst() |
获取并删除队首元素,失败则返回null |
element() |
getFirst() |
获取但不删除队首元素,失败则抛出异常 |
peek() |
peekFirst() |
获取但不删除队首元素,失败则返回null |
下标列出Deque和Stack对应的接口:
Stack 方法 | Deque 方法 | 说明 |
---|---|---|
push(e) |
addFirst(e) |
向栈顶插入元素,失败则抛出异常 |
无 | offerFirst(e) |
向栈顶插入元素,失败则返回false |
pop() |
removeFirst() |
获取并删除栈顶元素,失败则抛出异常 |
无 | pollFirst() |
获取并删除栈顶元素,失败则返回null |
peek() |
peekFirst() |
获取但不删除栈顶元素,失败则抛出异常 |
无 | peekFirst() |
获取但不删除栈顶元素,失败则返回null |
上表Deque总共定义了Deque的12个接口。添加,删除,取值都有两套接口,它们功能相同,区别是对失败情况的处理不同。一套接口遇到失败就会抛出异常,另一套遇到失败会返回特殊值(false
或null
)。除非某种实现对容量有限制,大多数情况下,添加操作是不会失败的。虽然Deque的接口有12个之多,但无非就是对容器的两端进行操作,或添加,或删除,或查看。明白了这一点讲解起来就会非常简单。
三、ArrayDeque
ArrayDeque是基于数组实现的可动态扩容的双端队列,定义和head、tail头尾两个下标值,默认为0。为了满足可以同时在数组两端插入或者删除元素,该数组还必须是循环的,即循环数组(circular array),也就是说数组的任何一点都可以被看作是起点或者终点。ArrayDeque是非线程安全的,另外不允许插入null元素。
当ArrayDeque作为队列使用时,核心方法是addLast(),该方法的作用是在ArrayDeque的尾部插入元素,也就是在tail的位置插入元素,tail总是指向下一个可以插入元素的空位,所以在源码中只需elements[tali] = e; 插入完成之后再检查空间是否需要扩容,如果需要扩容则调用**doubleCapacity()**进行扩容,源码如下:
1 | public void addList(E e){ |
扩容方法:两倍扩容,通过数组copy数据位移
1 | private void doubleCapacity() { |
当Deque作为栈使用时,核心方法为addFirst(),也就是在ArrayDeque首段插入元素,在数组空间没有越界的情况下elements[–elements.length] = e 即可。源码如下:
1 | public void addFirst(E e) { |
四、LinkedList
LinkedList是由双向链表实现的双端队列,定义了first、last首尾两个节点用于连接链表,核心方法同样是**addFirst()和addLast()**。
LinkedList作为队列使用,addLast()源码为:
1 | public void addLast(E e) { |
LinkedList作为栈使用,addFirst()源码为:
1 | public void addFirst(E e) { |