用动图详细讲解——栈

栈

栈的概念：

栈：

一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，是操作受到限制的线性表，遵行后进先出LIFO（Last In First Out）的原则。

简单理解就是一个一端封口，另一端没有封口的管子，你往里面放直径与管子的直径相同的球，不管你放多少球，你先取的一定是最后放的球，最里面的球要把前面的球全部取出来才能取到。这个管子里的空间就相当于栈的空间，球就相当于你所要放入栈的数据

栈顶和栈底

进行数据插入和删除操作的一端称为栈顶，另一端称为栈底，非空栈中的栈顶指针始终在栈顶元素的下一个位置上，空栈时，栈顶指针和栈底指针指向同一块位置。

借助管子和球的例子，简单理解就是管子封口那里就是栈底，管子中最外层的球的下一个可以存放球的空间，但还没有存放球的位置就是栈顶，不能直接理解为管口就是栈顶。

当管子中没有球时（空栈），栈顶和栈底所指向的位置相等，都指向管子最里面所能存放一个球的空间

压栈和出栈

栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶，栈的删除操作叫做出栈。出数据也在栈顶。

入栈gif动画

出栈gif动画

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾部插入数据的代价比较小，可以根据下标直接锁定尾部。
用链表(无头单向非循环链表)在尾部插入数据的代价比较大，需要先遍历一遍才能找到尾部，但也不是不可以，不过尽量用数组比较好一些。

对于栈的实现，有这几个功能，

