28、指针与数据结构：栈、队列、树的指针实现

各位同学，今天我们来聊聊指针在数据结构里的核心作用。说实话，我当年学数据结构时，最头疼的就是指针。但后来做了十几年嵌入式开发，我才真正明白——没有指针，很多数据结构根本玩不转。

栈、队列、树，这些听起来抽象的概念，底层全靠指针在撑。你想想看，如果没有指针，你怎么让一个节点“指向”另一个节点？数组？那只能顺序访问，灵活性差太多了。

指针为什么是数据结构的灵魂？

我个人的理解是：指针提供了“连接”的能力。数据结构说白了就是数据之间的关系，而指针就是描述这种关系的工具。

• 静态数组：数据在内存里排排坐，位置固定
• 指针链表：数据可以散落在任何地方，指针告诉你怎么找到下一个

我在项目中遇到过一个问题：用数组实现栈，栈大小固定，一旦满了就崩。后来改用指针实现的链式栈，动态分配内存，再也没出过这问题。

栈的指针实现

栈，先进后出。用数组实现很简单，但用指针实现更灵活。我习惯用单链表来实现栈——入栈就是在链表头部插入，出栈就是删除头部节点。

// 链式栈的节点定义
typedef struct StackNode {
    int data;
    struct StackNode* next;
} StackNode;

// 栈结构体（只保存栈顶指针）
typedef struct {
    StackNode* top;
    int size;
} LinkedStack;

// 入栈操作
void push(LinkedStack* stack, int value) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    if (!newNode) return;  // 内存分配失败
    
    newNode->data = value;
    newNode->next = stack->top;  // 新节点指向原来的栈顶
    stack->top = newNode;        // 更新栈顶
    stack->size++;
}

// 出栈操作
int pop(LinkedStack* stack) {
    if (stack->top == NULL) {
        printf("栈已空\n");
        return -1;
    }
    StackNode* temp = stack->top;
    int value = temp->data;
    stack->top = temp->next;  // 栈顶下移
    free(temp);
    stack->size--;
    return value;
}

你看，这里最关键的就是 stack->top = newNode->next 和 stack->top = temp->next 这两行。说白了，就是通过指针的重新指向，完成了节点的插入和删除。时间复杂度 O(1)，非常高效。

队列的指针实现

队列，先进先出。用数组实现队列有个问题：出队后前面的空间就浪费了。用指针实现就没有这个烦恼。

队列需要两个指针：front 指向队头，rear 指向队尾。入队操作在 rear 后面加节点，出队操作删除 front 节点。

// 链式队列的节点定义
typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

// 队列结构体
typedef struct {
    QueueNode* front;  // 队头指针
    QueueNode* rear;   // 队尾指针
    int size;
} LinkedQueue;

// 入队
void enqueue(LinkedQueue* queue, int value) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (!newNode) return;
    
    newNode->data = value;
    newNode->next = NULL;
    
    if (queue->rear == NULL) {
        // 队列为空
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;  // 原队尾指向新节点
        queue->rear = newNode;        // 更新队尾
    }
    queue->size++;
}

// 出队
int dequeue(LinkedQueue* queue) {
    if (queue->front == NULL) {
        printf("队列已空\n");
        return -1;
    }
    QueueNode* temp = queue->front;
    int value = temp->data;
    queue->front = temp->next;  // 队头后移
    
    if (queue->front == NULL) {
        queue->rear = NULL;  // 队列变空，rear也要置空
    }
    free(temp);
    queue->size--;
    return value;
}

树的指针实现

树，这是指针发挥到极致的数据结构。每个节点可以有多个子节点，全靠指针来维系。

二叉树是最常见的树结构。每个节点有三个指针：左孩子、右孩子，以及（可选）父节点。

// 二叉树节点定义
typedef struct TreeNode {
    int data;
    struct TreeNode* left;   // 左孩子指针
    struct TreeNode* right;  // 右孩子指针
    struct TreeNode* parent; // 父节点指针（可选）
} TreeNode;

// 创建新节点
TreeNode* createNode(int value) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    if (!node) return NULL;
    
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    return node;
}

// 插入左孩子
void insertLeft(TreeNode* parent, int value) {
    if (parent->left != NULL) {
        printf("左孩子已存在\n");
        return;
    }
    TreeNode* child = createNode(value);
    if (child) {
        parent->left = child;
        child->parent = parent;
    }
}

// 前序遍历（递归）
void preorder(TreeNode* root) {
    if (root == NULL) return;
    
    printf("%d ", root->data);   // 访问根节点
    preorder(root->left);        // 遍历左子树
    preorder(root->right);       // 遍历右子树
}

你看，树的遍历本质上就是沿着指针走。递归也好，非递归也好，核心都是通过指针从一个节点跳到另一个节点。

我做过一个项目，需要快速查找数据。用数组？查找 O(n)。用二叉搜索树？查找 O(log n)。为什么？因为指针让树可以二分查找——每次比较后，通过 left 或 right 指针直接跳到下一层，不用遍历所有数据。

指针在数据结构中的核心作用

总结一下，指针在数据结构里到底扮演了什么角色？我归纳了三点：

作用	说明	举例
连接	把分散的内存块串起来	链表中的 next 指针
定位	快速找到目标节点	树的 left/right 指针
动态扩展	运行时分配新节点，改变结构	栈的 push 操作

说白了，没有指针，数据结构就是一堆死数据。有了指针，数据才有了“关系”，才有了“结构”。

知识体系图

下面这张图展示了指针与三种数据结构的关系：

这张图想表达的是：指针是中心，栈、队列、树都依赖指针来实现各自的结构特性。没有指针，这些数据结构就失去了“动态”的灵魂。

避坑指南

最后，分享几个我踩过的坑：

• 野指针：节点释放后，记得把指针置 NULL。我早期写代码时经常忘了，结果程序跑着跑着就崩了。
• 内存泄漏：用 malloc 分配了节点，用完一定要 free。嵌入式设备内存小，泄漏几次就挂了。
• 空指针检查：每次访问指针前，先判断是不是 NULL。这个习惯救了我很多次。

好了，指针与数据结构就讲到这里。记住一句话：指针是数据结构的骨架，没有它，数据就是一盘散沙。

---

公众号:蓝海资料掘金营，微信deep3321