栈
1 栈是什么
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
1.1 基本功能
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈可以形象得想象成一个高高的箱子，只能从上面放入与拿出。
1.2 为什么选择“顺序表”为基础
根据对顺序表的了解 ，顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。这样操作简单快速就可以实现“栈”的功能。
因为“栈”只能在栈顶进行操作，如果使用链表就需要频繁找尾，导致时间复杂度较高
而使用顺序表，通过“size”变量的使用可以快速找到尾部，更加方便。
2 功能实现
这是“栈”的功能概况，下面予以实现：
2.1 初始化与销毁
//初始化 void StackInit(Stack* ps) { assert(ps); ps->a = NULL; //栈顶元素的下一个元素 ps->top = 0; ps->capacity = 0; } //销毁 void StackDestroy(Stack* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; }
与顺序表一致，多加了一个"top"变量的初始化。
top : 记录栈顶位置。 (与顺序表的“size”本质相同)
2.2 入栈与出栈
//入栈 void StackPush(Stack* ps, STDataType data) { assert(ps); //容量检查 if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity)； if (tmp == NULL) { perror("relloc failed"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = data; ps->top++; }
与顺序表的尾插功能一致。进行容量检查之后，就可以在尾部进行插入，并将“top”++。
//出栈 void StackPop(Stack* ps) { assert(ps); assert(ps->top > 0); ps->top--; }
出栈的功能更加简单，将“top”–即可。
2.3 获取栈顶元素与获取有效元素个数
//获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top-1]; }
返回“top”前一个即可。
//获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top; }
返回“top”就好。
2.4 检查是否为空
//检测是否为空 bool StackEmpty(Stack* ps) { assert(ps); return ps->top == 0; }
判断"top"是否等于初始值即可。
3 总结
栈可以用来快速解决一些特殊化问题，它独特的性质值得我们学习使用。
