=========================================================================
相关代码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 <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> //动态顺序表： //定义栈的栈顶数据元素： 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 ? 4 : ps->capacity * 2; //因为栈容量capacity初始化为0， //所以可以使用三目操作符进行增容： //ps->capacity == 0 ? 4 : ps->capacity * 2 //如果为0则直接增容到4，不为0则增容2倍 //开辟动态空间： STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*newCapacity); //这里直接使用realloc进行动态空间开辟 //如果realloc函数接收头指针（第一个参数）为空， //那么它的作用相当于malloc函数 //对开辟空间进行检查： if (tmp == NULL) //返回空指针，开辟失败： { //打印错误信息： perror("realloc fail"); //终止程序： exit(-1); } //开辟成功后， //栈内元素控制指针指向开辟空间： ps->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; }
文章出处登录后可见！
