数据结构————栈
一.栈
1. 栈的的概念
栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素的操作。进行元素插入和删除的一段是栈顶，另一端是栈底。栈中的元素遵从后进先出LIFO（Last In First Out）的原则。
- 压栈：栈的插入操作叫做进栈/入栈，入数据在栈顶。
- 出栈：栈的删除操作叫做出栈/出数据在栈顶。
2.栈的结构
3.栈的状态
3.1. 空栈
3.1.1.概念：
指栈中没有任何元素，栈顶指针（或列表长度）指向 “空” 的位置
3.2.满栈
3.2.1.概念：
满栈仅针对顺序栈（数组 / 列表实现的栈），指栈中元素数量达到了预设的最大容量，无法再执行入栈操作
3.3.递归栈
3.3.1.概念：
递归栈不是一种物理栈，而是程序执行递归函数时，操作系统 / 解释器为其维护的函数调用栈。每一次递归调用都会将函数的上下文（参数、局部变量、返回地址）压入栈；每一次递归返回（执行完当前函数），都会将该上下文弹出栈。
3.4.递减栈
3.4.1.概念：
递减栈（也叫 “单调递减栈”）是一种算法技巧（而非基础数据结构），指栈内的元素始终保持严格递减（或非递增）的顺序。入栈时会主动弹出不符合递减规则的元素，确保栈的单调性。
二.栈的实现
顺序栈(用数组实现)
函数接口
#defineMAX_SIZE100// 定义栈的最大容量typedefintSTDataType;// 栈中元素的类型// 顺序栈结构体typedefstructStack{STDataType a[MAX_SIZE];// 数组用于存储栈元素inttop;// 栈顶指针}Stack;// 初始化栈voidSTInit(Stack*ps);// 判断栈是否为空intSTEmpty(Stack*ps);// 判断栈是否为满intSTFull(Stack*ps);// 入栈操作voidSTPush(Stack*ps,STDataType x);// 出栈操作voidSTPop(Stack*ps);// 查看栈顶元素STDataTypeSTTop(Stack*ps);// 获取栈的大小intSTSize(Stack*ps);初始化
// 初始化栈voidSTInit(Stack*ps){assert(ps);ps->top=-1;// 初始化栈顶指针为-1，表示栈为空}判断是否为空
// 判断栈是否为空intSTEmpty(Stack*ps){assert(ps);returnps->top==-1;// 如果栈顶指针为-1，表示栈为空}判断是否满了
// 判断栈是否为满intSTFull(Stack*ps){assert(ps);returnps->top==MAX_SIZE-1;// 如果栈顶指针等于最大容量减1，表示栈已满}入栈
// 入栈操作voidSTPush(Stack*ps,STDataType x){assert(ps);if(STFull(ps)){printf("栈已满，无法入栈！\n");return;}ps->a[++(ps->top)]=x;// 将元素放入栈顶，并更新栈顶指针}出栈
// 出栈操作voidSTPop(Stack*ps){assert(ps);if(STEmpty(ps)){printf("栈为空，无法出栈！\n");return;}ps->top--;// 更新栈顶指针，删除栈顶元素}查看栈顶元素
// 查看栈顶元素STDataTypeSTTop(Stack*ps){assert(ps);if(STEmpty(ps)){printf("栈为空，无法查看栈顶元素！\n");return-1;// 如果栈为空，返回一个非法值}returnps->a[ps->top];// 返回栈顶元素}有效元素个数
// 获取栈的大小intSTSize(Stack*ps){assert(ps);returnps->top+1;// 栈的大小等于栈顶指针+1}链式栈(用链表实现)
函数接口
typedefintSTDataType;//动态typedefstructStack{int*a;inttop;intcapacity;}ST;voidSTInit(ST*ps);voidSTDestory(ST*ps);voidSTPush(ST*ps,STDataType x);voidSTPop(ST*ps);intSTSize(ST*ps);boolSTEmpty(ST*ps);STDataTypeSTTop(ST*ps);初始化
#include"STack.h"voidSTInit(ST*ps){assert(ps);ps->a=(STDataType*)malloc(sizeof(STDataType)*4);if(ps->a==NULL){perror("malloc failed");return;}ps->capacity=4;ps->top=0;//top栈顶元素的下一个位置//ps->top = -1;//top是栈顶元素位置}销毁
voidSTDestory(ST*ps){assert(ps);free(ps);ps->a=NULL;ps->capacity=0;ps->top=0;}进栈
voidSTPush(ST*ps,STDataType x){assert(ps);if(ps->top==ps->capacity){STDataType*tmp=(STDataType*)realloc(ps->a,sizeof(STDataType)*ps->capacity*2);if(tmp==NULL){perror("realloc failed");return;}ps->a=tmp;ps->capacity*=2;}ps->a[ps->top]=x;ps->top++;}出栈
voidSTPop(ST*ps){assert(ps);assert(!STEmpty(ps));ps->top--;}有效元素个数
intSTSize(ST*ps){assert(ps);returnps->top;}判断是否为空
boolSTEmpty(ST*ps){assert(ps);returnps->top==0;}获取栈顶元素
STDataTypeSTTop(ST*ps){assert(ps);assert(!STEmpty(ps));returnps->a[ps->top-1];}三.栈的应用
1.递归
2.括号的匹配
这是leetcode上的一道例题，有兴趣大家可以去试一试
有效括号
希望大家能支持关注一下新人博主，谢谢。