前言
在前几期的学习中，我们认识了顺序表和链表这两种线性表，而在本期学习中，我们将会认识别的线性表。跟随我们的脚本，看看栈和队列有怎样的特点。
1. 栈
1.1 栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
- 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
- 出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.2 栈的结构
2. 栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
2.1 栈的初始化
我们将结构体的所有元素都初始化为0。这里与我们在顺序表中的初始化不同，在顺序表中我们在初始化时就开辟了空间，下面我们会介绍另一种方式。
void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->capacity = 0; pst->top = 0; }
2.2 入栈
在进栈时可能遇到容量为零，所以我们使用一个条件判断，来确定容量。因为top为0，所以它表示的是下一个元素的下标，要先赋值，再top++。
void STPush(ST* pst, STDataType x) { assert(pst); if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = calloc(pst->a, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("calloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } pst->a[pst->top] = x; pst->top++; }
malloc 和 realloc 开辟空间的区别就是 realloc 要传递一个指针，而当我们给 realloc 传递一个空指针，那么它的功能就和 malloc 相同。
2.3 出栈
出栈只需要将 top --就访问不到这个元素了。在出栈时我们要判断栈中是否还有元素。
void STPop(ST* pst) { assert(pst); assert(pst->top > 0); pst->top--; }
2.4 读取栈顶元素
栈顶元素就是我们插入的最后一个元素。由于top表示的是下一个元素的下标，所以读取栈顶元素是top要减1。
STDataType STTop(ST* pst) { assert(pst); assert(pst->top > 0); return pst->a[pst->top - 1]; }
2.5 判断栈空
bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; }
2.6栈的销毁
这里使用的内存是动态开辟的，因此在我们使用完后要及时释放掉内存，否则会造成内存泄漏。
void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = 0; pst->capacity = 0; }
3. 栈完整源代码
Stack.h
#include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* a; int top; // 标识栈顶位置的 int capacity; }ST; void STInit(ST* pst);//初始化 void STDestroy(ST* pst);//销毁 void STPush(ST* pst, STDataType x);//入栈 void STPop(ST* pst);//出栈 STDataType STTop(ST* pst);//读取栈顶元素 bool STEmpty(ST* pst);//判断栈空
Stack.c
#include"Stack.h" void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->capacity = 0; pst->top = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = 0; pst->capacity = 0; } void STPush(ST* pst, STDataType x) { assert(pst); if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = calloc(pst->a, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("calloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } pst->a[pst->top] = x; pst->top++; } void STPop(ST* pst) { assert(pst); assert(pst->top > 0); pst->top--; } STDataType STTop(ST* pst) { assert(pst); assert(pst->top > 0); return pst->a[pst->top - 1]; } bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; }
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。
