Stack和Deque、ArrayDeque和LinkedList

cylin...大约 3 分钟

总览

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

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

Deque<Integer> stack = new ArrayDeque<>();
Deque<Integer> stack = new LinkedList<>();

为什么不用Stack？

Stack和Vector都是线程安全的，其实多数情况下并不需要做到线程安全，因此没有必要使用Stack。毕竟保证线程安全需要上锁，有额外的系统开销
Stack从Vector继承是个历史遗留问题，JDK官方已建议优先使用Deque的实现类来代替Stack

Stack从Vector继承的一个副作用是，暴露了set/get方法，可以进行随机位置的访问，这与Stack只能从尾巴上进行增减的本意相悖
此外，Deque在转成ArrayList或者stream的时候保持了“后进先出”的语义，而Stack因为是从Vector继承，没有这个语义
Stack<Integer> stack = new Stack<>();
Deque<Integer> deque = new ArrayDeque<>();

stack.push(1);
stack.push(2);
deque.push(1);
deque.push(2);

System.out.println(new ArrayList<>(stack)); // [1,2]
List<Integer> list1 = stack.stream().collect(Collectors.toList());//[1,2]

// deque转成ArrayList或stream时保留了“后进先出”的语义
System.out.println(new ArrayList<>(deque)); // [2,1]
List<Integer> list2 = deque.stream().collect(Collectors.toList());//[2,1]

使用ArrayDeque还是LinkedList？

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

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

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

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

性能

注意到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快

测试代码

public class cyl {
    public static int[] generateRandomArray(int length, int max) {
        int[] arr = new int[length];
        Random rand = new Random();
        for (int i = 0; i < length; i++) {
            arr[i] = rand.nextInt(max) + 1; // 生成 [1, max] 范围内的随机数
        }
        return arr;
    }
    public static void main(String[] args) {
        int length = 500000;
        // 生成一个长度为length，值从1~max的随机数组
        int[] data = generateRandomArray(length, length);
        int loopCount = 10;
        long t1, t2, t3, t4;

        t1 = System.currentTimeMillis();
        for (int i = 0; i < loopCount; i++) {
            testLinkedList(data);
        }
        t2 = System.currentTimeMillis();
        System.out.println("LinkedList-timeTaken: " + String.format("%.1f", (t2-t1)/(double)loopCount));

        t3 = System.currentTimeMillis();
        for (int i = 0; i < loopCount; i++) {
            testArrayDeque(data);
        }
        t4 = System.currentTimeMillis();
        System.out.println("ArrayDeque-timeTaken: " + String.format("%.1f", (t2-t1)/(double)loopCount));

    }

    public static void testArrayDeque(int[] data) {
        int length = data.length;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < length/2; i++) {
            stack.push(data[i]);
            stack.push(data[i+1]);
            stack.pop();
            stack.push(stack.peek()+1);
        }
    }

    public static void testLinkedList(int[] data) {
        int length = data.length;
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < length/2; i++) {
            stack.push(data[i]);
            stack.push(data[i+1]);
            stack.pop();
            stack.push(stack.peek()+1);
        }
    }
}

性能结果

数据量	`ArrayDeque`	`LinkedList`
10万	4.7	3.5
50万	13.6	8.1
100万	27.2	24.0
200万	154.2	43.9

数据量未达到200万的情况下，感觉几乎可以忽略不记