什么是栈，如何实现？

欢迎来到 Claffic 的博客 💞💞💞 

“但有一枝堪比玉，何须九畹始征兰?”

前言：

栈是一种特殊的线性表，就像开盖的桶一样，从底部开始放数据，从顶部开始取数据，那么栈具体是如何实现的呢？这篇博客为你解答：

---

目录

💩Part1：何为栈

1.栈的概念

2.栈的结构 

🪲Part2: 栈的实现

1.前期准备

1.1创建项目

1.2栈的结构

1.3栈的初始化

2.相关功能实现

2.1入栈

2.2检测栈是否为空 

2.3出栈

2.4获取栈顶元素

2.5获取栈中有效元素的个数

2.6销毁栈 

---

Part1：何为栈

1.栈的概念

栈是一种特殊的线性表，只允许从特定的一端插入或删除元素，栈中数据的元素遵循后进先出原则(Last In First Out)。

进行数据插入和删除的一端称为栈顶，另一端称栈底。 

就像个桶子一样，总是先从顶部放入或取出元素。

2.栈的结构 

说完了栈的概念，大家的脑海里也许就会有栈的基本样子了，这里画图解释： 

 我是图示

Part2: 栈的实现

1.前期准备

1.1创建项目

老样子，三个项：

SList.h：头文件，声明所有函数；

SList.c：源文件，实现各函数；

test.c：  源文件，主函数所在项，可调用各函数。

1.2栈的结构

在创建结构体之前，我们不妨要考虑一个问题：
用数组还是链表来实现栈？

数组：存储空间在物理上连续，随机访问时间复杂度O(1)：

链表：存储空间在逻辑上连续，但物理上不一定连续，随机访问时间复杂度O(N).

就栈的特点来说，数组更接近。还是数组香哇。

所以我们 用数组来实现栈 ：

创建一个结构体，其中的元素包含： 

数组首元素的地址；

栈顶；

容量。

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top; // 栈顶int capacity; // 容量
}Stack;

1.3栈的初始化

既然创建了栈，就要进行初始化

无非就是对结构体中的元素进行初始化：

数组容量，先定义一个初始大小：4个元素大小，并且是动态的。

栈顶的话，可以是0，也可以是-1：

0时，top 的位置就是栈顶元素的下一个位置；

-1时，top 的位置就是栈顶元素的位置。

在这里我们取 top = 0；

// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->capacity = 4;ps->top = 0;
}

2.相关功能实现

2.1入栈

所谓入栈，就相当于尾部插入新的数据。

要注意插入数据前需检查是否满容，判断方法也很简单，就看 栈顶与容量 是否相等就可以。

// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->capacity == ps->top){STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = data;ps->top++;
}

2.2检测栈是否为空 

这里把检测栈是否为空单独封装成一个函数，是为了出栈做铺垫；

在栈为空的情况下是不能出栈的，所以出栈前要检测栈是否为空；

这里我们约定 如果为空返回非0结果，如果为不为空返回0 ；

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;//表达式，真为非0，假为0
}

2.3出栈

出栈就相当于删除数据，但又不完全等于删除数据

它 只是改变了栈顶 ，栈顶之外的元素占有的空间不需要释放。

// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));//注意逻辑反，为空就报错ps->top--;
}

2.4获取栈顶元素

因为是栈，总要在栈顶取元素的

// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);return ps->a[ps->top-1];//注意元素个数与下标差1
}

2.5获取栈中有效元素的个数

其实就是栈顶啦，栈顶的数值代表了栈中有效元素的个数；

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

2.6销毁栈 

用完了栈，要记得销毁哦。

其实就是该释放的释放，容量归0，栈顶置为-1，表示没有元素。

// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = -1;
}

代码已上传至 我的gitee

拿走不谢~ 

---

总结：

栈也是线性表，具有后进先出的特点，在有这总需求的情况下可以应用，你学会了吗？

码文不易 

如果你觉得这篇文章还不错并且对你有帮助，不妨支持一波哦  💗💗💗