欢迎来到 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

拿走不谢~


总结:

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

码文不易

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