Java中的栈Stack、Deque、ArrayDeque、LinkedList

2023-05-29 18:48| 来源: 网络整理| 查看: 265

文章目录先来说说Java中的Stack类不用Stack至少有以下两点原因该用ArrayDeque还是LinkedList？ArrayDeque的反向遍历结论加餐

先来说说Java中的Stack类

Java中Stack类从Vector类继承，底层是用数组实现的线程安全的栈。栈是一种后进先出(LIFO)的容器，常用的操作push/pop/peek。

不过Java中用来表达栈的功能（push/pop/peek），更适用的是使用双端队列接口Deque，并用实现类ArrayDeque/LinkedList来进行初始化。

Deque stack = new ArrayDeque(); Deque stack = new LinkedList(); 不用Stack至少有以下两点原因

1、从性能上来说应该使用Deque代替Stack。

Stack和Vector都是线程安全的，其实多数情况下并不需要做到线程安全，因此没有必要使用Stack。毕竟保证线程安全需要上锁，有额外的系统开销。

2、Stack从Vector继承是个历史遗留问题，JDK官方已建议优先使用Deque的实现类来代替Stack。

Stack从Vector继承的一个副作用是，暴露了set/get方法，可以进行随机位置的访问，这与Stack只能从尾巴上进行增减的本意相悖。

此外，Deque在转成ArrayList或者stream的时候保持了“后进先出”的语义，而Stack因为是从Vector继承，没有这个语义。

Stack stack = new Stack(); Deque deque = new ArrayDeque(); stack.push(1); stack.push(2); deque.push(1); deque.push(2); System.out.println(new ArrayList(stack)); // [1,2] List list1 = stack.stream().collect(Collectors.toList());//[1,2] // deque转成ArrayList或stream时保留了“后进先出”的语义 System.out.println(new ArrayList(deque)); // [2,1] List list2 = deque.stream().collect(Collectors.toList());//[2,1] 该用ArrayDeque还是LinkedList？

ArrayDeque和LinkedList这两者底层，一个采用数组存储，一个采用链表存储；

数组存储，容量不够时需要扩容和数组拷贝，通常容量不会填满，会有空间浪费；

链表存储，每次push都需要new Node节点，并且node节点里面有prev和next成员，也会有额外的空间占用。

PS：这两者既可当成栈（仅支持在尾部加入或移除元素）使用；也可当成双端队列使用，即可以在队列的两端（头或尾）将元素加入或移除。单次加入/移除元素的平均时间复杂度均为O(1)。

那么问题来了，在用作栈时到底用ArrayDeque好还是LinkedList好呢？

注意到ArrayDeque源码注释中有一句话： This class is likely to be faster than {@link Stack} when used as a stack, and faster than {@link LinkedList} when used as a queue.

ArrayDeque用作栈时比Stack快没有疑问，用作队列的时候似乎也会比LinkedList快！

笔者经过50W数据量的测试，发现两者性能基本接近，ArrayDeque平均耗时在18-24ms，LinkedList耗时平均在20-28ms。

如果数据量上升到100W的话，ArrayDeque的优势会更明显。

结论：ArrayDeque会略胜一筹，不过差别通常可以忽略

public static void main(String[] args) { int length = 500000; int max = length; // 生成一个长度为length，值从1~max的随机数组 int[] data = new RandomIntArray(length,1,length,max).next(); int loopCount = 10; long t1, t2; t1 = System.currentTimeMillis(); for (int i = 0; i int length = data.length; Deque stack = new ArrayDeque(); for (int i = 0; i int length = data.length; Deque stack = new LinkedList(); for (int i = 0; i T x = it.next(); } 结论

ArrayDeque会略胜一筹，不过差别通常可以忽略。经过性能对比，笔者更倾向于使用ArrayDeque来表达Java中的栈功能。

加餐

力扣上面有一道设计双端队列的题目（不要求扩容，简化版的ArrayDeque），有兴趣的朋友不妨去试试： 641. 设计循环双端队列

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章