😺前言
- 👻前面我们学习了链表，总算是跨过一个台阶了，本章带大家轻松一波，领悟一下栈的魅力。
- 🤡栈是一种较为简单的数据结构，它的主要性质，就是数据后进先出(
LIFO)，我们可以利用这一性质，在做某些算法题时，以此为切入点。因此，栈还是挺不错的。
栈初始化
- 栈的性质是后进先出(不能任意插入删除)，并且只能访问栈顶元素，因此，对数据的入栈和出栈是特别方便的。
根据栈的这样一个后进先出的性质，我们该如何选择它的底层结构呢？是顺序表的数组还是链表呢？由此我们分析一下。
如果是数组，很容易想到，完全符合对栈的性质的操作，如果是入栈，直接在数组最后一个位置插入即可，空间不够扩容就好，如果是出栈，直接将统计栈顶的变量减一即可，想要获取栈顶的数据，那不也很简单嘛。由此看来，数组还真是不错呢。
如果是链表，入栈只要将数据头插即可，出栈就是头删，获取栈顶数据就是头节点的数据，这样看来，链表也挺不错呢。那么到底是选数组还是链表呢？
我们来看一下数据对比：
可以看到，对于栈的性质，该表的前面五个特点都没有明显的优与劣(就扩容会有差别)，但是最后一个缓存利用率却能分出高下，很明显，实现一个栈，使用数组会更好。（对于什么是缓存利用率，这里就不讲解了，大家自行查找资料噢）
选取了实现栈的底层结构，接下来就是对栈的初始化操作了。
首先需要三个文件（与前面的单链表一样哈哈哈）stack.h，stack.c，test.c，stack.h用来存放一些所需头文件，函数声明以及栈的结构体。stack.c用来实现函数接口，test.c用来测试。
所需头文件：
#include <stdio.h> // assert断言 #include <assert.h> // 判空需用到 #include <stdbool.h> // 动态空间需用 #include <stdlib.h>
- 接下来就对控制栈的结构体进行创建：
typedef int STDataType; typedef struct stack { // 底层数组 STDataType* a; // 容量 int capacity; // 标识栈顶 int top; }stack;
- 接下来是函数声明：
// 初始化 void STInit(stack* pt); // 入栈 void STPush(stack* pt, STDataType x); // 出栈 void STPop(stack* pt); // 判空 bool STEmpty(stack* pt); // 取栈顶元素 STDataType STTop(stack* pt); // 栈的元素个数 int STSize(stack* pt); // 销毁栈 void STDestroy(stack* pt);
怎么样，是不是看了函数接口就很简单呢，只有这些接口噢。
栈的初始化：
- 对于栈的初始化，我们可以直接将
top和capacity置为0，指向存放数据的数组的指针置为NULL。如下：
void STInit(stack* pt) { // 这里断言一下pt是为了防止传递一个NULL指针，正确的应该传递一个结构体的地址 assert(pt); pt->a = NULL; pt->capacity = 0; pt->top = 0; }
关于top实际上还可以初始化为-1。但-1与0实际差别不大，只是获取栈顶元素，判空和数据入栈这些代码会有所不同。如果top初始化为-1，那么top就是栈顶元素，如果top初始化为0，top就是栈顶元素的下一个位置。所以我们在实现的时候，要注意这个top。
而本章采用的top为0，也就是top是栈顶元素的下一个位置。
top = 0 ，实际上也间接体现了此时栈的数据个数。
栈顶入栈
栈顶入栈就是在数组的最后一个位置添加一个数据即可，操作简单，不过这里要考虑一个扩容的问题。
如果此时空间容量不够(判断条件：top == capacity)，就需要扩容，这里使用realloc扩容，如果开始没有空间，该函数的功能就跟malloc一样。
插入只要在top位置插入即可，最后top要加加一下噢。
下面是相关函数接口的代码实现：
void STPush(stack* pt, STDataType x) { // 防止传递一个NULL assert(pt); // 检查容量看是否已满，满了就需要扩容 if (pt->top == pt->capacity) { int newcapacity = pt->capacity == 0 ? 4 : pt->capacity * 2; STDataType* tmp = realloc(pt->a, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } pt->a = tmp; pt->capacity = newcapacity; } // 在top位置放新的的数据，同时top要加一 pt->a[pt->top++] = x; }
栈顶出栈
- 栈顶出栈就是抹去数组最后一个数据，只要
top自减一即可。 - 注意，当栈为空的时候，就不能出栈了，如何判断是否为空？在下面呢，别急哈哈哈。
下面是相关函数接口的代码实现：
void STPop(stack* pt) { // 如果为空就不能删了。判空在后面写到。 assert(pt && !STEmpty(pt)); // top减一即可 pt->top--; }
栈体判空
- 栈体判空，只需要判断一下
top是否为0即可。如果是0，说明此时栈为空，返回true；如果不等于0，说明此时栈不为空，返回false。
下面是相关函数接口的代码实现：
bool STEmpty(stack* pt) { assert(pt); return pt->top == 0; }
栈的数据个数
- 前面说了，
top就相当于是数据的个数，所以这里直接返回top的值即可。
下面是相关函数接口的代码实现：
int STSize(stack* pt) { assert(pt); return pt->top; }
获取栈顶元素
- 由于
top是最后一个元素的下一个位置，因此获取栈顶元素时，它的位置为top - 1。
下面是相关函数接口的代码实现：
STDataType STTop(stack* pt) { assert(pt && !STEmpty(pt)); return pt->a[pt->top - 1]; }
栈的销毁
- 有空间的开辟，那就要有空间的释放，这里称为销毁。
- 销毁也很简单，只需要将指向栈空间的那个指针
free即可。 - 当然，最后可以将
top置为0，capacity也置为0。
下面是相关函数接口的代码实现：
void STDestroy(stack* pt) { assert(pt); free(pt->a); pt->capacity = 0; pt->top = 0; }
整体代码
stack.h
#include <stdio.h> #include <assert.h> #include <stdbool.h> #include <stdlib.h> typedef int STDataType; typedef struct stack { STDataType* a; int capacity; int top; }stack; // 初始化 void STInit(stack* pt); // 入栈 void STPush(stack* pt, STDataType x); // 出栈 void STPop(stack* pt); // 判空 bool STEmpty(stack* pt); // 取栈顶元素 STDataType STTop(stack* pt); // 栈的元素个数 int STSize(stack* pt); // 销毁栈 void STDestroy(stack* pt);
stack.c
#include "stack.h" void STInit(stack* pt) { assert(pt); pt->a = NULL; pt->capacity = 0; pt->top = 0; } void STPush(stack* pt, STDataType x) { assert(pt); if (pt->top == pt->capacity) { int newcapacity = pt->capacity == 0 ? 4 : pt->capacity * 2; STDataType* tmp = realloc(pt->a, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } pt->a = tmp; pt->capacity = newcapacity; } pt->a[pt->top++] = x; } void STPop(stack* pt) { assert(pt && !STEmpty(pt)); pt->top--; } bool STEmpty(stack* pt) { assert(pt); return pt->top == 0; } STDataType STTop(stack* pt) { assert(pt && !STEmpty(pt)); return pt->a[pt->top - 1]; } int STSize(stack* pt) { assert(pt); return pt->top; } void STDestroy(stack* pt) { assert(pt); free(pt->a); pt->capacity = 0; pt->top = 0; }
test.c
#include "stack.h" void test() { stack st; STInit(&st); STPush(&st, 1); STPush(&st, 2); STPush(&st, 3); STPush(&st, 4); STPush(&st, 5); while (!STEmpty(&st)) { printf("%d ", STTop(&st)); STPop(&st); } printf("\n"); STPush(&st, 5); STPush(&st, 55); STPush(&st, 555); STPush(&st, 5555); STPush(&st, 55555); STPush(&st, 555555); printf("%d\n", STTop(&st)); while (!STEmpty(&st)) { printf("%d ", STTop(&st)); STPop(&st); } printf("\n"); STDestroy(&st); } int main() { test(); return 0; }
😼写在最后
💝到这里，一个简简单单的栈就完成了，是不是很简单呢？不过也别得意哈，后面难的数据结构还没来呢，栈就是让你处于一个平静期，为后来的难度做准备呢哈哈哈哈哈。
❤️🔥后续将会持续输出有关数据结构的文章，你们的支持就是我写作的最大动力！
感谢阅读本小白的博客，错误的地方请严厉指出噢~
