Java中的栈：Stack、Deque、ArrayDeque与LinkedList

Java中的栈：Stack、Deque、ArrayDeque与LinkedList

在Java中，栈（Stack）是一种后进先出（LIFO）的数据结构。栈在各种应用中都有用武之地，比如括号匹配、函数调用栈等。Java标准库提供了java.util.Stack类来实现栈，但在实际开发中，我们更推荐使用java.util.Deque接口及其实现类java.util.ArrayDeque和java.util.LinkedList来实现栈。

Stack类

Stack类是Java早期提供的一个实现栈的类，它继承自Vector类，实现了java.util.Stack接口。Stack类提供了一些基本的方法，如push（压栈）、pop（弹栈）、peek（查看栈顶元素）等。

然而，Stack类在Java集合框架中已经被标记为遗留（legacy），不推荐在新的代码中使用。因为它作为Vector的子类，继承了Vector的所有方法，这可能导致不期望的副作用。另外，Stack类也没有实现Deque接口，这意味着它缺少了一些现代栈实现应有的功能，比如offerFirst、offerLast、pollFirst和pollLast等。

Deque接口

Deque（双端队列）接口是Java集合框架中的一个接口，它扩展了Queue接口，添加了栈的功能。Deque接口提供了在两端添加和删除元素的方法，这使得它既可以作为队列使用，也可以作为栈使用。

Deque接口的实现类通常比Stack类更灵活、更高效。两个常用的实现类是ArrayDeque和LinkedList。

ArrayDeque类

ArrayDeque是一个基于数组的双端队列，它提供了高效的栈操作。ArrayDeque没有容量限制，可以根据需要动态扩展和收缩。

由于ArrayDeque是基于数组的，它在内存使用上通常比LinkedList更紧凑，因此在需要高性能的场景中，ArrayDeque通常是更好的选择。

LinkedList类

LinkedList是一个基于链表的双端队列，它也可以用来实现栈。LinkedList实现了Deque接口，因此它提供了完整的栈操作。

与ArrayDeque相比，LinkedList在插入和删除元素时可能更慢，因为链表需要遍历来找到正确的位置。然而，LinkedList在需要频繁在列表中间插入和删除元素时，性能可能更好。

总结

在Java中实现栈时，我们推荐使用Deque接口及其实现类ArrayDeque和LinkedList，而不是使用遗留的Stack类。Deque接口提供了更丰富的功能，而ArrayDeque和LinkedList则提供了高效的实现。

在大多数情况下，ArrayDeque是更好的选择，因为它在内存使用和性能上通常优于LinkedList。然而，如果你需要在列表中间频繁插入和删除元素，LinkedList可能是一个更好的选择。

// 使用ArrayDeque实现栈
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 输出3
System.out.println(stack.pop()); // 输出2
System.out.println(stack.pop()); // 输出1
// 使用LinkedList实现栈
Deque<Integer> stack2 = new LinkedList<>();
stack2.push(1);
stack2.push(2);
stack2.push(3);
System.out.println(stack2.pop()); // 输出3
System.out.println(stack2.pop()); // 输出2
System.out.println(stack2.pop()); // 输出1