算法模板（Java版）_链表（单链表、双链表）、栈和队列

@ZZHow(ZZHow1024)

单链表（静态链表）

使用数组模拟单链表（静态链表），head 为头指针，e 数组为数据，ne 数组为指针。

• 例题：AcWing 826. 单链表

import java.util.Scanner;public class Main {static final int N = 100000;static int head; //头指针static int[] e = new int[N]; //数据static int[] ne = new int[N]; //指针static int idx;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int m = scanner.nextInt();init();while (m-- != 0) {int k, x;char op = scanner.next().charAt(0);switch(op) {case 'H': {x = scanner.nextInt();add(x);break;}case 'D': {k = scanner.nextInt();remove(k - 1);break;}case 'I': {k = scanner.nextInt();x = scanner.nextInt();add(k - 1, x);break;}}}for (int i = head; i != -1; i = ne[i])System.out.print(e[i] + " ");}// 初始化public static void init() {head = -1;idx = 0;}// 将 x 插到头结点的位置public static void add(int x) {e[idx] = x;ne[idx] = head;head = idx;idx++;}// 将 x 插到下标为 k 的结点后面public static void add(int k, int x) {e[idx] = x;ne[idx] = ne[k];ne[k] = idx;idx++;}// 将下标为 k 的结点后边的结点删除public static void remove(int k) {// 特判删除头结点的情况if (k == -1)head = ne[head];elsene[k] = ne[ne[k]];}
}

双链表（静态链表）

使用数组模拟双链表（静态链表），索引 0 为头结点，索引 1 为尾结点，e 数组为数据，l 数组为左指针，r 数组为右指针。

• 例题：AcWing 827. 双链表

import java.util.Scanner;public class Main {static final int N = 100000;static int[] e = new int[N]; // 数据static int[] l = new int[N]; // 左指针static int[] r = new int[N]; // 右指针static int idx;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);init();int m = scanner.nextInt();while (m-- != 0) {int k, x;String op = scanner.next();switch (op) {case "L": {x = scanner.nextInt();add(0, x);break;}case "R": {x = scanner.nextInt();add(l[1], x);break;}case "D": {k = scanner.nextInt();remove(k + 1);break;}case "IL": {k = scanner.nextInt();x = scanner.nextInt();add(l[k + 1], x);break;}case "IR": {k = scanner.nextInt();x = scanner.nextInt();add(k + 1, x);break;}}}for (int i = r[0]; i != 1; i = r[i])System.out.print(e[i] + " ");}// 初始化public static void init() {r[0] = 1;l[1] = 0;idx = 2;}// 在下标是 k 的结点的右边插入 xpublic static void add(int k, int x) {e[idx] = x;r[idx] = r[k];l[idx] = k;l[r[k]] = idx;r[k] = idx;idx++;}// 将下标为 k 的结点右边的结点删除public static void remove(int k) {r[l[k]] = r[k];l[r[k]] = l[k];}
}

栈

使用数组模拟栈，stk 数组为数据，tt 既指示元素个数也作为指针指示数组下标。

• 例题：AcWing 828. 模拟栈

import java.util.Scanner;public class Main {static final int N = 100000;static int[] stk = new int[N]; // 存储数据static int tt; // 元素个数（指向栈顶元素）public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int m = scanner.nextInt();while (m-- != 0) {int x;String op = scanner.next();switch (op) {case "push": {x = scanner.nextInt();add(x);break;}case "pop": {pop();break;}case "empty": {System.out.println(isEmpty() ? "YES" : "NO");break;}case "query": {System.out.println(query());break;}}}}// 插入元素public static void add(int x) {stk[++tt] = x;}// 弹出元素public static void pop() {tt--;}// 查询栈顶元素public static int query() {return stk[tt];}// 判断栈是否为空public static boolean isEmpty() {if (tt > 0)return false;elsereturn true;}
}

队列

使用数组模拟队列，q 数组为数据，hh 作为指针指向对头，tt 作为指针指向队尾。

• 例题：AcWing 829. 模拟队列

import java.util.Scanner;public class Main {static final int N = 100000;static int[] q = new int[N]; // 存储数据static int hh = 0; // 队头static int tt = -1; // 队尾public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int m = scanner.nextInt();while (m-- != 0) {int x;String op = scanner.next();switch(op) {case "push": {x = scanner.nextInt();add(x);break;}case "pop": {pop();break;}case "empty": {System.out.println(isEmpty() ? "YES" : "NO");break;}case "query": {System.out.println(query());}}}}// 插入元素public static void add(int x) {q[++tt] = x;}// 弹出元素public static void pop() {hh++;}// 查询队头元素public static int query() {return q[hh];}// 判断队列是否为空public static boolean isEmpty() {if (hh <= tt)return false;elsereturn true;}
}

单调栈

在数组模拟栈的基础上，每次插入数据前将比待插入数据大的元素弹出，一直弹栈到栈顶元素小于待插入数据或栈为空。

应用：求输入的数左边第一个比它小的数。

• 例题：AcWing 830. 单调栈

