=========================================================================

相关代码gitee自取：

C语言学习日记: 加油努力 (gitee.com)

=========================================================================

接上期：

【数据结构初阶】四、线性表里的链表（带头+双向+循环 链表 — C语言实现）_高高的胖子的博客-CSDN博客

=========================================================================

1 . 栈（Stack）

栈的概念和结构：

栈的概念

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

压栈和出栈

  • 栈的插入操作叫做进栈/压栈/入栈 — Push
    入数据在栈顶
  • 栈的删除操作叫做出栈 — Pop
    出数据也在栈顶

栈的结构

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

2 . 栈的实现

使用 顺序表(数组) 或 链表(链式结构) 都可以实现栈，

使用链表的话，可以使用 尾插(头插)和 尾删(头删)实现 栈的“后进先出”，

（ 尾插 — 压栈；尾删 — 出栈 ）

使用顺序表同样可以使用 尾插 和 尾删 实现，

但顺序表的尾插和尾删操作效率较高，处理数据时的缓存利用率也较高，

所以下面用顺序表(数组)实现栈：

（详细解释在图片的注释中，代码分文件放下一标题处）

实现具体功能前的准备工作

  • 包含之后会用到的头函数
  • 创建栈数据类型—栈中存储数据的类型
  • 创建栈结构体(类型) — 类型中应有控制栈内元素指针、栈顶值、栈大小
图示

———————————————————————————————

STInit函数 –对栈类型进行初始化

  • assert断言栈类型指针不为空
  • 将栈内元素控制指针置为空，
    将栈容量（大小）置为0，
    将栈顶值定义为0
图示

———————————————————————————————

STDestroy函数 –销毁栈类型

  • assert断言栈类型指针不为空
  • 释放栈内元素控制指针并置空，
    栈容量置为0，
    栈顶值置为0
图示

———————————————————————————————

STPush函数 –进行压栈

  • assert断言栈类型指针不为空
  • 为栈开辟动态空间并进行检查
  • 开辟成功后，栈内元素控制指针指向开辟的空间，
    重新设置capacity栈容量
  • 将压栈的值（x）放入栈
  • 调整栈顶值“下标”top的位置
图示

———————————————————————————————

STPop函数 –进行出栈

  • assert断言栈类型指针不为空，
    assert断言栈不为空
  • 把栈顶向下移动一个单位即可实现“删除”（出栈）
图示

———————————————————————————————

STTop函数 –获取栈顶元素

  • assert断言栈类型指针不为空，
    assert断言栈不为空
  • 返回栈顶元素
图示

———————————————————————————————

STSize函数 –计算栈中元素个数

  • assert断言栈类型指针不为空
  • 返回top，即栈中元素个数
图示

———————————————————————————————

STEmpty函数 –判断栈是否为空

  • assert断言栈类型指针不为空
  • 判断top栈顶值是否为空，
    是则返回true，否则返回false
图示

———————————————————————————————

总体测试：

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

3 . 对应代码

Stack.h– 栈头文件

#pragma once//包含之后需要的头文件：#include #include #include #include //动态顺序表：//定义栈的栈顶数据元素：typedef int STDataType;//定义栈类型：typedef struct Stack{//为栈开辟动态空间时的头指针：//控制栈内元素的指针STDataType* a;//栈顶值(用于定义栈顶)：int top;//类似于数组下标//栈存放数据容量（栈的大小）：int capacity;}ST; //重命名为ST//静态顺序表：//define N 10//struct Stack//{//int a[N];//int top;//};//初始化栈函数 -- 对栈类型进行初始化//接收栈类型指针void STInit(ST* ps);//销毁栈函数 -- 销毁栈类型//接收栈类型指针void STDestroy(ST* ps);//因为只有压栈和出栈操作//只操作栈顶元素，所以没有//头插（尾插）头删（头删）等其他操作//压栈函数 -- 进行压栈//接收栈类型指针（ps）、进行压栈的值（x）void STPush(ST* ps, STDataType x);//出栈函数 -- 进行出栈//接收栈类型指针void STPop(ST* ps);//栈顶元素函数 -- 获取栈顶元素//接收栈类型指针STDataType STTop(ST* ps);//栈中元素函数 --计算栈中元素个数//接收栈类型指针int STSize(ST* ps);//判空函数 -- 判断栈是否为空//接收栈类型指针bool STEmpty(ST* ps);

