C语言数据结构：动态栈（链式存储）的实现与详解

慢慢来

发布时间：2026-10-13 | 5人浏览过

原创

本文详细解析C语言中基于链表实现的动态栈，包括数据结构定义、初始化、入栈、出栈、遍历及清空等核心功能的代码实现与原理说明。

栈的基本概念与结构

栈（Stack）是一种特殊的线性表，其插入和删除操作仅能在表的一端进行，该端称为栈顶（Top），另一端称为栈底（Bottom）。栈遵循“后进先出”（LIFO, Last In First Out）的原则，即最后放入的数据最先被取出。

1. 物理表现

以箱子装衣物为例，最后放上去的衣服总是最先被拿走，这便是栈的现实映射。在程序设计中，局部变量等数据常存放在栈区，体现了这一特性。

2. 存储方式

栈主要有两种实现方式：

静态栈：使用数组实现，大小固定。
动态栈：使用链表实现，大小随节点增加而动态扩展。本文将重点讲解此方式。

3. 空栈与有元素栈的结构

在链式栈中，通常设置一个不存放有效数据的头结点，或让栈顶/栈底指针直接指向第一个有效节点。以下为标准链式栈的两种状态示意图：

图示说明：空栈时，栈顶指针（pTop）与栈底指针（pBottom）均指向同一个无用的头结点，此时 pTop == pBottom 即为栈空条件。

图示说明：存有结点的栈结构中，栈顶指针 pTop 始终指向当前栈顶的有效结点，而栈底指针 pBottom 指向头结点。新节点插入时，改变的是 pTop 的指向。

数据结构定义与函数声明

为了实现动态栈，我们需要定义两个结构体：NODE 用于表示链表中的每一个节点，STACK 用于封装栈的整体属性（如头尾指针）。

以下是完整的C语言源码实现，包含详细的中文注释。代码涵盖了初始化、入栈、出栈、遍历、判空及清空等操作。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

// ==================== 数据结构定义 ====================

// 定义节点结构体
typedef struct Node {
    int data;             // 数据域
    struct Node *pNext;   // 指针域，指向下一个节点
} NODE, *PNODE;           // PNODE为struct Node*的别名

// 定义栈结构体
typedef struct Stack {
    PNODE pTop;   // 栈顶指针
    PNODE pBottom; // 栈底指针
} STACK, *PSTACK; // PSTACK为struct Stack*的别名

// ==================== 函数声明 ====================
void initStack(PSTACK pS);      // 初始化栈
bool isEmpty(PSTACK pS);        // 判断栈是否为空
void pushStack(PSTACK pS, int val); // 入栈
bool popStack(PSTACK pS, int *val); // 出栈
void traverseStack(PSTACK pS);  // 遍历栈
void clearStack(PSTACK pS);     // 清空栈

// ==================== 主函数测试 ====================
int main(void) {
    STACK s;
    int val;

    // 1. 初始化栈
    initStack(&s);

    // 2. 入栈操作：10 -> 20 -> 30 -> 50
    // 此时栈顶为50，栈底方向依次为30, 20, 10
    pushStack(&s, 10);
    pushStack(&s, 20);
    pushStack(&s, 30);
    pushStack(&s, 50);

    // 3. 遍历栈
    printf("栈内元素如下:\n");
    traverseStack(&s);

    // 4. 出栈操作
    if(popStack(&s, &val)) {
        printf("出栈成功，出栈元素值为：%d\n", val);
    } else {
        printf("出栈失败！栈可能为空。\n");
    }

    // 5. 再次遍历验证
    printf("出栈后剩余元素:\n");
    traverseStack(&s);

    // 6. 清空栈并验证
    clearStack(&s);
    printf("清空后栈内元素:\n");
    traverseStack(&s);

    return 0;
}

// ==================== 函数实现 ====================

/**
 * @brief 初始化栈
 * 创建一个头结点，使pTop和pBottom都指向它，构成空栈。
 */
void initStack(PSTACK pS) {
    pS->pTop = (PNODE)malloc(sizeof(NODE));
    if(NULL != pS->pTop) {
        pS->pBottom = pS->pTop;
        pS->pTop->pNext = NULL;
    } else {
        printf("内存分配失败!\n");
        exit(-1);
    }
}

/**
 * @brief 判断栈是否为空
 * @return true 为空, false 不为空
 */
bool isEmpty(PSTACK pS) {
    if(pS->pTop == pS->pBottom)
        return true;
    else
        return false;
}

/**
 * @brief 入栈操作
 * 将val存入新节点，并将新节点插入到栈顶。
 */
void pushStack(PSTACK pS, int val) {
    // 1. 创建新节点
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if(NULL == pNew) { // 建议增加内存检查
         printf("内存不足\n");
         return;
    }
    pNew->data = val;
    
    // 2. 新节点的next指向原栈顶
    pNew->pNext = pS->pTop;
    
    // 3. 栈顶指针指向新节点
    pS->pTop = pNew;
}

/**
 * @brief 出栈操作
 * 弹出栈顶元素，并通过pVal返回其值。
 * @return true 成功, false 栈空失败
 */
bool popStack(PSTACK pS, int *pVal) {
    // 1. 检查栈是否为空
    if(isEmpty(pS)) {
        return false;
    }
    
    // 2. 保存栈顶节点地址和数据
    PNODE rNode = pS->pTop;
    *pVal = rNode->data;
    
    // 3. 栈顶指针下移
    pS->pTop = rNode->pNext;
    
    // 4. 释放原栈顶节点内存
    free(rNode);
    rNode = NULL;
    
    return true;
}

/**
 * @brief 遍历栈
 * 从栈顶向栈底打印所有元素。
 */
void traverseStack(PSTACK pS) {
    PNODE pCurrent = pS->pTop;
    
    // 只要当前节点不是栈底节点，就继续遍历
    while(pCurrent != pS->pBottom) {
        printf("%d ", pCurrent->data);
        pCurrent = pCurrent->pNext;
    }
    printf("\n");
}

/**
 * @brief 清空栈
 * 释放除头结点外的所有节点内存，使栈回到初始状态。
 */
void clearStack(PSTACK pS) {
    if(isEmpty(pS)) {
        return; // 栈已空，无需操作
    }
    
    PNODE p = pS->pTop;
    PNODE q = NULL;
    
    while(p != pS->pBottom) {
        q = p->pNext;   // 记录下一个节点
        free(p);         // 释放当前节点
        p = q;           // 移动到下一个节点
    }
    
    // 重置栈顶指针指向头结点
    pS->pTop = pS->pBottom;
}