速学数据结构 | （超级干货）业界程序员公认的实现栈最简单的方法！太简单了

⛺️生活的理想，就是为了理想的生活!

📋 前言

🌈hello！各位铁铁们大家好啊，今天来给大家更新一下栈这个数据结构,栈实际上是实现一种后进先出效果。 ⛳️一般我们在C语言学习期间函数开辟的空间就是在栈区，那么我们今天就来领略一下栈的风采吧!

文章目录

📋 前言
一、栈的概念及结构
二、栈的实现
2.1 栈的定义与初始化
2.2 栈的入栈实现
2.3 栈的出栈实现
2.4 获取栈顶元素
2.5 获取栈的数据个数
2.7 栈的判空实现
2.6 销毁栈
📝全篇总结

一、栈的概念及结构

栈：其实是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底 。栈中的数据元素遵守后进先出 LIFO（Last In First Out） 的原则。

其主要有俩个操作：
压栈/入栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

具体我们可以看一下图片来了解了解，其实栈有点类似堆砖块。想拿到最下面的砖块必须要把上面的都拿走才可以拿到。

在这里插入图片描述

二、栈的实现

既然栈实现的是后进先出的方法，那么我们选用顺序表，还是链表来实现呢? 答案肯定是数组啦。

后面先出说明只需要 尾插尾删
而顺序表尾插就只需要把下标 -1 ，就好了效率不知道比链表快了多少倍
链表实现的话尾插尾删的效率都不够高。

2.1 栈的定义与初始化

既然选择好了使用什么类型来实现栈那么接下来就是先定义栈的结构：

首先需要定义一个 指针 来开空间
然后需要一个 capacity 来记录容量
一个 top 来记录栈顶元素

📚 代码演示：

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps)
{
assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

2.2 栈的入栈实现

入栈要注意的是考虑好边界情况：

如果栈满了怎么办？如何开辟空间
栈如果为零怎么办？如何开辟空间

📚 代码演示：

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	// 11:40
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

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

2.3 栈的出栈实现

出栈就很简单这个也是，顺序表实现栈表的好处：

只需要 top-- 就好了不需要去真正的删除数据

📚 代码演示：

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);

	// 
	assert(ps->top > 0);

	--ps->top;
}

2.4 获取栈顶元素

获取栈顶元素也非常简单，前面我们定义了一个 top 这时候就可以派上用场了：

只需要 ps->a[top] ,就可以一键获取了
还要注意一下断言判空一下，栈如果都没有元素了那还怎么获取

📚 代码演示：

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);

	// 
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}

2.5 获取栈的数据个数

这个也是一样，贼简单直接 ps->top 就是栈区数据的个数：

📚 代码演示：

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

	return ps->top;
}

2.7 栈的判空实现

栈的判空这个如何实现呢？是不是只要 ps->top == 0 就是空了呢？

连数据都没有了，栈区肯定是空的

📚 代码演示：

// 检测栈是否为空，如果为空返回真，如果不为空返回假 
bool StackEmpty(Stack* ps); 
{
	assert(ps);

	return ps->top == 0;
}

2.6 销毁栈

销毁现在对于我们已经是轻车熟路了，free( ) 掉动态开辟的空间，在 free( ) 掉栈就好了；

📚 代码演示：

// 销毁栈 
void StackDestroy(Stack* ps)
{
	free(ps->a);
	free(ps);
}

📝全篇总结

☁️ 好了以上就是栈的实现了，总的来说还是很简单的一会就写完了。大家不要忘记练习哦！

在这里插入图片描述