栈

      • 栈的概念：
          • 栈：
          • 栈顶和栈底
          • 压栈和出栈
      • 栈的实现
          • 用结构体自定义一个栈的数据类型
          • 初始化栈
          • 检测栈的容量是否充足(不充足进行扩容)
          • 入栈
          • 检测栈是否为空(为空返回非0结果，不为空返回0）
          • 出栈
          • 获取栈顶元素
          • 获取栈中有效元素个数
          • 销毁栈
      • C语言实现栈的具体代码

栈的概念：

栈：

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

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

栈顶和栈底

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

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

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

压栈和出栈

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

入栈gif动画

出栈gif动画

栈的实现

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

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

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

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

用结构体自定义一个栈的数据类型
// 支持动态增长的栈typedef int STDataType;typedef struct Stack{STDataType* a;int top;// 栈顶int capacity;// 容量 }Stack;

因为我们不知道存放在栈中的数据的类型，所以将存放数据的类型用typedef重命名为STDataType，以方便随时更改。（这里我们存放数据的类型是int）

Stack就是我们定义并重命名的栈的数据类型
STDataType* a指向栈用数组存放数据的地方起始位置，即栈底
top是栈顶，也是用来访问数组尾部的下标
capacity是栈的容量，指栈所能容纳多少的数据

初始化栈
void StackInit(Stack* ps){assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;}

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

assert(ps)对传过来的地址进行空指针的判断，因为传过来的地址不能为空
ps->a = NULL将指针为空，表明栈的容量为0
ps->top = ps->capacity = 0top记录栈顶位置，capacity记录栈的容量，当容量不足时(也就是ps->top == ps->capacity)进行扩容

检测栈的容量是否充足(不充足进行扩容)
void CheckCapacity(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个字节的空间，并把扩容后空间的起始地址保存在tmpSTDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);if (tmp == NULL)//判断是否扩容成功，不成功则停止运行并报错{perror("realloc fail");exit(-1);}ps->a = tmp;//将扩容后空间的起始地址重新赋予给ps->aps->capacity = newcapacity;//把新的容量记录到ps的成员capacity中}}

未扩容过的空栈

扩容过的栈

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

入栈
void StackPush(Stack* ps, STDataType data){assert(ps);CheckCapacity(ps);//检查容量，容量不足则扩容ps->a[ps->top] = data;ps->top++;}

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

检测栈是否为空(为空返回非0结果，不为空返回0）
int StackEmpty(Stack* ps){assert(ps);return ps->top == 0;//栈顶指向下标0，则栈为空，返回非零，若不指向下标0，则栈不为空，返回假}
出栈
void StackPop(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];//返回栈顶的元素}

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

获取栈中有效元素个数
int StackSize(Stack* ps){assert(ps);return ps->top;}

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

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

C语言实现栈的具体代码

//Stack.h#pragma once#include#include// 支持动态增长的栈typedef int STDataType;typedef struct Stack{STDataType* a;int top;// 栈顶int capacity;// 容量 }Stack;// 初始化栈 void StackInit(Stack* ps);// 入栈 void StackPush(Stack* ps, STDataType data);// 出栈 void StackPop(Stack* ps);// 获取栈顶元素 STDataType StackTop(Stack* ps);// 获取栈中有效元素个数 int StackSize(Stack* ps);// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps);// 销毁栈 void StackDestroy(Stack* ps);
//Stack.c#define _CRT_SECURE_NO_WARNINGS#include "Stack.h"void StackInit(Stack* ps){assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;}void CheckCapacity(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个字节的空间，并把扩容后空间的起始地址保存在tmpSTDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);if (tmp == NULL)//判断是否扩容成功，不成功则停止运行并报错{perror("realloc fail");exit(-1);}ps->a = tmp;//将扩容后空间的起始地址重新赋予给ps->aps->capacity = newcapacity;//把新的容量记录到ps的成员capacity中}}void StackPush(Stack* ps, STDataType data){assert(ps); CheckCapacity(ps);ps->a[ps->top] = data;ps->top++;}void StackDestroy(Stack* ps){assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;}void StackPop(Stack* ps){assert(ps);assert(!StackEmpty(ps));ps->top--;}int StackEmpty(Stack* ps){assert(ps);return ps->top == 0;}STDataType StackTop(Stack* ps){assert(ps);assert(!StackEmpty(ps));ps->top--;return ps->a[ps->top];}int StackSize(Stack* ps){assert(ps);return ps->top;}