目录
栈的概念以及示意图
栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底，栈中的数据元素遵守先进后出的原则
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
出栈：栈的删除操作叫做出栈，出数据也在栈顶
栈结构示意图：
链式栈和数组栈
链式栈：
使用单链表实现栈的话就要用头节点做栈顶，这样出栈和压栈的效率才能达到O(1)
否则用尾节点当作栈顶的话，那么出栈和压栈时还要先找到尾节点，效率就低到了O(N)
且使用双向带头循环链表的话就会多使用一个指针，且和栈的使用逻辑不匹配
数组栈：
数组也就是顺序表，顺序表这种结构更加符合栈的出栈、压栈等操作，因为将顺序表尾部当作栈顶，那么出栈和压栈操作也就是尾删和尾插，效率为O(1)
唯一的缺陷就是当空间不够时，需要扩容，每次以原容量的 2 倍进行扩容，那么到后面会越扩越慢，申请扩容的效率也并不是很低
而且顺序表的CPU高速缓存效率比链式栈更高，所以选择实现数组栈
数组栈的结构
// 数据类型
typedef int STDataType;
typedef struct Stack
{
STDataType* a; //指向栈底的指针
int top; //栈顶元素的下标
int capaicty; //容量
}ST;注意：top 是指向栈顶元素的位置，而不是栈顶元素的下一个位置
实现数组栈的准备工作
创建3个文件
test.c 文件：用来测试增删查改功能是否完善
Stack.h 文件：用来声明动态顺序表的结构以及声明增删查改函数
Stack.c 文件：用来实现动态顺序表的增删查改及功能函数
实现数组栈
初始化数组栈
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = -1;
pst->capaicty = 0;
}top 初始化为 -1 的原因是：top 指向的是栈顶元素，那么对于数组来说，top 也就是数组最后一个元素的下标
当没有数据时，top 为 -1，当栈中有一个数据时，先将 top 自增 1，再放入数据，那么 a[top] 就是栈顶元素，top 也就是栈顶元素的下标，所以要初始化为 -1
且如果这样设计的话，那么后续的函数都要根据 top 的初始化为标准，大家也可以设计成 top 指向栈顶元素的下一个位置，这两种设计都可以
入栈（尾插）
void STPush(ST* pst, STDataType x)
{
// 数据入栈前判断是否需要扩容
if (pst->capaicty == (pst->top + 1))
{
// 扩容
int newCapaicty = pst->capaicty == 0 ? 4 : pst->capaicty * 2;
ST* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newCapaicty);
// 判断是否扩容成功
if (tmp == NULL)
{
perror("realloc fail");
}
pst->a = tmp;
pst->capaicty = newCapaicty;
}
// 存放数据
pst->a[++pst->top] = x;
}栈这个结构只有入栈时才会存放数据，所以不需要将扩容的逻辑额外封装成函数
且因为 top 是指向栈顶元素，所以判断是否需要扩容时要加 1
最后存放数据时要先将 top 自增 1，再存放数据
测试代码：
出栈（尾删）
void STPop(ST* pst)
{
// 当栈内无数据时
if (pst->top == -1)
{
printf("无数据可出栈\n");
return;
}
pst->top--;
}测试代码：
访问栈顶数据
STDataType STTop(ST* pst)
{
assert(pst);
// 当栈内无数据时
if (pst->top == -1)
{
printf("无数据可访问\n");
return;
}
return pst->a[pst->top];
}测试代码：
判断栈是否为空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == -1;
}栈数据的总数
int STSize(ST* pst)
{
assert(pst);
return (pst->top + 1);
}访问栈的所有数据
printf("栈顶<-");
while (!STEmpty(&st))
{
// 访问当前栈顶元素
printf("%d<-", STTop(&st));
// 移除当前栈顶元素
STPop(&st);
}
printf("栈底\n");测试代码：
释放栈
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capaicty = 0;
pst->top = -1;
}Stack.h 的所有代码
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
// 数据类型
typedef int STDataType;
typedef struct Stack
{
STDataType* a; //指向栈底的指针
int top; //栈顶元素的下标
int capaicty; //容量
}ST;
// 初始化
void STInit(ST* pst);
// 打印
void STPrint(ST* pst);
// 入栈（尾插）
void STPush(ST* pst, STDataType x);
// 出栈（尾删）
void STPop(ST* pst);
// 访问栈顶元素
STDataType STTop(ST* pst);
// 判断栈是否为空
bool STEmpty(ST* pst);
// 栈数据的总数
int STSize(ST* pst);
// 释放栈
void STDestroy(ST* pst);Stack.c 的所有代码
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
// 初始化
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = -1;
pst->capaicty = 0;
}
// 打印
void STPrint(ST* pst)
{
assert(pst);
printf("栈底->");
for (int i = 0; i <= pst->top; i++)
{
printf("%d->", pst->a[i]);
}
printf("栈顶\n\n");
}
// 入栈（尾插）
void STPush(ST* pst, STDataType x)
{
// 数据入栈前判断是否需要扩容
if (pst->capaicty == (pst->top + 1))
{
// 扩容
int newCapaicty = pst->capaicty == 0 ? 4 : pst->capaicty * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newCapaicty);
// 判断是否扩容成功
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capaicty = newCapaicty;
}
// 存放数据
pst->a[++pst->top] = x;
}
// 出栈（尾删）
void STPop(ST* pst)
{
// 当栈内无数据时
if (pst->top == -1)
{
printf("无数据可出栈\n");
return;
}
pst->top--;
}
// 访问栈顶元素
STDataType STTop(ST* pst)
{
assert(pst);
// 当栈内无数据时
if (pst->top == -1)
{
printf("无数据可访问\n");
return -1;
}
return pst->a[pst->top];
}
// 判断栈是否为空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == -1;
}
// 栈数据的总数
int STSize(ST* pst)
{
assert(pst);
return (pst->top + 1);
}
// 释放栈
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capaicty = 0;
pst->top = -1;
}