05.【数据结构-C语言】栈（先进后出，栈的实现：进栈、出栈、获取栈顶元素，栈实现代码，括号匹配问题）
目录
1. 栈的概念及结构
2. 栈的实现（数组）
2.1 栈的实现方式（数组 or 链表）
2.2 栈结构体声明
2.3 初始化&销毁（top初始化为0）
2.4 进栈（压栈）（尾插）
2.5 出栈（尾删）
2.6 获取栈顶元素
2.7 判空
2.8 获取栈元素个数
3. 栈实现完整版代码
4. 栈相关题目（括号匹配问题）
1. 栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
2. 栈的实现（数组）
2.1 栈的实现方式（数组 or 链表）
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。本文使用数组实现栈。
2.2 栈结构体声明
和顺序表类似，多了一个top来进行栈顶相关操作。
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int STDataType;
typedef struct Stack
{STDataType* a; // 栈数组指针int top; // top为实际栈顶下标+1int capacity; // 栈空间大小
}ST;2.3 初始化&销毁（top初始化为0）
栈顶定义有两种方式：
top初始化为-1，即top指的是栈顶元素的下标。
top初始化为0，即top指的是栈顶元素的下标+1，即栈的数据个数。（此方法比较好）
// 栈初始化和销毁
void STInit(ST* pst)
{assert(pst); // assert防止传入空指针assert(NULL)pst->a = NULL;pst->top = 0; // top指向数据的下一个元素pst->capacity = 0;
}void STDestory(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}2.4 进栈（压栈）（尾插）
// 入栈
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->capacity == pst->top) // 当栈顶空见满时，扩容{int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc");exit(1);}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top++] = x; // top++，注意此时top为实际栈顶下标+1
}2.5 出栈（尾删）
出栈只需要判断是否栈中还有数据，然后对top--即可。
// 出栈
void STPop(ST* pst)
{assert(pst && pst->a && pst->top >0);pst->top--;
}2.6 获取栈顶元素
获取下标为top-1的元素。top为实际栈顶下标+1。
// 获取栈顶元素
STDataType STTop(ST* pst)
{assert(pst && pst->a && pst->top > 0);return pst->a[pst->top-1];
}
2.7 判空
// 判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}2.8 获取栈元素个数
数组末尾元素下标+1=top，即为栈元素个数。
// 获取栈元素个数
int STSize(ST* pst)
{return pst->top;
}3. 栈实现完整版代码
【免费】栈-C语言实现完整版代码资源-CSDN下载
4. 栈相关题目（括号匹配问题）
括号匹配OJ