系列博客目录
文章目录
- 系列博客目录
- 理论知识
- 1. 栈的基本概念
- 2. 栈的主要操作
- 3. 栈的实现
- 4. 栈的应用
- 5. 栈的性能
- 6. 注意事项
- `ArrayDeque` 类概述
- 主要方法
- 1. `add(E e)` / `offer(E e)`
- 2. `addFirst(E e)` / `offerFirst(E e)`
- 3. `remove()` / `poll()`
- 4. `removeFirst()` / `pollFirst()`
- 5. `removeLast()` / `pollLast()`
- 6. `getFirst()` / `peekFirst()`
- 7. `getLast()` /`peekLast()`
- 8. `push(E e)`
- 9. `pop()`
- 10. `clear()`
- 11. `size()`
- 12. `isEmpty()`
- 13. `toArray()`
- 14. `contains(Object o)`
- 总结
- 例题
理论知识
Java 中的栈（Stack）是一种特殊的线性数据结构，它遵循后进先出（LIFO, Last In First Out）的原则。栈的基本操作包括入栈（push）、出栈（pop）和查看栈顶元素（peek）。下面是一些栈的基础知识：
1. 栈的基本概念
栈是一种仅允许从一端进行插入和删除操作的数据结构。插入和删除操作都发生在栈顶元素，常见的比喻是“餐盘堆叠”，最后放入的盘子是第一个被取走的。
2. 栈的主要操作
- push：将元素压入栈顶。
- pop：移除栈顶元素并返回它。
- peek（或 top）：返回栈顶元素，但不移除它。
- isEmpty：检查栈是否为空。
- size：返回栈中元素的数量。
3. 栈的实现
Java 并没有直接提供栈的接口，但可以使用 java.util.Stack 类实现栈操作。Stack 类是 Vector 类的一个子类，它实现了栈的常见操作。
示例代码：
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
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.peek()); // 20
// 检查栈是否为空
System.out.println("栈是否为空: " + stack.isEmpty()); // false
}
}
4. 栈的应用
栈在程序设计中有很多实际应用：
- 递归调用：递归调用本质上依赖于栈来保存调用函数的上下文。
- 表达式求值：例如，在中缀表达式转后缀表达式时，栈用于临时存储操作符。
- 回溯算法：如深度优先搜索（DFS）中，栈用于保存节点路径。
5. 栈的性能
栈的操作（push、pop、peek）时间复杂度为 O(1)，因为它们只是对栈顶元素进行操作，因此栈的性能是非常高效的。
6. 注意事项
Stack类是同步的，但其性能可能比其他非同步数据结构（如LinkedList）差。因此，若不需要同步操作，建议使用LinkedList或ArrayDeque来实现栈。- 现代 Java 中，
Stack类通常被认为是过时的，推荐使用Deque（双端队列）接口的实现类，如ArrayDeque，来实现栈。
示例代码：使用 ArrayDeque 实现栈
import java.util.ArrayDeque;
import java.util.Deque;
public class ArrayDequeStackExample {
public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<>();
// 入栈操作
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.peek()); // 20
}
}
ArrayDeque 是 Java 中一个非常常用的类，提供了一个基于数组实现的双端队列（Deque）。ArrayDeque 允许在队列的两端进行插入、删除和访问元素，因此它可以用来实现栈（LIFO）和队列（FIFO）等数据结构。由于它是基于动态数组实现的，因此在效率上比 LinkedList 更好，尤其是在需要频繁操作队列头尾时。
ArrayDeque 类概述
ArrayDeque 是 Deque 接口的一个实现，继承自 AbstractCollection，提供了常见的队列和栈操作。ArrayDeque 适用于那些对性能要求较高的场景，尤其是在不需要线程安全的情况下。
主要方法
以下是 ArrayDeque 中常见的各种方法及其用途：
1. add(E e) / offer(E e)
-
add(E e)：将元素添加到队列的尾部。如果队列的容量满了，它会抛出IllegalStateException。 -
offer(E e)：与add(E e)类似，但它不会抛出异常。如果队列满了，它返回false，而不是抛出异常。通常用于容量受限的队列。ArrayDeque<Integer> deque = new ArrayDeque<>(); deque.add(10); // 将 10 添加到队列尾部 deque.offer(20); // 将 20 添加到队列尾部
2. addFirst(E e) / offerFirst(E e)
-
addFirst(E e)：将元素添加到队列的头部。如果队列的容量满了，它会抛出IllegalStateException。 -
offerFirst(E e)：与addFirst(E e)类似，但它不会抛出异常。如果队列满了，它返回false。deque.addFirst(5); // 将 5 添加到队列头部 deque.offerFirst(2); // 将 2 添加到队列头部
3. remove() / poll()
-
remove()：移除并返回队列的头部元素。如果队列为空，会抛出NoSuchElementException。 -
poll()：与remove()相似，但如果队列为空，它返回null。deque.remove(); // 移除并返回队列头部的元素，如果队列为空会抛出异常 deque.poll(); // 移除并返回队列头部的元素，如果队列为空会返回 null
4. removeFirst() / pollFirst()
-
removeFirst()：移除并返回队列的头部元素。如果队列为空，会抛出NoSuchElementException。 -
pollFirst()：与removeFirst()类似，但如果队列为空，它返回null。deque.removeFirst(); // 移除并返回队列头部的元素 deque.pollFirst(); // 移除并返回队列头部的元素，如果队列为空返回 null
5. removeLast() / pollLast()
-
removeLast()：移除并返回队列的尾部元素。如果队列为空，会抛出NoSuchElementException。 -
pollLast()：与removeLast()类似，但如果队列为空，它返回null。deque.removeLast(); // 移除并返回队列尾部的元素 deque.pollLast(); // 移除并返回队列尾部的元素，如果队列为空返回 null
6. getFirst() / peekFirst()
-
getFirst()：返回队列的头部元素，但不移除它。如果队列为空，会抛出NoSuchElementException。 -
peekFirst()：与getFirst()类似，但如果队列为空，它返回null。deque.getFirst(); // 返回队列头部的元素，不移除 deque.peekFirst(); // 返回队列头部的元素，不移除，如果队列为空返回 null
7. getLast() /peekLast()
-
getLast()：返回队列的尾部元素，但不移除它。如果队列为空，会抛出NoSuchElementException。 -
peekLast()：与getLast()类似，但如果队列为空，它返回null。deque.getLast(); // 返回队列尾部的元素，不移除 deque.peekLast(); // 返回队列尾部的元素，不移除，如果队列为空返回 null
8. push(E e)
-
push(E e)：将元素压入双端队列的头部，相当于栈的“入栈”操作。push()与addFirst()和offerFirst()的作用相似，都是将元素添加到队列头部。deque.push(10); // 将 10 压入栈顶（队列头部）
9. pop()
-
pop()：移除并返回队列的头部元素，类似栈的“出栈”操作。pop()会抛出NoSuchElementException如果队列为空。deque.pop(); // 移除并返回队列头部的元素
10. clear()
-
clear()：移除队列中的所有元素。deque.clear(); // 清空队列
11. size()
-
size()：返回队列中的元素数量。int size = deque.size(); // 返回队列中元素的数量
12. isEmpty()
-
isEmpty()：检查队列是否为空。如果队列为空，返回true，否则返回false。boolean empty = deque.isEmpty(); // 判断队列是否为空
13. toArray()
-
toArray()：返回队列中元素的一个数组副本。Object[] array = deque.toArray(); // 将队列元素转换为数组
14. contains(Object o)
-
contains(Object o)：检查队列是否包含指定的元素。如果队列中存在该元素，返回true，否则返回false。boolean contains = deque.contains(10); // 判断队列中是否包含元素 10
总结
ArrayDeque 提供了一系列方法来操作双端队列的元素，支持从队列的两端进行插入、删除和查看元素。与其他 Deque 实现相比，ArrayDeque 在处理高效的队列和栈操作时具有明显优势。如果你只是把他当作栈来使用，那就用pollLast()、peekLast()t和offerLast()，不要和push等连用！！！
例题
20.有效的括号
class Solution {
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/valid-parentheses/solutions/373578/you-xiao-de-gua-hao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
71.简化路径
class Solution {
public String simplifyPath(String path) {
String[] names = path.split("/");
Deque<String> stack = new ArrayDeque<String>();
for (String name : names) {
if ("..".equals(name)) {
if (!stack.isEmpty()) {
stack.pollLast();
}
} else if (name.length() > 0 && !".".equals(name)) {
stack.offerLast(name);
}
}
StringBuffer ans = new StringBuffer();
if (stack.isEmpty()) {
ans.append('/');
} else {
while (!stack.isEmpty()) {
ans.append('/');
ans.append(stack.pollFirst());
}
}
return ans.toString();
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/simplify-path/solutions/1193258/jian-hua-lu-jing-by-leetcode-solution-aucq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
150.求逆波兰表达式的值
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for(String str : tokens){
if(isNumber(str)){
stack.offerLast(Integer.valueOf(str));
}else {
int num2 = stack.pollLast();
int num1 = stack.pollLast();
switch (str) {
case "+":
stack.offerLast(num1 + num2);
break;
case "-":
stack.offerLast(num1 - num2);
break;
case "*":
stack.offerLast(num1 * num2);
break;
case "/":
stack.offerLast(num1 / num2);
break;
default:
}
}
}
return stack.pollLast();
}
private boolean isNumber(String str){
return !(str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/"));
}
}
155.最小栈
class MinStack {
Deque<Integer> stack;
Deque<Integer> minStack;
public MinStack() {
stack = new LinkedList<>();
minStack = new LinkedList<>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int val) {
stack.push(val);
minStack.push(Math.min(minStack.peek(),val));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}