第三章：数据结构基础——数组、链表、栈、队列在游戏中的典型应用

大家好，我是你们的老朋友。今天我们来聊聊游戏开发里最基础、也最绕不开的东西——数据结构。

说实话，我见过不少新手，一上来就急着学渲染、学物理引擎，结果写背包系统时发现物品取不出来，做命令历史时发现撤销不了。为什么？说白了，就是数据结构没选对。

这一章，我会结合我实际做项目时踩过的坑，把数组、链表、栈、队列这四种结构在游戏里的典型用法讲透。你想想看，这些东西学会了，以后写代码心里就有底了。

3.1 数组：背包系统的“老黄牛”

数组，大家最熟了。连续内存、随机访问快，但插入删除慢。在游戏里，最适合它的场景就是固定大小的背包系统。

我记得有一次做一款MMORPG，背包格子固定为64格。一开始有人提议用链表，说灵活。我直接否了——背包里经常要按索引取物品（比如玩家点第5格），数组的O(1)随机访问，链表做不到。

核心思路：用数组存储物品ID，空位用-1或0表示。

// 背包系统：固定64格
#define BACKPACK_SIZE 64
int backpack[BACKPACK_SIZE]; // -1表示空

// 初始化背包
void InitBackpack() {
    for (int i = 0; i < BACKPACK_SIZE; i++) {
        backpack[i] = -1;
    }
}

// 添加物品（找到第一个空位）
int AddItem(int itemId) {
    for (int i = 0; i < BACKPACK_SIZE; i++) {
        if (backpack[i] == -1) {
            backpack[i] = itemId;
            return i; // 返回格子索引
        }
    }
    return -1; // 背包满了
}

// 使用物品（按索引取）
int UseItem(int slotIndex) {
    if (slotIndex < 0 || slotIndex >= BACKPACK_SIZE) return -1;
    int itemId = backpack[slotIndex];
    backpack[slotIndex] = -1;
    return itemId;
}

我的小技巧：如果背包需要排序（比如按品质排列），可以用数组+索引排序法，不移动实际数据，只移动索引数组。这样性能好很多。

3.2 链表：动态装备栏与技能链

链表的好处是插入删除快，但随机访问慢。在游戏里，最适合它的地方是动态变化的装备栏或技能连招系统。

我曾经做过一个动作游戏，玩家可以随时更换装备，而且装备数量不固定。用数组的话，每次插入都要移动大量数据，卡顿明显。换成链表后，问题迎刃而解。

// 装备链表节点
typedef struct EquipNode {
    int equipId;
    struct EquipNode* next;
} EquipNode;

// 在头部插入装备（穿装备）
void EquipItem(EquipNode** head, int equipId) {
    EquipNode* newNode = (EquipNode*)malloc(sizeof(EquipNode));
    newNode->equipId = equipId;
    newNode->next = *head;
    *head = newNode;
}

