网站导航
> 技术文档 > 数据结构之栈

数据结构之栈

网友: 技术文档 2025-07-30 11:37:17

欢迎拜访：雾里看山-CSDN博客
本篇主题：数据结构之栈
发布时间：2025.7.5
隶属专栏：数据结构

在这里插入图片描述

目录

  • 栈的概念与结构
    • 基本概念
    • 核心特性
  • 栈的实现
    • 顺序栈
      • 栈结构的定义：
      • 基本操作的实现
    • 链栈
      • 栈结构的定义
      • 基本操作的实现
  • 两种实现的比较
  • 总结与选择建议
    • 栈的核心价值
    • 实现选择建议
    • 应用领域总结

栈的概念与结构

基本概念

栈是一种后进先出（LIFO: Last In First Out）的线性数据结构，只允许在固定的一端进行插入和删除操作。

  • 压栈/入栈 (Push)：将元素放入栈顶
  • 出栈 (Pop)：从栈顶移除元素
  • 栈顶 (Top)：唯一允许操作的元素位置
  • 栈底 (Bottom)：不允许操作的一端

核心特性

  • LIFO原则：最后入栈的元素最先出栈
  • 受限访问：只能访问栈顶元素
  • 动态大小：大小随操作变化（除固定大小栈）
  • 操作高效：所有操作时间复杂度为O(1)

数据结构之栈

栈的实现

栈有两种主要实现方式：顺序栈（基于数组）和链栈（基于链表）。

顺序栈

栈结构的定义：

typedef int STDataType;typedef struct Stack{STDataType* a;// 数组的指针int top; // 存储数据的数量int capacity; // 栈的总容量}ST;

基本操作的实现

// 栈的初始化void STInit(ST* ps){assert(ps);STDataType* tmp= (STDataType*)malloc(sizeof(STDataType) * 4);if (tmp == NULL){perror(\"Init malloc fail\");exit(-1);}ps->a = tmp;ps->capacity = 4;ps->top = 0;}// 栈的销毁void STDestroy(ST* ps){assert(ps);free(ps->a);ps->a == NULL;ps->top = ps->capacity = 0;}// 入栈void STPush(ST* ps, STDataType x){assert(ps);if (ps->capacity == ps->top){STDataType* tmp = realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));if (tmp == NULL){perror(\"Push realloc fail\");exit(-2);}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;}// 出栈void STPop(ST* ps){assert(ps);assert(ps->top > 0);ps->top--;}// 取栈顶元素STDataType STTop(ST* ps){assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];}// 栈存储的数量int STSize(ST* ps){assert(ps);return ps->top;}//栈是否为空bool STEmpty(ST* ps){assert(ps);return ps->top == 0;}

链栈

栈结构的定义

typedef int STDataType;typedef struct StackNode{STDataType data; // 存放数据struct StackNode* next;// 指向下一个节点}STNode;typedef struct Stack{STNode* top; // 栈顶元素int size; // 栈内元素的数量}Stack;

基本操作的实现

// 初始化栈void StackInit(Stack* ps){ps->top = NULL;ps->size = 0;}// 创建节点STNode* BuyNode(STDataType x){STNode* tmp = (STNode *)malloc(sizeof(STNode));if (tmp == NULL){perror(\"malloc node fail\\n\");exit(-1);}tmp->data = x;tmp->next = NULL;return tmp;}// 入栈void StackPush(Stack* ps, STDataType data){assert(ps);STNode* node = BuyNode(data);node->next = ps->top;ps->size++;ps->top = node;}// 出栈void StackPop(Stack* ps){assert(ps);assert(ps->size > 0);STNode* top = ps->top;ps->top = ps->top->next;ps->size--;free(top);}// 获取栈顶元素STDataType StackTop(Stack* ps){assert(ps);return ps->top->data;}// 获取栈中有效元素个数int StackSize(Stack* ps){assert(ps);return ps->size;}// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(Stack* ps){assert(ps);return ps->size == 0;}// 销毁栈void StackDestroy(Stack* ps){assert(ps);while (ps->top){STNode* tmp = ps->top;ps->top = ps->top->next;free(tmp);}ps->size = 0;}

两种实现的比较

特性 顺序栈（数组实现） 链栈（链表实现） 内存分配 半静态/固定大小 动态分配/无固定大小 空间效率 无额外指针开销 每个节点额外指针开销 时间效率 所有操作O(1) 所有操作O(1) 扩容能力 有限（需重新分配） 无限（除非内存耗尽） 缓存友好 高（连续内存） 低（非连续内存） 实现难度 简单 中等 适用场景 元素数量可预测/固定大小 元素数量变化大/内存受限

总结与选择建议

栈的核心价值

  • 简单高效：所有操作时间复杂度O(1)
  • 逻辑清晰：LIFO原则简化问题处理
  • 功能强大：适用于多种算法和系统功能
  • 内存友好：最小化临时存储需求

实现选择建议

场景 推荐实现 理由 元素数量固定/可预测 顺序栈（数组） 内存紧凑，无额外开销 元素数量变化大/不可预测 链栈（链表） 动态扩展，无容量限制 高频访问/内存敏感 顺序栈 缓存友好，访问速度快 需要多栈共享内存 顺序栈 可在同一数组实现多个栈 需要实现复杂功能 链栈 灵活性高，无扩容问题

应用领域总结

  • 系统级开发：函数调用栈、中断处理
  • 算法实现：DFS、回溯、表达式求值
  • 应用软件：撤销/重做、浏览历史
  • 编译器：语法分析、中间代码生成
  • 嵌入式系统：有限状态机、任务调度

⚠️ 写在最后：以上内容是我在学习以后得一些总结和概括，如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流！！！

网络标签：

相关问题