数组模拟链表、栈、队列与优先队列：高效实现与性能对比
一、前言
在算法竞赛中，直接使用 Java 内置的 LinkedList、Stack 等类，往往会因为封装和对象创建的开销导致超时。因此，用数组模拟数据结构是算法竞赛中的核心技能。它不仅能将时间复杂度优化到极致，还能更深刻地理解数据结构的底层原理。
本文将详细讲解如何用数组模拟单链表、双链表、栈、队列和优先队列（堆）的核心内容，结合 OJ 平台的经典例题，提供可直接复用的代码模板。
二、链表
链表是一种线性数据结构，它不要求数据在内存中连续存储，而是通过指针将一个个独立的节点串联起来。在数组模拟中，我们用数组下标来代替指针。
2.1 单链表
单链表的每个节点只包含一个指向下一个节点的指针。它的特点是只能从头向尾遍历，无法直接访问前驱节点。
2.1.1 核心思想
e[]数组：e[i]表示地址为i的节点的下一个节点的地址（数组下标）。data[]数组：data[i]表示地址为i的节点存储的数据。head和tail：分别指向链表的头节点和尾节点。头节点通常是哨兵节点，不存放数据。idx：记录当前已使用的内存空间，用于分配新节点。用-1表示空指针。
2.1.2 核心操作
删除指定节点后的节点：
// 删除地址为 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( val) {
e[tail] = ++idx;
e[idx] = -;
data[idx] = val;
tail = idx;
}
