💯💯💯
本篇主要利用数组来实现栈，对于栈的各种操作都作详细介绍，压栈，出栈以及获取栈中元素的操作都是学习栈的必备知识，快来学起来吧！！！
©Ⅰ.栈的概念及结构
栈：是一种特殊的线性表，其只允许在固定的一端进行插入与删除操作。
进行数据的插入和删除的一端称为栈顶，另一端称为栈底。
栈遵循先进后出，后进先出的原则。
压栈：栈的插入操作叫做压栈/入栈/进栈，在栈顶实现
出栈：栈的删除操作叫做出栈。也在栈顶实现。
入栈
出栈
©Ⅱ.栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小。
//下面是定长的静态栈的结构，实际中一般不用，因为不能扩大容量，所以我们主要实现下面的支持动态增长的栈 #define N 10 typedef int STData; struct stack1 { int arr[N];//静态数组 int top;//栈顶 }ST; //支持动态增长的栈结构 #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int STData;//重定义栈使用的数据，如果栈使用的数据不是int类型那么可以通过修改这里从而修改栈的使用数据类型 typedef struct Stack { int* a;//指向一个数组的指针 int top;//栈顶 int capicty;//数组容量 }ST;//重命名为ST //初始化栈表 void STInit(ST*ps); //销毁栈表 void STDestroy(ST* ps); //压栈，在栈顶压入一个元素 void STpush(ST* ps,STData x); //出栈，在栈顶弹出一个元素。 void STpop(ST* ps); //访问栈顶元素 //获取栈有效数据的大小 int STSize(ST* ps); STData STTop(ST* ps); //检查栈是否为空，如果为空返回值为非0，如果是假则返回0； int STSize(ST* ps);
2.1栈的初始化
因为该数组是动态数组，可以增容，一开始我们可以给数组一定的容量，当数组元素个数等于容量时再进行扩容即可。
不过要注意的是top值应该初始化为几呢？
如果初始化为0，那a[top]表示的是有元素还是没有元素呢？
如果初始化为0的化，那top就表示指向栈顶元素下一个位置的地方。
而如果初始化为-1，那才表示的是栈顶元素的位置。一开始没有元素，top为-1，当有元素压栈进来后，top++，变成0，a[top]上就存在元素了。
两中表示方法都可以，但 要注意表示一种就要一种按照该逻辑进行。
void STInit(ST* ps)//初始化栈表 { assert(ps);//判断结构体指针不为NULL； //一上来可以给栈表初始化容量 ps->a = (STData*)malloc(sizeof(STData) * 4); if (ps->a == NULL)//判断是否开辟成功 { perror("malloc"); } //初始话容量为4 ps->capicty = 4; ps->top = 0;//top=0 表示的是指向栈顶元素的下一个位置 //top如果为-1，则表示栈顶元素的位置 }
2.2压栈
在元素入栈之前我们需要考虑是否栈空间已满，而需要进行扩容。
所以一开始我们就需要将扩容操作写下。
每次扩容两倍。容量的大小随之改变。
还要注意的是，当入栈后，top是要进行++，然后top就是指向栈顶元素下一个位置的地方了。
void STpush(ST* ps, STData x)//压栈，在栈顶压入一个元素--在压入之前也要考虑是否需要增容 { assert(ps);//断言判断 if (ps->top == ps->capicty)//当数组元素等于容量时 { //增容 STData* tmp = (STData*)realloc(ps->a, sizeof(STData) * ps->capicty * 2); if (tmp == NULL) { perror("realloc"); } ps->a = tmp;//将扩容的空间赋给a ps->capicty *= 2;//数组的容量也随之变大 } ps->a[ps->top] = x;//将元素压入栈顶，一开始top是0，当元素进去后，再让top指向该栈顶元素后一个位置 ps->top++; }
2.3出栈
在删除数据之前我们需要考虑栈空间里还有没有数据可以删除，当栈空间里没有数据可删，那就立刻停止。
所以我们首先需要对栈进行检查是否为空。
当栈为空时返回非0，不为空时返回0；
int STEmpty(ST* ps) { assert(ps); return ps->top == 0; }
而删除数据的操作我们只要让top–即可，不需要释放空间。
void STpop(ST* ps)//出栈，在栈顶弹出一个元素。 { assert(ps); //删除元素之前要检查栈表是否还有元素可删 assert(!STEmpty(ps));//当栈表为NULL是断言 ps->top--; }
2.4获取栈顶元素
获取栈顶元素也就是top所指向的元素，但要注意每次压入一个数据后top都会++，所以最后top是多加了一次，要想访问最后一个元素也就是栈顶元素需要top-1；
STData STTop(ST* ps)//访问栈顶元素 { assert(ps);//断言判断 return ps->a[ps->top - 1];//top-1的位置才是栈顶元素 }
2.5获取栈中有效元素的个数
其实top的数值大小就是栈中有效元素的个数，一开始top为0，表中没有元素，当有元素时，top就进行++，有一个加一次，有一个加一次，所以最后栈中有效元素的个数就是top的数值
int STSize(ST* ps)//计算栈表长度 { assert(ps);//断言判断 return ps->top; //top的长度就是栈表的长度 }
2.6销毁栈
将栈销毁掉也就是让数据都归还操作系统。
开辟的空间需要释放，定义的变量需要置0；
void STDestroy(ST* ps)//销毁栈表 { assert(ps);//断言判断 free(ps->a);//释放数值空间 ps->a = NULL;//并手动置NULL ps->capicty = 0;//置0 ps->top = 0; }
2.7栈的"打印"
栈是不能进行打印的，因为栈要求数据后入的要先出，而打印的顺序是先入先出。
想要让栈的数据展现出来，那就要按照它的特点，我们先打印栈顶元素，打印完再将栈顶元素出栈，再打印新的栈顶元素，再出栈，知道栈变成空为止。
void test() { ST p; STInit(&p); STpush(&p, 1); STpush(&p, 2); STpush(&p, 3); STpush(&p, 4); STpush(&p, 5); printf("%d\n", STSize(&p));//获得栈中有效元素的个数 while (!STEmpty(&p)) { printf("%d ", STTop(&p));//将栈的数据展现出现，要求先进后出，后进先出 STpop(&p); } STDestroy(&p); }
