数据结构--栈（Stack）& 队列（Queue）

一、栈（Stack）

1. 栈的定义

• 栈（Stack）是一种 先进后出（LIFO, Last In First Out） 的数据结构。

• 就像一摞书：最后放的书最先拿走。

---

2. 栈的常用方法（Stack 类）

• Stack<E> 继承自 Vector，是 线程安全 的，但性能一般。

• 更推荐使用 Deque<E>（如 ArrayDeque 或 LinkedList）来实现栈结构。

方法	功能描述	备注
push(E e)	将元素压入栈顶	相当于入栈操作
pop()	弹出栈顶元素，并返回该元素	栈为空时会抛 EmptyStackException
peek()	查看栈顶元素，但不删除	栈为空时会抛 EmptyStackException
empty()	判断栈是否为空	返回 true 或 false
search(Object o)	返回元素在栈中的位置（从 1 开始，栈顶为 1）	找不到返回 -1

---

3. 使用示例

• Stack<E> 继承自 Vector，是 线程安全 的，但性能一般。(下面的(1))

• 更推荐使用 Deque<E>（如 ArrayDeque 或 LinkedList）来实现栈结构。(下面的(2))

（1）使用 Stack 类

Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
stack.push(30);

System.out.println(stack.peek()); // 30
System.out.println(stack.pop());  // 30
System.out.println(stack.pop());  // 20
System.out.println(stack.empty()); // false

（2）使用 ArrayDeque 模拟栈（推荐）

Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
stack.push("C");

System.out.println(stack.pop()); // C
System.out.println(stack.peek()); // B

---

4. 栈的应用场景

• 函数调用栈：保存方法调用现场（局部变量、返回地址等）。

• 括号匹配：比如判断 ({[]}) 是否匹配。

• 表达式求值：逆波兰表达式（后缀表达式）。

• 回溯算法：比如迷宫寻路。

二、队列（Queue）

1. 队列的定义

• 队列（Queue）是一种 先进先出（FIFO, First In First Out） 的数据结构。

• 就像排队买票：先排队的人先买，后排的人要等前面的人买完。

• 在 Java 中，Queue 是一个接口，继承自 Collection 接口。

---

2. 队列的常用方法（来自 Queue 接口）

方法	功能
boolean add(E e)	向队列尾部插入元素，若失败抛异常
boolean offer(E e)	向队列尾部插入元素，失败时返回 false
E remove()	删除并返回队首元素，队列为空时抛异常
E poll()	删除并返回队首元素，队列为空时返回 null
E element()	返回队首元素但不删除，队列为空时抛异常
E peek()	返回队首元素但不删除，队列为空时返回 null

---

3. 常见的队列实现类

（1）LinkedList

• LinkedList 实现了 Queue 接口，可以作为普通队列使用。

Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
queue.offer("C");
System.out.println(queue.poll()); // A
System.out.println(queue.peek()); // B

（2）PriorityQueue（优先队列）

• 元素按 优先级排序（默认是自然顺序，小的优先）。

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
System.out.println(pq.poll()); // 1
System.out.println(pq.poll()); // 3

（3）ArrayDeque（双端队列）

• 推荐的队列实现，比 LinkedList 更高效。

• 可以当队列（FIFO）或栈（LIFO）使用。

Queue<String> dq = new ArrayDeque<>();
dq.offer("A");
dq.offer("B");
System.out.println(dq.poll()); // A

---

4. 队列的应用场景

• 排队系统：比如消息队列（RabbitMQ、Kafka）。

• 缓冲区：比如网络 IO 中的数据缓冲。

• 广度优先搜索（BFS）：图/树的层序遍历。

---

三、栈和队列对比

特点	栈（Stack）	队列（Queue）
存取顺序	LIFO（先进后出）	FIFO（先进先出）
典型操作	push 入栈，pop 出栈	offer 入队，poll 出队
Java 实现类	Stack, ArrayDeque	LinkedList, ArrayDeque, PriorityQueue
应用场景	函数调用栈、表达式计算、回溯	消息队列、BFS、排队系统

---

✅ 总结

• 栈：适合 回溯 / 嵌套处理，强调后进先出。

• 队列：适合 排队 / 顺序处理，强调先来先服务。

• 推荐 使用 ArrayDeque 来实现队列和栈，性能比 LinkedList 和 Stack 更好。