手撕数据结构 —— 栈（C语言讲解）
目录
1.认识栈
什么是栈
栈的示意图
2.如何实现栈
3.栈的实现
Stack.h中接口总览
具体实现
结构的定义
初始化栈
销毁栈
入栈
出栈
取栈顶元素
获取有效元素的个数
判断栈是否为空
4.完整代码附录
Stack.h
Stack.c
1.认识栈
什么是栈
栈是一种特殊的线性表，只允许在固定的一端进行数据的插入和删除操作；
- 进行数据的插入和删除的一端叫做栈顶，另一端叫做栈底。
- 栈中的数据必须严格遵守后进先出的原则，这也是栈这种数据结构最重要的特点。
栈的示意图
两个专业术语：
- 入栈：栈的插入数据元素的操作叫做入栈。
- 出栈：栈的删除数据元素的操作叫做出栈。
入栈和出栈都是在栈顶进行的。
2.如何实现栈
要想实现栈，必须满足以下两个条件：
- a、控制在一端进行数据的插入和删除
- b、满足后进先出的原则。
基于上述条件，我们可以使用数组或者链表来实现栈，那么使用哪种数据结构来实现栈更好呢？
我们可以对比一下：
| 数组（顺序表） | 链表（单链表） | |
| 头插效率 | O(N) | O(1) |
| 头删效率 | O(N) | O(1) |
| 尾插效率 | O(1) | O(N) |
| 尾删效率 | O(1) | O(N) |
可以看出，使用数组（顺序表）来实现栈的话，需要将尾部作为栈顶，插入数据和删除数据的时间复杂度都是O(1)。使用链表（单链表）来实现栈的话，需要将头部作为栈顶，插入数据和删除数据的时间复杂度都是O(1)。
但是相对而言，使用数组实现栈更优，因为数组没有太多的指针操作，删除数据的时候只需要让size-- 即可（size是数组中有效元素的个数），插入数据的时候直接赋值即可。
我们实现栈的时候，采用数组的形式实现数组栈。
3.栈的实现
实现栈的时候，我们主要实现Stack.h 和 Stack.c这两个文件，Stack.h用来存放声明，Stack.c用来存放定义。
Stack.h中接口总览
具体实现
结构的定义
因为静态的栈不实用，我们实现的数组栈采用动态增长的形式。
- a指向动态开辟的内存空间的起始地址。
- top指向栈顶元素的下一个位置。
- capacity表示栈的容量，当容量不够的时候，需要动态扩容。
初始化栈
初始化栈的之后，将a置为空，capacity和top都为0。
- top初始化为0表示top指向栈顶元素的下一个位置。
- top如果初始化为-1表示top指向栈顶元素。
- 两种方式实现都可以，我们采用第一种，这样的好处是top的值直接就可以表示栈中数据元素的个数。
注意：指向物理空间的指针ps不能为空，后面涉及该指针变量的地方都一样。
销毁栈
销毁栈的时候，只需要将动态申请的空间释放，并将指向这块空间的指针置空；然后将top和capacity都置为0即可。
入栈
实现入栈需要注意以下几个点：
- 栈空间不能为空，使用断言assert()暴力判断。
- 注意空间是否足够，空间不够时需要扩容。
- 元素入栈之后，top记得++。
出栈
出栈时需要注意以下几点：
- 指向物理空间的指针不能为空。
- 栈中元素个数 >0 时元素才能出栈。
- 元素出栈之后记得将top-- 。
取栈顶元素
我们定义结构的时候，将top定义为栈顶元素的下一个位置，top-1就表示栈顶元素的下标，直接返回栈顶元素即可。
获取有效元素的个数
top也能表示栈中有效元素的个数，直接返回top即可。
判断栈是否为空
top表示栈中有效数据的个数，当top == 0时，栈为空；当top != 0时，栈不为空。
4.完整代码附录
Stack.h
#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;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->a = NULL;ps->capacity = 0;ps->top = 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity) // 当 top==capacity时就需要扩容了 {// 初始空间为4，扩容按照两倍扩 int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;// 当a为空的时候，realloc的功能类似于malloc STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL) // 判断扩容是否成功 {perror("realloc fail");exit(-1);}ps->a = tmp; // 将开辟的空间赋值给变量a ps->capacity = newCapacity; // 更新容量 }ps->a[ps->top] = x; // 元素入栈 ps->top++; // top++指向栈顶元素的下一个位置
}void STPop(ST* ps)
{assert(ps); // 指针不能为空 assert(ps->top > 0); // 栈中元素个数 >0 元素才能出栈 --ps->top; // 元素出栈之后记得将top--
}STDataType STTop(ST* ps)
{assert(ps); assert(ps->top > 0); // 栈中有元素 return ps->a[ps->top - 1]; // 返回栈顶元素
}int STSize(ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}