链表、栈与队列
链表与邻接表
单链表：出现最多的是邻接表，用于存储树和图
双链表：多用于优化某些问题
为什么用数组模拟链表？ Java 中每 new 一个链表节点对象都要动态分配内存、记录对象头，开销大且慢；而竞赛题的链表长度通常已知，可以直接开好静态数组，用下标代替指针，速度快、代码短。
单链表（邻接表的底层结构）： head 存头结点下标（-1 表示空链表），e[idx] 存节点的值，ne[idx] 存下一个节点的下标，idx 记录当前可用的新节点下标。头插法三步：新节点存值 → 新节点指向原头 → head 指向新节点。
双链表： 每个节点记录左右邻居 l[idx]、r[idx]。用 0 号节点当”左哨兵”、1 号节点当”右哨兵”，所有操作都发生在两个哨兵之间，插入、删除就不需要特判边界，这是双链表最经典的技巧。
单链表
import java.util.*;public class Main{ static int idx = 0; static int[] e = new int[10010]; static int[] ne = new int[10010]; static int head; public static void init(){ head = -1; idx = 0;
} public static void add_to_head(int x){ e[idx] = x; ne[idx] = head; head = idx; idx++; } public static void add(int k,int x){ e[idx]= x; ne[idx] = ne[k]; ne[k] = ne[ne[k]]; idx++; } public static void remove(int k){ ne[k] = ne[ne[k]]; } public static void main(String[] args){
}}双链表
import java.util.*;public class Main{ static int[] e = new int[10010]; static int[] l = new int[10010]; static int[] r = new int[10010]; int idx; public static void init(){ r[0] = 1; l[1] = 0; idx= 2; } public static void add(int k , int x){ e[idx] = x; l[idx] = k; r[idx] = r[k]; l[r[k]] = idx; r[k] = idx; } pubilc static void remove(int k){ l[r[k]] = l[k]; r[l[k]] = r[k]; } public static void main(String args[]){ //双链表 }}栈与队列
栈（Stack）： 后进先出（LIFO）。数组模拟只需要一个栈顶指针 tt：入栈 stack[++tt] = x，出栈 tt--，栈顶即 stack[tt]。
队列（Queue）： 先进先出（FIFO）。数组模拟需要队头指针 hh 和队尾指针 tt：入队 queue[++tt] = x，出队 hh++。队列为空当且仅当 hh > tt。
代码定义栈
int[] stack = new int[10010];int tt;插入
stack[++tt] = x;弹出
tt--;判断是否为空
if(tt > 0){ not empty;}else{ is empty;}取出栈顶元素
stack[tt]代码定义队列
int[] queue = new int[10010];int tt;int hh;在队尾插入元素，在队头弹出元素
queue[++tt] = x;hh++;判断队列为空
if(hh <= tt) not empty;else empty取队头元素
queue[tt];queue[hh];单调栈
单调栈的应用
作用类似双指针，都是通过找到某种性质来优化时间复杂度,多用于在一个序列中查找一个数(k)左边最近的一个比它小的数。思路是
在一个序列中，如果有a[i] > a[j] 且 j > i 那么在查找时a[j]就是更优解而a[i]是一个永远不会用到的数，从此可以得出思路就是将满足
a[i] > a[j] j > i 时的a[i]删掉，从而使得栈中的数是单调的，形成单调栈，如果 k <= stack[tt] 那么就将 stack[tt]删去，反之stack[tt]就是正确答案
原理再讲一遍： 对于”找每个数左边第一个比它小的数”这类问题，我们维护一个栈底到栈顶递增的栈。新数 x 入栈前，把栈顶所有 ≥ x 的元素弹掉——因为这些元素比 x 大、位置又比 x 靠左，对于 x 之后的所有查询来说，x 都更小、更靠右，永远更优，那些元素再也不可能成为答案。弹完之后：
- 栈顶（如果还有）就是 x 左边第一个比 x 小的数；
- 再把 x 压入栈，保持栈内单调递增。
每个元素最多入栈一次、出栈一次，总复杂度 O(n)。
import java.util.*;public class Main{ public static void main(String args[]){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] stk = new int[n]; int tt = 0; for (int i = 0; i < n; i++) { int x= sc.nextInt(); while(tt > 0 && stk[tt] >= x){ tt--; } if(tt > 0) System.out.print(stk[tt] + " "); else System.out.print(-1 + " "); stk[ ++ tt] = x; }
}}单调队列（滑动窗口）
单调队列的应用
给定一个长度为
n ≤ 10^6的数组。 有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。 你只能在窗口中看到k个数。 每次滑动窗口向右移动一个位置。以下是一个例子： 该数组为
[1, 3, -1, -3, 5, 3, 6, 7]，k为 3。
窗口位置 最小值 最大值 [1, 3, -1], -3, 5…-1 3 1, [3, -1, -3], 5…-3 3 1, 3, [-1, -3, 5],…-3 5 … … …
思路： 单调队列是”滑动窗口 + 单调性”的组合。队列里存下标（因为要判断下标是否滑出窗口），并保持”队头到队尾对应元素单调”：
- 过期弹出： 窗口右移时，若队头下标已经滑出窗口（
i - k + 1 > q[hh]），把队头弹出； - 维护单调： 新元素 a[i] 入队前，从队尾弹出所有”比 a[i] 更差的元素”——求最小值时弹掉 ≥ a[i] 的（它们更大且更早离开窗口，永远没机会当最小值），求最大值时弹掉 ≤ a[i] 的；
- 答案： 队头就是当前窗口的最小值/最大值，
i ≥ k-1（窗口第一次装满）之后开始输出。
每个元素最多入队、出队各一次，总复杂度 O(n)。
import java.util.*;public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[] a = new int[10010]; int[] q = new int[10010]; int hh = 0; int tt = -1; for(int i = 0 ;i<n;i++){ a[i] = sc.nextInt(); } for (int i = 0; i < n; i++) { //判断站是否为空，并且栈顶元素是否出栈 if(hh <= tt && i - k + 1 > q[hh]) hh++; while(hh <= tt && a[i] <= a[q[tt]]) 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[i] >= a[q[tt]]) tt--; q[++tt] = i; if(i>=k-1) System.out.print(a[q[hh]] + " "); }
}}如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时