本文介绍了使用数组模拟单链表、双链表、栈、队列及优先队列（堆）的实现方法。通过对比内置类开销，阐述了静态数组模拟的优势。提供了核心操作代码模板，并结合典型算法题目展示了具体应用场景，如括号匹配、机器翻译及取模优化问题。旨在帮助开发者深入理解数据结构底层原理并提升算法竞赛效率。
在算法竞赛中，直接使用 Java 内置的 LinkedList、Stack 等类，往往会因为封装和对象创建的开销导致超时。因此，用数组模拟数据结构是算法竞赛中的核心技能。它不仅能将时间复杂度优化到极致，还能更深刻地理解数据结构的底层原理。
本文将详细讲解如何用数组模拟单链表、双链表、栈、队列和优先队列（堆）的核心内容，结合 OJ 平台的经典例题，提供可直接复用的代码模板。
链表是一种线性数据结构，它不要求数据在内存中连续存储，而是通过指针将一个个独立的节点串联起来。在数组模拟中，我们用数组下标来代替指针。
单链表的每个节点只包含一个指向下一个节点的指针。它的特点是只能从头向尾遍历，无法直接访问前驱节点。
e[] 数组：e[i] 表示地址为 i 的节点的下一个节点的地址（数组下标）。data[] 数组：data[i] 表示地址为 i 的节点存储的数据。head 和 tail：分别指向链表的头节点和尾节点。头节点通常是哨兵节点，不存放数据。idx：记录当前已使用的内存空间，用于分配新节点。用 -1 表示空指针。删除指定节点后的节点：
// 删除地址为 adr 的节点的下一个节点（adr 不能是尾节点）
void delete_next(int adr) {
e[adr] = e[e[adr]]; // 让 adr 节点直接指向它下下个节点
}
在指定节点后插入节点：
// 将值 val 插入到地址为 adr 的节点之后
void insert_after(int adr, int val) {
++idx; // 分配新节点地址
e[idx] = e[adr]; // 新节点的 next 指向 adr 节点原来的 next
e[adr] = idx; // adr 节点的 next 指向新节点
data[idx] = val; // 新节点存储数据
}
在尾部插入节点：
// 将值 val 插入到链表尾部
void insert_to_tail(int val) {
e[tail] = ++idx; // 原尾节点的 next 指向新节点
e[idx] = -1; // 新节点的 next 为空
data[idx] = val; // 新节点存储数据
tail = idx; // 更新尾节点
}
初始化：
int head = 0, tail = 0, idx = 0;
int[] e = new int[N];
int[] data = new int[N];
Arrays.fill(e, -1); // 初始化所有指针为空
双链表在单链表的基础上，为每个节点增加了一个指向前驱节点的指针，因此可以双向遍历，插入和删除操作也更加灵活。
next[] 数组：next[i] 表示地址为 i 的节点的下一个节点地址。pre[] 数组：pre[i] 表示地址为 i 的节点的上一个节点地址。0 作为哨兵节点，将链表首尾相连，方便操作。题目大意：初始有 1~n 按顺序排列，进行 m 次操作，每次将数字 x 移动到数字 y 的前面或后面，求最终顺序。
解题思路：移动节点的通用操作是'先删除，再插入'。
x：找到 x 的前驱 a 和后继 b，让 a 和 b 直接相连。x：将 x 插入到目标位置 y 的后面。如果要求插入到前面，则先找到 y 的前驱 pre[y]，再插入到 pre[y] 后面。Java 代码实现：
import java.util.Scanner;
public class Main {
static int N = (int) 1e4 + 10;
static int[] pre = new int[N];
static int[] next = new int[N];
// 删除节点 x
static void remove(int x) {
int a = pre[x];
int b = next[x];
next[a] = b;
pre[b] = a;
}
// 将 x 插入到 y 的后面
static void add(int x, int y) {
int z = next[y];
pre[z] = x;
pre[x] = y;
next[y] = x;
next[x] = z;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
// 初始化双链表 1<->2<->...<->n
for (int i = 1; i < n; i++) {
pre[i] = i - 1;
next[i] = i + 1;
}
next[0] = 1;
pre[0] = n; // 哨兵 0
next[n] = 0;
pre[n] = n - 1;
while (m-- > 0) {
int x = scan.nextInt();
int y = scan.nextInt();
int z = scan.nextInt();
// z=1 表示插到 y 前面，z=0 表示插到 y 后面
if (z == 1) {
y = pre[y]; // 插到 y 前面等价于插到 pre[y] 后面
}
// z=0 表示 x 插到 y 后面 (默认)
remove(x);
add(x, y);
}
// 遍历输出
for (int i = next[0]; i > 0; i = next[i]) {
System.out.print(i + " ");
}
scan.close();
}
}
栈是一种'后进先出'（LIFO）的数据结构，只能在栈顶进行插入和删除操作。数组模拟栈非常高效。
stk[] 数组：用于存储栈内元素。top 变量：指向栈顶元素。初始化时 top = 0 表示栈空。stk[++top] = x;top--;stk[top];top == 0;题目大意：判断一个由 ( 和 ) 组成的括号串是否合法。
解题思路：经典的栈应用。
( 就入栈（用 top++ 模拟）。) 时，如果栈不为空（top > 0），则出栈（top--）；如果栈为空，说明括号不合法。top == 0），则所有括号都匹配，合法；否则不合法。Java 代码实现：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
char[] c = scan.next().toCharArray();
int top = 0;
boolean valid = true;
for (char x : c) {
if (x == '(') {
top++;
} else {
top--;
if (top < 0) { // 遇到多余的 ')'
valid = false;
break;
}
}
}
if (top != 0) { // 有多余的 '(' 未匹配
valid = false;
}
System.out.println(valid ? "Yes" : "No");
scan.close();
}
}
队列是一种'先进先出'（FIFO）的数据结构，元素从队尾入队，从队头出队。
q[] 数组：用于存储队列元素。h（head）：队头指针，指向队头元素。t（tail）：队尾指针，指向队尾元素。h = 1, t = 0。此时 h > t，表示队列为空。有效元素区间为 [h, t]。q[++t] = x;h++;q[h];t - h + 1 == 0 或 h > t。题目大意：模拟一个内存容量为 M 的翻译软件。文章有 N 个单词。如果单词在内存中，直接翻译；否则查词典（计数 +1），并将单词加入内存。如果内存满了，就删除最早进入内存的单词（FIFO）。
解题思路：用队列模拟内存。
x。x 是否在内存中。如果在，跳过。res++。t-h+1）大于 M，则队头元素出队（h++）。x 入队。Java 代码实现：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int m = scan.nextInt(); // 内存容量
int n = scan.nextInt(); // 单词数
int[] queue = new int[n + 1];
int h = 1, t = 0, res = 0;
for (int i = 0; i < n; i++) {
int x = scan.nextInt();
boolean f = true;
// 扫描队列，检查 x 是否在内存中
for (int j = h; j <= t; j++) {
if (queue[j] == x) {
f = false;
break;
}
}
if (f) { // 不在内存中，需要查词典
res++;
queue[++t] = x;
// 如果内存满了，先出队
if (t - h + 1 > m) {
++h;
}
}
}
System.out.println(res);
scan.close();
}
}
优先队列是一种队列数据结构实现，其中元素根据优先级处理，而非先进先出。在优先队列中，添加的对象根据其优先级排序，默认情况下，优先级由对象的自然顺序决定，队列构建时提供的比较器可以覆盖默认优先级。
优先队列的底层实现就是一个堆，它可以维护一个集合的最大值（大顶堆）或最小值（小顶堆），并能在优秀的对数时间复杂度（O(log n)）内完成查询、插入（push）和删除（pop）操作。
i，其左孩子为 2*i，右孩子为 2*i+1，父节点为 i/2。题目大意：给定一个数组 a，共有 q 次操作，每次操作给定一个值 x，对数组的每个元素对 x 进行一次取模，输出每次操作后数组所有元素的和。
解题思路：
x 的元素进行取模，然后将取模后的值重新插入堆中。Java 代码实现：
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int q = scan.nextInt();
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
long sum = 0;
for (int i = 0; i < n; i++) {
int x = scan.nextInt();
queue.add(x);
sum += x;
}
while (q-- > 0) {
int k = scan.nextInt();
while (!queue.isEmpty() && queue.peek() >= k) {
int x = queue.poll();
sum -= x;
sum += x % k;
queue.add(x % k);
}
System.out.println(sum);
}
scan.close();
}
}
| 数据结构 | 核心数组/变量 | 核心操作 | 典型应用 |
|---|---|---|---|
| 单链表 | e[], data[], head, tail, idx | 头/尾插、指定位置插删 | 邻接表、静态链表 |
| 双链表 | pre[], next[] | 任意位置插删（O(1)） | 重新排队、LRU 缓存 |
| 栈 | stk[], top | push, pop | 括号匹配、表达式求值、DFS |
| 队列 | q[], h, t | enqueue, dequeue | BFS、缓冲区、FIFO 替换策略 |
| 优先队列（堆） | heap[], size | push, pop, peek | TopK 问题、贪心算法、事件调度 |
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online