———————————————————————————————

Stack.c — 栈函数实现文件

#define _CRT_SECURE_NO_WARNINGS 1//包含栈头文件：#include "Stack.h"//初始化栈函数 -- 对栈类型进行初始化//接收栈类型指针void STInit(ST* ps){//assert断言栈类型指针不为空：assert(ps != NULL);//将栈内元素控制指针置为空：ps->a = NULL;//将栈容量（大小）置为0：ps->capacity = 0;//将栈顶值定义为0：ps->top = 0;}//销毁栈函数 -- 销毁栈类型//接收栈类型指针void STDestroy(ST* ps){//assert断言栈类型指针不为空：assert(ps != NULL);//释放栈内元素控制指针：free(ps->a);//并将其置为空：ps->a = NULL;//栈容量置为0：ps->capacity = 0;//栈顶值置为0：ps->top = 0;}//压栈函数 -- 进行压栈//接收栈类型指针（ps）、进行压栈的值（x）void STPush(ST* ps, STDataType x){//assert断言栈类型指针不为空：assert(ps != NULL);//为栈开辟动态空间：if (ps->top == ps->capacity)//栈顶值 等于 栈大小//说明空间不够，需要扩容{//只有压栈时容量会增大可能需要扩容//只有这个函数会进行扩容操作，//所以没必要单独写一个扩容函数//进行扩容:int newCapacity = ps->capacity == 0 " />a = tmp;//重新设置capacity栈容量：ps->capacity = newCapacity;}//将压栈的值（x）放入栈：ps->a[ps->top] = x; //上面以a为头开辟连续的空间，//所以a可以看作一个数组名使用（？）//通过数组下标放入值//再调整栈顶值“下标”位置：ps->top++;}//出栈函数 -- 进行出栈//接收栈类型指针void STPop(ST* ps){//assert断言栈类型指针不为空：assert(ps != NULL);//assert断言栈顶top到了栈底就不能继续出栈了assert(ps->top > 0); //栈不为空//出栈只要栈顶top--//把栈顶向下移动一个单位即可实现”删除“（出栈）：--ps->top;}//栈顶元素函数 -- 获取栈顶元素//接收栈类型指针STDataType STTop(ST* ps){//assert断言栈类型指针不为空：assert(ps != NULL);//assert断言栈为空的话就不能找栈顶元素了assert(ps->top > 0);//返回栈顶元素：return ps->a[ps->top - 1];//top即栈中元素个数：//top从0开始，压栈后top++，先赋值再++//top永远在栈顶元素的下一个位置//所以要获得栈顶元素就要top-1到栈顶元素位置}//栈中元素函数 --计算栈中元素个数//接收栈类型指针int STSize(ST* ps){//assert断言栈类型指针不为空：assert(ps != NULL);//top即栈中元素个数：//top从0开始，压栈后top++，先赋值再++//top永远在栈顶元素的下一个位置return ps->top;}//判空函数 -- 判断栈是否为空//接收栈类型指针bool STEmpty(ST* ps){//assert断言栈类型指针不为空：assert(ps != NULL);//如果top为0//说明栈中没有元素return ps->top == 0; //top为0 -> 栈为空 -> 返回true//top不为0 -> 栈不为空 -> 返回false}

———————————————————————————————

Test.c — 栈测试文件

#define _CRT_SECURE_NO_WARNINGS 1//包含栈头文件：#include "Stack.h"//测试函数：void TestStack(){//创建一个栈类型：ST st;//对其进行初始化：STInit(&st);//使用压栈往栈中增加元素：STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);//元素大于4个再次进行扩容//打印当前栈中元素个数：printf("目前栈内元素个数为：%d\n", STSize(&st));//换行：printf("\n");//使用while循环：//打印栈顶元素再出栈，循环此操作：//证明栈的后进先出原则while (!STEmpty(&st))//链表不为空就继续操作：{//打印当前栈顶元素：printf("出栈前栈顶元素：%d\n", STTop(&st));//进行出栈：STPop(&st);}//换行：printf("\n");//打印当前栈中元素个数：printf("目前栈内元素个数为：%d", STSize(&st));//进行销毁：STDestroy(&st);}//主函数int main(){TestStack();return 0;}