// 卸下指定装备（删除节点）
void UnequipItem(EquipNode** head, int equipId) {
    EquipNode *prev = NULL, *curr = *head;
    while (curr) {
        if (curr->equipId == equipId) {
            if (prev) prev->next = curr->next;
            else *head = curr->next;
            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    }
}

避坑指南：我曾经在链表里忘记处理头节点删除的情况，结果内存泄漏加野指针，查了一整天。记住：删除头节点时，一定要更新头指针。

3.3 栈：命令历史与撤销系统

栈，后进先出。游戏里最常见的应用就是命令历史和撤销/重做。

我记得做RTS游戏时，玩家需要撤销上一步操作。用栈来存命令，简直天造地设。每次执行命令就压栈，撤销就弹栈。

// 命令历史栈
#define CMD_STACK_SIZE 20
typedef struct {
    int cmdType;   // 命令类型
    int param1;    // 参数1
    int param2;    // 参数2
} Command;

Command cmdStack[CMD_STACK_SIZE];
int cmdTop = -1; // 栈顶指针

// 执行命令并压栈
void ExecuteCommand(int type, int p1, int p2) {
    if (cmdTop < CMD_STACK_SIZE - 1) {
        cmdTop++;
        cmdStack[cmdTop].cmdType = type;
        cmdStack[cmdTop].param1 = p1;
        cmdStack[cmdTop].param2 = p2;
        // 实际执行命令...
    }
}

// 撤销：弹出栈顶命令
Command UndoCommand() {
    Command empty = {-1, 0, 0};
    if (cmdTop >= 0) {
        Command cmd = cmdStack[cmdTop];
        cmdTop--;
        // 执行撤销逻辑...
        return cmd;
    }
    return empty;
}

我的习惯：栈的大小一定要有限制，否则玩家操作多了会爆内存。我一般设20-50步，超过就丢弃最老的命令。

3.4 队列：消息队列与技能冷却

队列，先进先出。游戏里最典型的应用是消息队列和技能冷却队列。

你想想看，玩家连续按技能，如果服务器一下子全处理，那不乱套了？用队列把技能请求排好队，一个一个处理，既公平又稳定。

// 技能冷却队列
#define SKILL_QUEUE_SIZE 10
typedef struct {
    int skillId;
    int cooldownTime; // 剩余冷却时间（帧数）
} SkillRequest;

SkillRequest skillQueue[SKILL_QUEUE_SIZE];
int queueHead = 0, queueTail = 0, queueCount = 0;

// 入队：玩家释放技能
int EnqueueSkill(int skillId, int cooldown) {
    if (queueCount >= SKILL_QUEUE_SIZE) return -1; // 队列满
    skillQueue[queueTail].skillId = skillId;
    skillQueue[queueTail].cooldownTime = cooldown;
    queueTail = (queueTail + 1) % SKILL_QUEUE_SIZE;
    queueCount++;
    return 0;
}

// 出队：每帧处理一个技能
SkillRequest DequeueSkill() {
    SkillRequest empty = {-1, 0};
    if (queueCount == 0) return empty;
    SkillRequest req = skillQueue[queueHead];
    queueHead = (queueHead + 1) % SKILL_QUEUE_SIZE;
    queueCount--;
    return req;
}

关键点：队列用循环数组实现，避免频繁的内存分配。我做过测试，循环队列比链表队列快3倍以上。

3.5 如何选择？一张表说清楚

很多同学问我：到底什么时候用数组，什么时候用链表？我整理了一张表，你一看就明白。

数据结构 优点 缺点 游戏典型场景
数组 随机访问快，内存连续 插入删除慢，大小固定 背包系统、固定网格地图
链表 插入删除快，动态大小 随机访问慢，内存碎片 装备栏、技能链、动态对象列表
栈 后进先出，实现简单 不能随机访问 命令历史、撤销系统、递归调用
队列 先进先出，公平有序 不能随机访问 消息队列、技能冷却、AI行为队列

我的建议：别死记硬背。写代码前先问自己三个问题：数据量固定还是动态？访问频繁还是插入删除频繁？需要顺序处理还是随机处理？答案出来了，数据结构自然就定了。

3.6 实战小项目：简易背包+命令历史

最后，我带你做一个综合小练习。把数组背包和栈命令历史结合起来，实现一个可撤销操作的背包系统。

// 综合示例：可撤销的背包操作
#define MAX_BACKPACK 10
int backpack[MAX_BACKPACK];

// 命令历史栈（记录每次操作）
typedef enum { OP_ADD, OP_REMOVE } OpType;
typedef struct {
    OpType type;
    int slotIndex;
    int oldItemId; // 用于撤销
} HistoryCmd;

HistoryCmd history[50];
int historyTop = -1;

// 添加物品（带历史记录）
int AddItemWithHistory(int itemId) {
    for (int i = 0; i < MAX_BACKPACK; i++) {
        if (backpack[i] == -1) {
            backpack[i] = itemId;
            // 记录操作
            if (historyTop < 49) {
                historyTop++;
                history[historyTop].type = OP_ADD;
                history[historyTop].slotIndex = i;
                history[historyTop].oldItemId = -1;
            }
            return i;
        }
    }
    return -1;
}

// 撤销上一次操作
void UndoLastOp() {
    if (historyTop < 0) return;
    HistoryCmd cmd = history[historyTop];
    historyTop--;
    if (cmd.type == OP_ADD) {
        backpack[cmd.slotIndex] = -1; // 撤销添加
    } else if (cmd.type == OP_REMOVE) {
        backpack[cmd.slotIndex] = cmd.oldItemId; // 撤销删除
    }
}

嗯，这个例子虽然简单，但包含了数组和栈的核心用法。你把它跑通了，背包系统和命令历史就都掌握了。

好了，这一章就到这里。下一章我们会聊更高级的数据结构——树和图，它们在游戏AI和场景管理里大有用处。到时候见！

← 上一章 📖 返回目录 下一章 →