1. 栈
1.1 概念与结构
栈：⼀种特殊的线性表，其只允许在固定的⼀端进行插入和删除元素操作。进行数据插入和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出 LIFO（Last In First Out）的原则。
压栈：栈的插⼊操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
但栈要怎么实现呢?使用数组还是用链表？
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优⼀些。
因为数组在尾上插入数据的代价比较小。
下面用一幅图来给大家解释一下用链表还是数组。
1.2链表实现栈的优缺点：
优点:
1、任意位置插入删除O(1)
2、按需申请释放空间
缺点:
1、不支持下标随机访问
2、CPU高速缓存命中率会更低
1.2.1链表实现栈的缺点：
1.额外内存开销：链表实现的栈需要为每个节点分配内存空间来存储数据和指针。相比于数组实现的栈，链表实现需要额外的内存开销来维护节点之间的指针关系，可能导致内存碎片化。
2.动态内存分配：链表实现的栈需要通过动态内存分配来创建和释放节点。这涉及到频繁的内存分配和释放操作，可能导致内存管理的复杂性和性能开销。在某些情况下，可能会出现内存分配失败或内存泄漏的问题。
3.指针操作开销：链表实现的栈需要通过指针进行节点之间的连接操作。这包括插入和删除节点时的指针修改，可能涉及到多个指针的更新。相比于数组实现的栈，链表实现的栈需要更多的指针操作，可能会带来一定的性能开销。
3.随机访问的限制：链表是一种顺序访问的数据结构，无法像数组一样通过索引进行随机访问。如果需要在栈中进行随机访问元素，链表实现的栈可能不太适合，而数组实现的栈更具优势。
1.3顺序表的优缺点：
优点:
1、尾插尾删效率高。
2、下标的随机访问。
3、CPU高速缓存命中率会更高
缺点:
1、前面部分插入删除数据，效率是O(N)，需要挪动数据。
2、空间不够，需要扩容。a、扩容是需要付出代价的b、一般还会伴随空间浪费。
1.3.1顺序表实现栈的优点：
1.内存连续性：顺序表在内存中是连续存储的，相比于链表的动态内存分配，顺序表的元素在物理上更加紧凑。这样可以减少内存碎片化，提高内存的利用效率。
2.随机访问：顺序表可以通过索引直接访问栈中的元素，具有随机访问的能力。这意味着可以快速访问栈中任意位置的元素，而不需要遍历整个链表。
3.操作简单高效：顺序表的插入和删除操作只涉及元素的移动，不需要额外的指针操作和动态内存分配。这使得操作相对简单高效，并且在某些情况下比链表实现更快。
4.空间效率：相比于链表实现，顺序表不需要额外的指针来维护节点之间的连接关系，因此可以节省一定的空间开销。只需要存储元素本身和栈顶指针即可。
综上所述：选择顺序表较好一点。
栈的实现：
头文件：Stack.h
typedef int STDataType;
typedef struct Stack {
STDataType* a;
int top;
int capacity;
}ST;//定义栈的结构
// 初始化栈
void STInit(ST* ps);
// 销毁栈 void STDestroy(ST* ps);
// ⼊栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//取栈顶元素 STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//栈是否为空
bool STEmpty(ST* ps);
实现栈的文件：Stack.c
#include"Stack.h"
void STInit(ST* ps)
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}void STDestroy(ST* ps)
{
assert(ps);
if (ps->arr)
{
free(ps->arr);
}
ps->arr = NULL;
ps->capacity = ps->top = 0;
}void STackPush(ST* ps, STDateType x)
{
assert(ps);
if (ps->capacity == ps->top)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDateType* tem = (STDateType*)realloc(ps->arr, newCapacity * sizeof(STDateType));
if (tem == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tem;
ps->capacity = newCapacity;
}
ps->arr[ps->top++] = x;
}bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}void STackPop(ST* ps)
{assert(ps);
assert(!StackEmpty(ps));
--ps->top;}
STDateType STacktop(ST* ps) {
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top - 1];
}int STSize(ST* ps) {
assert(ps);
return ps->top;
}
测试文件：text.c
#include"Stack.h"
void STText()
{
//ST st;
//STInit(&st);
//STackPush(&st, 1);
//STackPush(&st, 2);
//STackPush(&st, 3);
//STackPush(&st, 4);
//STackPush(&st, 5);
//printf("size==%d\n", STSize(&st));
STackPop(&st);
//while (!StackEmpty(&st))
//{
// STDateType date = STacktop(&st);
// printf("%d ", date);
// STackPop(&st);
//}
//printf("\n");
//printf("size==%d\n", STSize(&st));
//STDestroy(&st);
}
int main()
{
STText();return 0;
}
有兴趣的小伙伴可以测试一下，代码是完全没有错误的。
