前言
今天给大家介绍一种特殊的数据结构——栈，栈和我们之前介绍的链表和顺序表一样都是线性结构，那栈为什么特殊呢？接下来请大家和小编一起细细了解。
1.栈的概念
概念：栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈(push）：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈(pop)：栈的删除操作叫做出栈。出数据也在栈顶。
以上就是栈的演示过程，那么我们如何用代码实现这个结构呢，接下来就让我们继续探讨。
2.栈的实现
2.1 栈的结构
对于栈的实现我们即可以使用链表也可以使用顺序表的形式，但是相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
这里我们可以让数组首元素为栈底，尾部为栈底，top指向下一个我们要插入的元素，具体结构如下
typedef int STdatatype; typedef struct Stack { STdatatype* a; int top; int capacity;//表示的是数组容量 }ST;
对于栈的链表结构这里大家也可以了解一下
2.2 初始化栈
void STInity(ST* ps) { assert(ps); ps->a = (STdatatype*)malloc(sizeof(STdatatype) * 4); if (ps->a == NULL) { perror("malloc fail"); return; } ps->capacity = 4; ps->top = 0;//top表示的是下一个元素的地址 }
对于初始化操作这里是比较简单的，这里我们把初始容量置为4，这里由于是改变结构体内部成员，所以我们的形参只需要一级指针即可。
2.3 入栈操作的实现
void STpush(ST* ps, STdatatype x) { assert(ps); if (ps->capacity == ps->top) { STdatatype*temp = (STdatatype*)realloc(ps->a,sizeof(STdatatype) * ps->capacity*4); if (temp== NULL) { perror("realloc fail"); return; } ps->a = temp; ps->capacity = ps->capacity * 4; } ps->a[ps->top] = x; ps->top++; }
对于入栈操作我们需要符合栈的特点，由于我们因为是把数组的尾部当作栈顶的，所以增容时我们只需要让top处的位置处的值为我们需要插入的值即可（添加元素后记得top要加1），还有就是这里我们需要注意当容量不足，我们需要进行增容操作。（由于我们是实现栈，如过进行打印函数进行逐个打印就不符合栈的后进先出的规则，所以我们这里就不好演示，之后总体实现了再给大家看总体效果）。
2.4 判断栈是否为空
bool STEmpty(ST* ps) { assert(ps); return ps->top==0; }
如果栈为空那么top所表示的位置就是0，所以我们只要判断top是否为0即可。相等就返回真，不等就返回假。
2.5 出栈的实现
void STPop(ST* ps) { assert(ps); assert(!STEmpty(ps));//判断栈是否为空 ps->top--; }
2.6 返回栈的长度
int STSize(ST* ps) { assert(ps); return ps->top; }
2.7 返回栈顶元素
STdatatype STTop(ST* ps) { assert(ps); return ps->a[ps->top - 1]; }
2.8 栈的销毁
void STDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = 0; ps->capacity = 0; } 3.总体代码测试 int main() { ST s; STInity(&s); STpush(&s, 1); STpush(&s, 2); printf("%d ", STTop(&s)); STPop(&s); STpush(&s, 3); STpush(&s, 4); printf("%d ", STTop(&s)); STPop(&s); STpush(&s, 5); while (!STEmpty(&s)) { printf("%d ", STTop(&s)); STPop(&s); } return 0; }
这里我们实现的操作时先对1，2进行入栈操作，然后打印栈顶元素，出栈顶元素2，然后入栈3，4然后打印栈顶元素，然后出栈4，最后入栈5，最后依次对栈顶元素进行打印出栈的操作，那么这里得到的结果应该是2，4 ，5，3，1.
运行一下，我们看结果
总代码
Stack.h #include<stdio.h> #include<stdlib.h> #include<stdbool.h> # include<assert.h> typedef int STdatatype; typedef struct Stack { STdatatype* a; int top; int capacity; }ST; void STInity(ST*ps); void STpush(ST* ps,STdatatype x); void STDestory(ST* ps); void STPop(ST* ps); int STSize(ST* ps); STdatatype STTop(ST* ps); bool STEmpty(ST* ps); Stack.c #include"Stack.h" bool STEmpty(ST* ps) { assert(ps); return ps->top==0; } void STInity(ST* ps) { assert(ps); ps->a = (STdatatype*)malloc(sizeof(STdatatype) * 4); if (ps->a == NULL) { perror("malloc fail"); return; } ps->capacity = 4; ps->top = 0;//top表示的是下一个元素的地址 } void STpush(ST* ps, STdatatype x) { assert(ps); if (ps->capacity == ps->top) { STdatatype*temp = (STdatatype*)realloc(ps->a,sizeof(STdatatype) * ps->capacity*4); if (temp== NULL) { perror("realloc fail"); return; } ps->a = temp; ps->capacity = ps->capacity * 4; } ps->a[ps->top] = x; ps->top++; } void STPop(ST* ps) { assert(ps); assert(!STEmpty(ps)); ps->top--; } int STSize(ST* ps) { assert(ps); return ps->top; } STdatatype STTop(ST* ps) { assert(ps); return ps->a[ps->top - 1]; } void STDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = 0; ps->capacity = 0; } text.c #include"Stack.h" int main() { ST s; STInity(&s); STpush(&s, 1); STpush(&s, 2); printf("%d ", STTop(&s)); STPop(&s); STpush(&s, 3); STpush(&s, 4); printf("%d ", STTop(&s)); STPop(&s); STpush(&s, 5); while (!STEmpty(&s))