import java.util.Scanner;public class Main {static final int N = 100010;static int[] stk = new int[N];static int tt = 0;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();for (int i = 0; i < n; i++) {int x = scanner.nextInt();while (tt != 0 && stk[tt] >= x)tt--;if (tt != 0)System.out.print(stk[tt] + " ");elseSystem.out.print(-1 + " ");stk[++tt] = x;}}
}

单调队列

在数组模拟队列的基础上，每次插入数据前将队尾比待插入数据大（小）的元素弹出，一直弹栈到队尾元素小于（大于）待插入数据或队列为空。

应用：滑动窗口求最小（最大）值。

例题：AcWing 154. 滑动窗口

import java.util.Scanner;public class Main {static final int N = 1000010;static int[] a = new int[N];static int[] q = new int[N];static int hh = 0;static int tt = -1;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int k = scanner.nextInt();for (int i = 0; i < n; i++)a[i] = scanner.nextInt();for (int i = 0; i < n; i++) {// 判断队头是否已经滑出窗口if (hh <= tt && i - k + 1 > q[hh])hh++;while (hh <= tt && a[q[tt]] >= a[i])tt--;q[++tt] = i;if (i >= k - 1)System.out.print(a[q[hh]] + " ");}System.out.println();hh = 0;tt = -1;for (int i = 0; i < n; i++) {// 判断队头是否已经滑出窗口if (hh <= tt && i - k + 1 > q[hh])hh++;while (hh <= tt && a[q[tt]] <= a[i])tt--;q[++tt] = i;if (i >= k - 1)System.out.print(a[q[hh]] + " ");}}
}

栈的应用——表达式求值

“表达式求值”问题，两个核心关键点：

• 双栈，一个操作数栈(num)，一个运算符栈(op)；
• 运算符优先级，栈顶运算符，和，即将入栈的运算符的优先级比较：
  1. 如果栈顶的运算符优先级低，新运算符直接入栈。
  2. 如果栈顶的运算符优先级高，先出栈计算，新运算符再入栈。

• 例题：AcWing 3302. 表达式求值

import java.util.*;public class Main {static Stack<Integer> num = new Stack<>();static Stack<Character> op = new Stack<>();static Map<Character, Integer> map = new HashMap<>();public static void main(String[] args) {Scanner scanner = new Scanner(System.in);map.put('+', 1);map.put('-', 1);map.put('*', 2);map.put('/', 2);String str = scanner.next();for (int i = 0; i < str.length(); i++) {char c = str.charAt(i);if (Character.isDigit(c)) {int x = 0;int j = i;while (j < str.length() && Character.isDigit(str.charAt(j))) {x = x * 10 + (str.charAt(j) - '0');j++;}num.push(x);i = j - 1;} else if (c == '(') {op.push(c);} else if (c == ')') {while (op.peek() != '(') {eval();}op.pop();} else {while (!op.empty() && op.peek() != '(' && map.get(op.peek()) >= map.get(c)) {eval();}op.push(c);}}while (!op.empty())eval();System.out.println(num.peek());}public static void eval() {int b = num.pop();int a = num.pop();char c = op.pop();switch(c) {case '+': {num.push(a + b);break;}case '-': {num.push(a - b);break;}case '*': {num.push(a * b);break;}case '/': {num.push(a / b);break;}}}
}

Trie树的应用——最大异或对

• 例题：AcWing 143. 最大异或对

import java.util.Scanner;public class Main {public static final int N = 100010;public static final int M = 3000000;public static int n;public static int[][] son = new int[M][2];public static int idx;public static int[] a = new int[N];public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();insert(a[i]);}int res = 0;for (int i = 0; i < n; i++)res = Math.max(res, query(a[i]));System.out.println(res);}public static void insert(int x) {int p = 0;for (int i = 30; i >= 0; i--) {int s = son[p][x >> i & 1];if (s == 0)son[p][x >> i & 1] = ++idx;p = son[p][x >> i & 1];}}public static int query(int x) {int res = 0;int p = 0;for (int i = 30; i >= 0; i--) {int s = x >> i & 1;if (son[p][1 - s] != 0) {res += 1 << i;p = son[p][1 - s];} elsep = son[p][s];}return res;}
}

并查集的应用——食物链

• 例题：AcWing 240. 食物链

import java.util.Scanner;public class Main {public static int N = 50010;public static int n;public static int m;public static int[] p = new int[N];public static int[] d = new int[N];public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();for (int i = 1; i <= n; i++)p[i] = i;int res = 0;while (m-- != 0) {int t, x, y;t = scanner.nextInt();x = scanner.nextInt();y = scanner.nextInt();if (x > n || y > n)res++;else {int px = find(x);int py = find(y);if (t == 1) {if (px == py && ((d[x] - d[y]) % 3 != 0))res++;else if (px != py) {p[px] = py;d[px] = d[y] - d[x];}} else {if (px == py && ((d[x] - d[y] - 1) % 3 != 0))res++;else if (px != py) {p[px] = py;d[px] = d[y] + 1 - d[x];}}}}System.out.println(res);}public static int find(int x) {if (p[x] != x) {int t = find(p[x]);d[x] += d[p[x]];p[x] = t;}return p[x];}
}