Java中的栈的实现

Java中的栈的实现--双端队列（Deque）

1. 解释代码
2.为什么不用 Stack<Character>？
3.使用示例
4.Deque 的常用方法
5.LinkedList<> 和 ArrayDeque<> 的区别和联系
6. 总结

1. 解释代码

Deque<Character> st = new ArrayDeque<>();

Deque st = new ArrayDeque<>(); 这行代码的作用是创建一个双端队列（Deque），用于存储 Character 类型的元素。它的行为类似于栈（Stack）或队列（Queue），取决于如何使用它。
• Deque：表示 st 是一个双端队列，支持两端插入和删除操作。
• new ArrayDeque<>()：使用 ArrayDeque 作为具体的实现，它比 LinkedList 更高效（无额外的节点开销）。
• Character：存储字符类型的数据。

2.为什么不用 Stack？

•	**Stack<Character>** 是 Vector 的子类，基于 动态数组，性能不如 ArrayDeque。
•	**ArrayDeque 是双端队列**，支持 栈（LIFO）和队列（FIFO） 操作，性能比 Stack 更优。

推荐使用 Deque 来代替 Stack，因为：
	•	**ArrayDeque** 没有同步开销（Stack 继承自 Vector，方法是 synchronized 的）。
•	**ArrayDeque 性能更高**，push() 和 pop() 都是 O(1)。

3.使用示例

作为栈（LIFO - 后进先出）

Deque<Character> stack = new ArrayDeque<>();

stack.push('A');  // 入栈
stack.push('B');  // 入栈
stack.push('C');  // 入栈

System.out.println(stack.pop());  // 输出 C（后进先出）
System.out.println(stack.pop());  // 输出 B
System.out.println(stack.pop());  // 输出 A

输出

C
B
A

push() 等价于 addFirst()，pop() 等价于 removeFirst()。

作为队列（FIFO - 先进先出）

4.Deque 的常用方法

Deque<Character> queue = new ArrayDeque<>();

queue.offer('A');  // 入队
queue.offer('B');  // 入队
queue.offer('C');  // 入队

System.out.println(queue.poll());  // 输出 A（先进先出）
System.out.println(queue.poll());  // 输出 B
System.out.println(queue.poll());  // 输出 C

输出

A
B
C

offer() 等价于 addLast()，poll() 等价于 removeFirst()。

在这里插入图片描述

5.LinkedList<> 和 ArrayDeque<> 的区别和联系

LinkedList<> 和 ArrayDeque<> 都实现了 Deque 接口，但它们的底层实现和性能特点有所不同。

主要区别
适用场景

LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(3);
list.add(4);
list.add(1, 2); // 在索引 1 处插入 2
System.out.println(list); // [1, 2, 3, 4

在这里插入图片描述

6. 总结

Deque st = new ArrayDeque<>(); 创建了一个双端队列，可以当作栈（LIFO）或队列（FIFO）使用。
• 推荐 ArrayDeque 代替 Stack，因为它更高效、更灵活，没有 Stack 的同步开销。
• 使用 push() 和 pop() 操作时，它表现得像 Stack（后进先出）。
• 使用 offer() 和 poll() 操作时，它表现得像 Queue（先进先出）。

在这里插入图片描述