数组模拟链表、栈、队列与优先队列：高效实现与性能对比

数组模拟链表、栈、队列与优先队列（附OJ实战）

一、前言

在算法竞赛中，直接使用Java内置的LinkedList、Stack等类，往往会因为封装和对象创建的开销导致超时。因此，用数组模拟数据结构是蓝桥杯等竞赛中必备的核心技能。它不仅能将时间复杂度优化到极致，还能更深刻地理解数据结构的底层原理。

本文将详细讲解如何用数组模拟单链表、双链表、栈、队列和优先队列（堆）的核心内容，结合蓝桥OJ的经典例题，提供可直接复用的代码模板。

二、链表

链表是一种线性数据结构，它不要求数据在内存中连续存储，而是通过指针将一个个独立的节点串联起来。在数组模拟中，我们用数组下标来代替指针。

2.1 单链表

单链表的每个节点只包含一个指向下一个节点的指针。它的特点是只能从头向尾遍历，无法直接访问前驱节点。

2.1.1 核心思想

• e[]数组：e[i] 表示地址为 i 的节点的下一个节点的地址（数组下标）。
• data[]数组：data[i] 表示地址为 i 的节点存储的数据。
• head 和 tail：分别指向链表的头节点和尾节点。头节点通常是哨兵节点，不存放数据。
• idx：记录当前已使用的内存空间，用于分配新节点。用 -1 表示空指针。

2.1.2 核心操作

2.2 双链表

双链表在单链表的基础上，为每个节点增加了一个指向前驱节点的指针，因此可以双向遍历，插入和删除操作也更加灵活。

2.2.1 核心思想

• next[]数组：next[i] 表示地址为 i 的节点的下一个节点地址。
• pre[]数组：pre[i] 表示地址为 i 的节点的上一个节点地址。
• 哨兵节点：通常用 0 作为哨兵节点，将链表首尾相连，方便操作。

2.2.2 经典例题：蓝桥OJ 3255 – 重新排队

题目大意：初始有 1~n 按顺序排列，进行 m 次操作，每次将数字 x 移动到数字 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）的数据结构，只能在栈顶进行插入和删除操作。数组模拟栈非常高效。

3.1 核心思想

• stk[]数组：用于存储栈内元素。
• top变量：指向栈顶元素。初始化时 top = 0 表示栈空。

3.2 核心操作

3.3 经典例题：蓝桥OJ 2490 – 小蓝的括号串1

题目大意：判断一个由 ( 和 ) 组成的括号串是否合法。

解题思路：经典的栈应用。

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）的数据结构，元素从队尾入队，从队头出队。

4.1 核心思想

• q[]数组：用于存储队列元素。
• h（head）：队头指针，指向队头元素。
• t（tail）：队尾指针，指向队尾元素。
• 初始化：h = 1, t = 0。此时 h > t，表示队列为空。有效元素区间为 [h, t]。

4.2 核心操作

4.3 经典例题：蓝桥OJ 511 – 机器翻译

题目大意：模拟一个内存容量为 M 的翻译软件。文章有 N 个单词。如果单词在内存中，直接翻译；否则查词典（计数+1），并将单词加入内存。如果内存满了，就删除最早进入内存的单词（FIFO）。

解题思路：用队列模拟内存。

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）操作。

5.1 核心思想

• 堆（Heap）：优先队列的核心是堆，它是一个完全二叉树。
  • 大顶堆：父节点的值大于等于子节点的值，堆顶为最大值。
  • 小顶堆：父节点的值小于等于子节点的值，堆顶为最小值。
• 数组模拟：在竞赛中，常用数组来模拟堆。数组下标从1开始，对于节点i，其左孩子为2*i，右孩子为2*i+1，父节点为i/2。

5.2 核心操作

5.3 经典例题：蓝桥OJ 3343 – 简单的取模问题

题目大意：给定一个数组 a，共有 q 次操作，每次操作给定一个值 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();
}
}

六、总结