用C++动手实现常见数据结构，代码实战不迷路

从数组到链表：基础但关键

写程序时，总免不了和数据打交道。比如你做个学生成绩管理系统，得存一堆人名和分数。这时候直接上数组当然行，但要是人数不固定呢？删一个、加一个，数组就有点卡手了。

C++里可以用结构体和指针搭出链表，灵活多了。下面是个简单的单链表节点定义：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

每次插入新学生，就new一个节点接上去，不用提前算好数组大小，也不用整体搬移数据，特别适合频繁增删的场景。

栈和队列：后进先出 vs 先进先出

你去食堂打饭，排队的人按顺序来——这就是队列。后面来的排末尾，前面的先打上饭走人。C++里可以用deque或者自己用链表实现一个队列：

class Queue {
private:
    ListNode* front;
    ListNode* rear;
public:
    Queue() : front(nullptr), rear(nullptr) {}
    
    void enqueue(int x) {
        ListNode* node = new ListNode(x);
        if (!rear) {
            front = rear = node;
        } else {
            rear->next = node;
            rear = node;
        }
    }

    int dequeue() {
        if (!front) return -1; // 表示空
        ListNode* temp = front;
        int val = temp->val;
        front = front->next;
        if (!front) rear = nullptr;
        delete temp;
        return val;
    }
};

而栈就像你桌上那摞书，最新放上去的最方便拿。函数调用底层就是靠栈实现的。C++标准库有stack，但自己实现一遍能更清楚它的逻辑。

二叉树：分叉的逻辑结构

家谱图、组织架构图，这些有层级关系的数据，用线性结构就不好表达了。二叉树在这种时候就很实用。每个节点最多两个孩子，左和右。

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : data(x), left(nullptr), right(nullptr) {}
};

比如你要实现一个简单的决策判断系统，每个节点代表一个问题，左走是“是”，右走是“否”，一路走到叶子节点得出结论。这种结构清晰又高效。

用STL还是自己写？

C++标准库提供了vector、list、queue、stack、map这些现成的容器，大多数情况下直接用就行，稳定又省事。但理解它们背后的实现原理，能帮你选对工具，也能在特殊需求下做定制优化。

比如你知道vector底层是动态数组，连续内存，访问快但中间插入慢；而list是双向链表，插入删除快但访问得遍历。项目里要频繁插删元素，还要求实时响应，这时候你就不会盲目用vector了。

再比如面试写算法题，经常需要自己构建数据结构。平时练熟了，到关键时刻才不会卡壳。