当前位置： 首页 > ds >正文

数据结构（C语言篇）：（八）栈

ds 2025/9/1 7:09:31

目录

前言

一、概念与结构

二、栈的实现

2.1  头文件的准备

2.2  函数的实现

2.2.1  STInit( )函数（初始化）

2.2.2  STDestroy( )函数（销毁）

2.2.3  STPush( )函数（入栈）

2.2.4  STPop( )函数（出栈）

2.2.5  STTop( )函数（取栈顶元素）

2.2.6  STSize( )函数（获取栈中元素个数）

总结

前言

        栈作为一种基础且强大的线性数据结构，在计算机科学领域扮演着至关重要的角色。其"后进先出"（LIFO）的核心特性，使其成为处理函数调用、表达式求值、括号匹配等场景的理想选择。从程序执行时系统栈的管理，到日常开发中撤销操作、浏览历史等功能的实现，栈的应用无处不在。本文将深入探讨栈的工作原理、实现方式以及典型应用场景，帮助读者全面理解这一数据结构的精髓及其在实际工程中的价值。下面就让我们正式开始吧！

一、概念与结构

        栈：是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素等操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

        压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

        出栈：栈的删除操作叫做出栈。出数据也在栈顶。

        压栈和出栈的示意图如下：

        栈的底层结构选型：

        栈的实现我们一般可以使用数组或者链表来实现，相对而言数组的结构更优一些。因为数组在尾上插入数据的代价是比较小的。

        如果使用数组来实现：

        此时入栈和出栈的时间复杂度都是O(1)。

        如果使用链表来实现：

        此时出栈和入栈的时间复杂度也同样都是O(1)。

二、栈的实现

2.1  头文件的准备

        我们将栈的结构和一系列栈相关的函数在头文件Stack.h中声明如下：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>//定义栈的结构
typedef int STDataType;
typedef struct Stack {STDataType* arr;int top; //指向栈顶的位置---刚好就是栈中有效数据个数int capacity;//栈的空间大小
}ST;//初始化
void STInit(ST* ps);
//销毁
void STDesTroy(ST* ps);//入栈——栈顶
void STPush(ST* ps, STDataType x);
//出栈———栈顶
void STPop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);//栈是否为空
bool STEmpty(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);

2.2  函数的实现

2.2.1  STInit( )函数（初始化）

        函数的实现逻辑如下：

        1.  初始化数组指针：先将栈的数组指针arr置为NULL，此时表示栈没有分配任何内存空间。

ps->arr = NULL;

        2.  初始化栈顶指针和容量：

  • ps->top = 0：将栈顶指针设置为0，表示空栈

  • ps->capacity = 0：将栈的容量设置为0，表示当前没有分配空间

ps->top = ps->capacity = 0;

        完整代码如下：

//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;}

2.2.2  STDestroy( )函数（销毁）

        函数实现逻辑如下：

        1.  释放动态数组内存：

  • 检查 ps->arr 是否为 NULL（是否分配了内存）

  • 如果分配了内存，使用 free() 释放数组内存

  • 避免对 NULL 指针调用 free()

if(ps->arr)free(ps->arr);

        2.  重置指针和状态：

  • ps->arr = NULL：将数组指针设置为 NULL，避免野指针

  • ps->top = 0：将栈顶指针重置为0，表示空栈

  • ps->capacity = 0：将容量重置为0，表示没有分配空间

ps->arr = NULL;
ps->top = ps->capacity = 0;

        完整代码如下：

//销毁
void STDesTroy(ST* ps)
{if(ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}

        使用示例如下：

ST stack;
STInit(&stack);      // 初始化栈// 使用栈进行各种操作
STPush(&stack, 10);
STPush(&stack, 20);
// ...STDesTroy(&stack);   // 销毁栈，释放资源
// 现在stack可以被重新初始化或丢弃

2.2.3  STPush( )函数（入栈）

        首先画图分析：

        函数实现逻辑如下：

        1.  参数验证：确保栈指针 ps 不为 NULL。

assert(ps);

        2.  检查空间是否足够：如果栈顶指针等于容量，说明栈已满，需要扩容。

if (ps->top == ps->capacity)

        3.  动态扩容机制：首次分配时，如果容量为0（初始状态），先分配四个元素的空间；后续扩容时，如果已有容量，就将容量扩大为原来的2倍。（使用 realloc 重新分配内存，可以保留原有数据）

int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));

        4.  错误处理：检查内存分配是否成功，如果失败就输出错误信息，并退出程序。

if (tmp == NULL)
{perror("realloc fail！");exit(1);
}

        5.  更新指针和容量：首先更新数组指针指向新分配的内存，然后更新容量为新分配的大小。

ps->arr = tmp;
ps->capacity = newCapacity;

        6.  压入元素：将元素 x 放入栈顶位置 ps->arr[ps->top]，然后栈顶指针 ps->top 自增1。

ps->arr[ps->top++] = x;

        完整代码如下所示：