1. 初始化栈
2. 检测栈的容量是否充足(不充足进行扩容)
3. 入栈
4. 出栈
5. 获取栈顶元素
6. 获取栈中有效元素个数
7. 检测栈是否为空(为空返回非0结果，不为空返回0）
8. 销毁栈

我们将用函数对这些功能进行封装

用结构体自定义一个栈的数据类型

// 支持动态增长的栈typedefint STDataType;typedefstructStack{
    STDataType* a;int top;// 栈顶int capacity;// 容量 }Stack;

因为我们不知道存放在栈中的数据的类型，所以将存放数据的类型用

typedef

重命名为

STDataType

，以方便随时更改。（这里我们存放数据的类型是

int

）

Stack

就是我们定义并重命名的栈的数据类型

STDataType* a

指向栈用数组存放数据的地方起始位置，即栈底

top

是栈顶，也是用来访问数组尾部的下标

capacity

是栈的容量，指栈所能容纳多少的数据

初始化栈

voidStackInit(Stack* ps){assert(ps);
    ps->a =NULL;
    ps->top = ps->capacity =0;}

将栈的地址传过来，对其成员进行初始化

assert(ps)

对传过来的地址进行空指针的判断，因为传过来的地址不能为空

ps->a = NULL

将指针为空，表明栈的容量为0

ps->top = ps->capacity = 0

top记录栈顶位置，capacity记录栈的容量，当容量不足时(也就是ps->top == ps->capacity)进行扩容

检测栈的容量是否充足(不充足进行扩容)

voidCheckCapacity(Stack* ps){assert(ps);//传过来的指针不能为空if(ps->top == ps->capacity)//相等表明容量不足{//创建一个新的变量，表示新的容量int newcapacity = ps->capacity;//对容量的不足类型判断：//第一种是未扩容过的空栈，则扩容为4个空间；//第二种是扩容过，但是容量不足，则扩容为原来容量的二倍
        newcapacity = ps->capacity ==0?4: newcapacity *2;//使用realloc函数对ps->a扩容为sizeof(STDataType) * newcapacity个字节的空间，并把扩容后空间的起始地址保存在tmp
        STDataType* tmp =(STDataType*)realloc(ps->a,sizeof(STDataType)* newcapacity);if(tmp ==NULL)//判断是否扩容成功，不成功则停止运行并报错{perror("realloc fail");exit(-1);}

        ps->a = tmp;//将扩容后空间的起始地址重新赋予给ps->a
        ps->capacity = newcapacity;//把新的容量记录到ps的成员capacity中}}

未扩容过的空栈

扩容过的栈

注：栈空间起始位置的下标为0

入栈

voidStackPush(Stack* ps, STDataType data){assert(ps);CheckCapacity(ps);//检查容量，容量不足则扩容

    ps->a[ps->top]= data;
    ps->top++;}

动画演示举例，对5个数据进行入栈，且此时的栈为空栈：

检测栈是否为空(为空返回非0结果，不为空返回0）

intStackEmpty(Stack* ps){assert(ps);return ps->top ==0;//栈顶指向下标0，则栈为空，返回非零，若不指向下标0，则栈不为空，返回假}

出栈

voidStackPop(Stack* ps){assert(ps);assert(!StackEmpty(ps));//判断栈是否为空，为空则不能出栈

    ps->top--;}

将栈顶

top-1

即可出栈，类似这个动画，但仅仅是出栈，未对出栈的数据进行存储

获取栈顶元素

STDataType StackTop(Stack* ps){assert(ps);assert(!StackEmpty(ps));//判断栈是否为空，为空则不能获取到元素

    ps->top--;//获得栈顶元素的下标return ps->a[ps->top];//返回栈顶的元素}

这一步对出栈的数据进行了返回，可以进行存储出栈返回的数据

获取栈中有效元素个数

intStackSize(Stack* ps){assert(ps);return ps->top;}

把栈顶top的存储的下标返回，可获得栈中元素的个数

销毁栈

voidStackDestroy(Stack* ps){assert(ps);free(ps->a);//free函数可以将从堆区开辟的空间释放，但不能反复释放，所以需要释放后置为空指针，防止再次释放
    ps->a =NULL;//置为NULL，防止重复释放堆区开辟的空间
    ps->top = ps->capacity =0;//空间释放，栈的容量为0}

C语言实现栈的具体代码

//Stack.h#pragmaonce#include<stdlib.h>#include<assert.h>// 支持动态增长的栈typedefint STDataType;typedefstructStack{
    STDataType* a;int top;// 栈顶int capacity;// 容量 }Stack;// 初始化栈 voidStackInit(Stack* ps);// 入栈 voidStackPush(Stack* ps, STDataType data);// 出栈 voidStackPop(Stack* ps);// 获取栈顶元素 
STDataType StackTop(Stack* ps);// 获取栈中有效元素个数 intStackSize(Stack* ps);// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 intStackEmpty(Stack* ps);// 销毁栈 voidStackDestroy(Stack* ps);

//Stack.c#define_CRT_SECURE_NO_WARNINGS#include"Stack.h"voidStackInit(Stack* ps){assert(ps);
    ps->a =NULL;
    ps->top = ps->capacity =0;}voidCheckCapacity(Stack* ps){assert(ps);//传过来的指针不能为空if(ps->top == ps->capacity)//相等表明容量不足{//创建一个新的变量，表示新的容量int newcapacity = ps->capacity;//对容量的不足类型判断：//第一种是未扩容过的空栈，则扩容为4个空间；//第二种是扩容过，但是容量不足，则扩容为原来容量的二倍
        newcapacity = ps->capacity ==0?4: newcapacity *2;//使用realloc函数对ps->a扩容为sizeof(STDataType) * newcapacity个字节的空间，并把扩容后空间的起始地址保存在tmp
        STDataType* tmp =(STDataType*)realloc(ps->a,sizeof(STDataType)* newcapacity);if(tmp ==NULL)//判断是否扩容成功，不成功则停止运行并报错{perror("realloc fail");exit(-1);}

        ps->a = tmp;//将扩容后空间的起始地址重新赋予给ps->a
        ps->capacity = newcapacity;//把新的容量记录到ps的成员capacity中}}voidStackPush(Stack* ps, STDataType data){assert(ps);CheckCapacity(ps);

    ps->a[ps->top]= data;
    ps->top++;}voidStackDestroy(Stack* ps){assert(ps);free(ps->a);
    ps->a =NULL;
    ps->top = ps->capacity =0;}voidStackPop(Stack* ps){assert(ps);assert(!StackEmpty(ps));

    ps->top--;}intStackEmpty(Stack* ps){assert(ps);return ps->top ==0;}

STDataType StackTop(Stack* ps){assert(ps);assert(!StackEmpty(ps));

    ps->top--;return ps->a[ps->top];}intStackSize(Stack* ps){assert(ps);return ps->top;}