文章目录
- 数组List
- 队列和栈
- 栈的应用：表达式求值
数组List
ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。
ArrayList 继承了 AbstractList ，并实现了 List 接口。
具体使用：
定义：
import java.util.*;
List<E> list = new ArrayList<>();
E: 泛型数据类型，用于设置 objectName 的数据类型，只能为引用数据类型。
已经封装可以直接调用的方法：
变量名.add(数据)：向尾部插入数据变量名.get(i)：通过下标访问数据变量名.set(i, 数据)：第一个参数为索引位置，第二个为要修改的值变量名.remove(i)：删除下标为i的数据变量名.size()：返回容器元素个数Collections.sort(变量名)：排序contains()：判断元素是否在 arraylistisEmpty()：判断 arraylist 是否为空subList()：截取部分 arraylist 的元素
import java.util.*;/*** @ClassName Main* @Description TODO* @Author 小何* @Date 2024/9/23 22:46**/
public class Main {public static void main(String[] args) {List<Integer> list = new ArrayList<>();// 添加数据list.add(3);list.add(4);list.add(1);list.add(2);list.add(6);System.out.println(list.toString()); // [3, 4, 1, 2, 6]// 修改数据list.set(2, 7);System.out.println(list.toString()); // [3, 4, 7, 2, 6]// 删除数据list.remove(list.size() -1);System.out.println(list.toString()); // [3, 4, 7, 2]// 反转Collections.reverse(list);System.out.println(list.toString()); // [2, 7, 4, 3]// 排序Collections.sort(list);System.out.println(list.toString()); // [2, 3, 4, 7]// 排序 大-》小Collections.sort(list, Collections.reverseOrder());System.out.println(list.toString()); // [7, 4, 3, 2]list.add(9);Collections.sort(list, new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});System.out.println(list.toString()); // [9, 7, 4, 3, 2]// 是否包含某个元素System.out.println(list.contains(8)); // false// 截取List<Integer> subList = list.subList(1, 3);System.out.println(subList.toString());// [7, 4]}
}队列和栈
队列：先进先出
栈：先进后出
LinkedList 实现了 Queue 接口等，可作为队列使用，也可以当作栈使用。
具体使用：
import java.util.LinkedList;
LinkedList<E> list = new LinkedList<>();
已经封装可以直接调用的方法：
- 添加元素
add - 尾部添加元素
addLast - 头部添加元素
addFirst - 移除头部元素
removeFirst - 移除尾部元素
removeLast - 获取头部元素
getFirst - 获取元素 i
get(i)
具体队列很栈的实现：
import java.util.*;/*** @ClassName Main* @Description TODO* @Author 小何* @Date 2024/9/23 22:46**/
public class Main {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(4);list.add(1);list.add(3);list.add(6);list.add(2);System.out.println(list.toString());// 在尾部添加元素list.addLast(8);// 在头部添加元素list.addFirst(9);System.out.println(list.toString()); //[9, 4, 1, 3, 6, 2, 8]// 移除头部元素list.removeFirst();System.out.println(list.toString()); // [4, 1, 3, 6, 2, 8]// 移除尾部元素list.removeLast();System.out.println(list.toString()); // [4, 1, 3, 6, 2]// 获取头部元素System.out.println(list.getFirst()); // 4// 获取尾部元素System.out.println(list.getLast()); // 2// 获取元素 iSystem.out.println(list.get(2)); // 3// 队列 queue 先进先出LinkedList<Integer> queue = new LinkedList<>();// 入队queue.add(1);queue.add(2);queue.add(3);System.out.println(queue.toString()); // [1, 2, 3]// 出队queue.removeFirst();System.out.println(queue.toString()); // [2, 3]// 访问队首元素System.out.println(queue.getFirst()); // 2// 访问队尾元素System.out.println(queue.getLast()); // 3// 队列元素System.out.println(queue.size()); // 2// 栈 stack 先进后出LinkedList<Integer> stack = new LinkedList<>();// 入栈stack.add(4);stack.add(6);stack.add(2);stack.add(1);stack.add(3);stack.add(5);System.out.println(stack.toString()); // [4, 6, 2, 1, 3]// 出栈stack.removeLast();System.out.println(stack.toString()); // [4, 6, 2, 1, 3]// 访问栈顶System.out.println(stack.getLast());// 3// 栈元素个数System.out.println(stack.size()); // 5}
}同时JAVA提供了专门的栈实现Stack类:
public class Main {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(1);stack.push(2);stack.push(3);stack.push(4);System.out.println(stack);System.out.println(stack.peek()); // 4 栈顶System.out.println(stack.pop()); // 4 出栈System.out.println(stack.peek()); // 3System.out.println(stack.size()); // 3}
}栈的应用：表达式求值
对于中缀表达式求值，需要定义两个栈：数字栈和符号栈，顾名思义分别存放数字和符号。
- 遇到数字，直接入数字栈，需要注意并不是只有个位数，还是需要一定的处理，详情见代码。
- 遇到符号，有三种情况：
- 左括号(：直接入符号栈。
- 右括号)：取两个数字栈的数据，取一个符号栈的数据，计算结果放入数字栈，循环直到符号栈中取出(结束。
- ±*/运算符：符号栈为空，直接入符号栈，不为空则需要比较当前的运算符和符号栈栈顶元素的优先级，当栈顶元素优先级大于等于当前的运算符，符号栈出栈，取两个数字栈元素进行计算，结果放入数字栈，循环，将所有大于等于当前的运算符的全部出栈为止。
- 最后的计算结果为数字栈的栈顶元素。
提前使用map集合定义好优先级:
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;public class Main {public static void main(String[] args) {String str = "2*(3+5)+7/1-4"; // 中缀表达式Stack<Integer> nums = new Stack<>(); // 数字栈Stack<Character> ops = new Stack<>(); // 符号栈// 符号优先级Map<Character, Integer> map = new HashMap<>();map.put('+', 1);map.put('-', 1);map.put('*', 2);map.put('/', 2);map.put('(', 0);char[] array = str.toCharArray();int i = 0;while (i < array.length) {// 遇到数字 直接入栈if (Character.isDigit(array[i])) {int sum = 0;while (i < array.length && Character.isDigit(array[i])) {sum = sum * 10 + (array[i] - '0');i++;}nums.push(sum);continue; // 继续到下一个字符}// 遇到符号if (array[i] == '(') {ops.push(array[i]);} else if (array[i] == ')') {// 出栈直到遇到左括号while (ops.peek() != '(') {performOperation(nums, ops);}ops.pop(); // 弹出左括号} else {// 运算符：比较优先级while (!ops.isEmpty() && map.get(ops.peek()) >= map.get(array[i])) {performOperation(nums, ops);}ops.push(array[i]);}i++;}// 处理剩余的运算符while (!ops.isEmpty()) {performOperation(nums, ops);}System.out.println(nums.pop());}private static void performOperation(Stack<Integer> nums, Stack<Character> ops) {int b = nums.pop();int a = nums.pop();char op = ops.pop();switch (op) {case '+': nums.push(a + b); break;case '-': nums.push(a - b); break;case '*': nums.push(a * b); break;case '/':// 注意：除以零的情况if (b == 0) throw new ArithmeticException("Division by zero");nums.push(a / b); break;}}
}
