ArrayDeque介绍&&不推荐使用Stack类

ArrayDeque学习笔记

一只小菜鸡~

761人浏览 · 2022-10-28 16:29:48

一只小菜鸡~ · 2022-10-28 16:29:48 发布

今天在写leetcode时，用了堆栈数据结构，栈声明语句为Stack s = Stack()。但是时间效率很低，只能恰好AC的程度。看了官方题解，发现我的思路是完全正确的。于是仔细核对自己的代码和官方代码的区别，找到了罪魁祸首 Stack，于是改用ArrayDeque stack = new StackDeque()来声明栈，果然时间效率有质的提升。于是看资料，看博客学了一下其中的原因。

为什么Stack会慢

参考博客：https://blog.csdn.net/qq_39144436/article/details/124474791

自己的理解：Stack类继承了Vector，需要保证线程安全，效率就很低~

`ArrayDeque`介绍

ArrayDeque实现了Serializable、Cloneable、Iterable、Collection，Deque，Queue接口。
ArrayDeque是大小可变数组的实现。没有容量限制，容量可以根据需求动态变化。
不是线程安全的，在没有外部同步时，不支持多个线程的并发访问。不允许null元素。
在用作堆栈时，效率高于Stack，在用作队列时，效率高于LinkedList。
此类的iterator方法返回的迭代器是快速失败的：如果在创建迭代器后的任意时间内，通过除迭代器本身的remove方法之外的任何其他方式修改了双端队列，则迭代器通常会抛出ConcurrentModificationException。因此，面对并发修改，迭代器很快就会抛出错误，而不是冒着将来不确定的时刻发生不确定行为的风险。（但是迭代器的快速失败特性并不能保证100%安全，因此编写的程序不能依赖于此特性，这种特性仅用于检测BUG）

`ArrayDeque`实现原理

参考：https://www.cnblogs.com/xuwc/p/13936335.html

看源码，能很快理解底层实现原理。

`ArrayDeque`常用接口

方法	摘要
`ArrayDeque()`	构造一个初始容量能够容纳16个元素的空数组双端队列
`ArrayDeque(Collection<? extends E> c)`	构造一个包含指定Collection元素的双端队列，这些元素按照collection的迭代器返回的顺序排列
`ArrayDeque(int numElements)`	构造一个初始容量能够容纳指定数量的元素的空数组双端队列
`boolean offer(E e)`	将指定元素插入此双端队列的末尾
`boolean offerFirst()`	将指定元素插入此双端队列的开头
`boolean offerLast()`	将指定元素插入此双端队列的末尾
`boolean add(E e)`	将指定元素插入此双端队列的末尾
`void addFirst(E e)`	将指定元素插入此双端队列的开头
`void addLast(E e)`	将指定元素插入此双端队列的末尾
`E element()`	获取，但不移除此双端队列所表示的队列的头
`E getFirst()`	获取，但不移除此双端队列的第一个元素
`E getLast()`	获取，但不移除此双端队列的最后一个元素
`E peek()`	获取，但不移除此双端队列的第一个元素；如果双端队列为空，则返回Null
`E peekFirst()`	获取，但不移除此双端队列的第一个元素；如果此双端队列为空，则返回 `null`。
`E peekLast()`	获取，但不移除此双端队列的最后一个元素；如果此双端队列为空，则返回 `null`。
`E poll()`	获取并移除此双端队列所表示的队列的头（换句话说，此双端队列的第一个元素）；如果此双端队列为空，则返回 `null`。
`E pollFirst()`	获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 `null`。
`E pollLast()`	获取并移除此双端队列的最后一个元素；如果此双端队列为空，则返回 `null`。
`E remove()`	获取并移除此双端队列所表示的队列的头。
`boolean remove(Object e)`	从此双端队列中移除指定元素的单个实例。
`E removeFirst()`	获取并移除此双端队列第一个元素。
`boolean removeFirstOccurrence(Object o)`	移除此双端队列中第一次出现的指定元素（当从头部到尾部遍历双端队列时）。
`E removeLast()`	获取并移除此双端队列的最后一个元素。
`boolean removeLastOccurrence(Obejct o)`	移除此双端队列中最后一次出现的指定元素（当从头部到尾部遍历双端队列时）。
`void push(E e)`	将元素推入此双端队列所表示的堆栈。
`E pop()`	从此双端队列所表示的堆栈中弹出一个元素。
`void clear()`	从此双端队列中移除所有元素
`ArrayDeque<E> clone`	返回此双端队列的副本
`boolean contains(Object o)`	如果此双端队列包含指定元素，则返回true
`Iterator<E> descendingIterator()`	返回以逆向顺序在此双端队列的元素上进行迭代的迭代器
`boolean isEmpty()`	如果此双端队列未包含任何元素，则返回true
`Iterator<E> iterator()`	返回在此双端队列上进行迭代的迭代器
`int size()`	返回此双端队列中的元素数。
`Object[] toArray()`	返回一个以恰当顺序包含此双端队列所有元素的数组（从第一个元素到最后一个元素）。
`<T> T toArray(T[] a)`	返回一个以恰当顺序包含此双端队列所有元素的数组（从第一个元素到最后一个元素）；返回数组的运行时类型是指定数组的运行时类型。