//入栈——栈顶
void STPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps->top == ps->capacity){//增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail！");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}

        使用示例如下：

ST stack;
STInit(&stack);STPush(&stack, 10);  // 分配4个空间，压入10
STPush(&stack, 20);  // 压入20
STPush(&stack, 30);  // 压入30  
STPush(&stack, 40);  // 压入40，栈满
STPush(&stack, 50);  // 扩容到8个空间，压入50

2.2.4  STPop( )函数（出栈）

        要想实现出栈函数，我们需要先实现一个STEmpty （判空）函数，如下所示：

//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

       画图分析如下：

        STPop的实现逻辑如下：

        1.  前置条件检查：首先使用用 STEmpty 函数检查栈是否为空，如果栈为空，则断言失败，不能执行弹出操作。同时需要确保栈中至少有一个元素可弹出。

        2.  执行弹出操作：首先将栈顶指针 top 减1，这样原来的栈顶元素就不再属于栈的有效范围，但实际上并没有删除数据，只是改变了栈的边界。

ps->top--;

        完整代码如下所示：

//出栈———栈顶
void STPop(ST* ps)
{assert(!STEmpty(ps));ps->top--;
}

        使用示例如下：

ST stack;
STInit(&stack);STPush(&stack, 10);
STPush(&stack, 20);
STPush(&stack, 30);
// 栈: [10, 20, 30], top=3STPop(&stack);  // 弹出30
// 栈: [10, 20], top=2STPop(&stack);  // 弹出20  
// 栈: [10], top=1STPop(&stack);  // 弹出10
// 栈: 空, top=0

2.2.5  STTop( )函数（取栈顶元素）

        画图分析如下：

        函数的实现逻辑如下：

        1.  前置条件检查：首先使用 STEmpty 函数检查栈是否为空，如果栈为空，则断言失败，不能获取栈顶元素。需要确保栈中至少有一个元素。

assert(!STEmpty(ps));

        2.  返回栈顶元素：

  • ps->top 指向下一个空位置（栈顶的下一个位置）

  • ps->top - 1 就是当前栈顶元素的位置

  • 返回该位置的元素值

return ps->arr[ps->top - 1];

        完整代码如下：

//取栈顶元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}

        使用示例：

ST stack;
STInit(&stack);STPush(&stack, 10);
STPush(&stack, 20);
STPush(&stack, 30);
// 栈: [10, 20, 30], top=3STDataType topValue = STTop(&stack);  // 获取栈顶值30
printf("栈顶元素: %d\n", topValue);   // 输出: 栈顶元素: 30// 栈仍然保持: [10, 20, 30], top=3

2.2.6  STSize( )函数（获取栈中元素个数）

        函数实现逻辑如下：

        1.  参数验证：确保栈指针 ps 不为 NULL。

assert(ps);

        2.  返回元素数量：直接返回栈顶指针 top 的值。因为 top 既指向下一个空位置，又表示当前元素数量。

return ps->top;

        完整代码如下：

//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

        使用示例如下：

ST stack;
STInit(&stack);printf("初始栈大小: %d\n", STSize(&stack));  // 输出: 0STPush(&stack, 10);
STPush(&stack, 20);
STPush(&stack, 30);printf("当前栈大小: %d\n", STSize(&stack));  // 输出: 3STPop(&stack);
printf("弹出后栈大小: %d\n", STSize(&stack));  // 输出: 2

总结

        本期我为大家介绍了数据结构中，栈的结构和其相关函数的实现逻辑，下期我将继续为大家带来队列的相关内容，请大家多多关注和支持~~~

http://www.xdnf.cn/news/19548.html

相关文章：

  • vscode+EIDE+Clangd环境导入keil C51以及MDK工程
  • shell脚本第六阶段---三剑客之sed
  • C++日志系统：高效异步日志实现解析
  • LeetCode 36. 有效的数独 - 解题思路与实现详解
  • ans.1中的对象标识符OBJECT_IDENTIFIER----OID
  • 【机器学习基础】决策树算法原理及其在无人驾驶技术中的应用
  • Matplotlib：让数据在Python中跳舞的魔法画笔！[特殊字符]
  • 基于FPGA的正弦波和及滤波（已通过仿真和上板）
  • 如何确定虚拟机的IP
  • DVWA靶场通关笔记-SQL Injection (Impossible级别)
  • [ Android Audio 篇 ] 高通平台 Android AudioRecord 多通道录音
  • LangChain中Prompt处理机制的技术架构与核心思想分析
  • STL库——stack/queue（类函数学习）
  • 切片语法[::-1]及其可用的类型
  • 基于STM32设计的智能家居控制系统(华为云IOT)_275
  • 2023年IEEE IOTJ SCI1区TOP，动态环境下无人机目标覆盖任务路径规划，深度解析+性能实测
  • KingbaseES JDBC 驱动详解：连接、配置与最佳实践
  • 介绍Ansible和实施Ansible PlayBook
  • pinia状态管理工具
  • Redis核心原理与Java应用实践
  • 洞悉边界：软件测试中边界值分析的艺术与科学
  • OpenJDK 17 解释器分发表与安全点表机制解析
  • 零基础入门AutoSar中的ARXML文件
  • 【Flask】测试平台开发，产品管理功能UI重构-第九篇
  • Kubernetes 服务发现与健康检查详解
  • 搭建卷积神经网络
  • 软考 系统架构设计师系列知识点之杂项集萃（139）
  • C++11语言(三)
  • Nginx实现P2P视频通话
  • codecombat（Ubuntu环境详细docker部署教程）