数据结构----栈

前言

Hello，小伙伴们，今天我们继续数据结构的学习，前面我们学习了顺序表和链表的实现，今天的栈知识也是和前面的知识相辅相成。

如果你喜欢我的内容的话，就请不要吝啬自己手中的三连哟，万分感谢！！好，废话不多说，开始我们今天的正题。

1.栈的概念和结构

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶；

出栈：栈的删除操作就叫做出栈。出数据也在栈顶。

栈的底层结构选型：

栈的实现一般可以使用数组或者链表，相对而言数组的结构要更加的简洁。因为数组在尾上插入数据的代价比较小。

2.栈的实现

更前几期的数据结构实现一样，我们还是先在VS2022上创建三个文件：

2.1 栈的定义：

 前面我们说到，栈的底层结构我们采用数组的方式是最好的，所以我们可以怎样来定义栈呢？

诶，我们是不是可以想到我们之前学习过的顺序表呢，他们们的底层逻辑都可以通过数组来实现，整体功能大同小异。

那我们就来试试这样定义栈的结构：

typedef int SDataType;
typedef struct Stack
{
	SDataType* arr;
	int capacity;
	int top;
}stack;

 而在实现栈的功能时我们只要注意，栈的数据插入和数据删除都只是在一端进行就好了！！

2.2 栈的初始化

初始化栈，我们应当怎么来做呢？

我们先来看实现该功能的函数：

2.2.1  void InitStack(stack* ps)函数的定义和实现

/首先实现栈的初始化
void InitStack(stack* ps);

看到这这里有没有人觉得很熟悉呢？

对，其实这里的初始化就是和顺序表的初始化一样的所以开始的时候，我们需要

将 ps->arr置为NULL 

ps->capacity = ps->top = 0;

函数我们就可以这样实现：
 

//首先实现栈的初始化
void InitStack(stack* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

2.2.2 函数功能测试

2.3压栈的实现

2.3.1  void StackPush(stack* ps, SDataType x)的定义和实现

其实，压栈的函数和前面我们遇到的顺序表和链表的实现大致相同：

我们先来看压栈函数的定义：

//实现入栈操作
void StackPush(stack* ps, SDataType x);

再来看看函数的实现逻辑：
在这里我们还是要注意，插入数据的前提就是必须要有足够的空间来存储数据。

所以我们还是要用到CheckCapacity函数来检查存储空间

还不了解这个函数的同学，可以看看我往期的文章中关于顺序表的尾插，里面对该函数有介绍：

文章链接为：http://t.csdnimg.cn/sHzPc

void CheckCapacity(stack* ps)
{
	if (ps->capacity == ps->top)
	{
 
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SDataType* newstack = (SDataType*)realloc(ps->arr, newcapacity * sizeof(SDataType));
		if (newstack == NULL)
		{
			perror("CheckCapacity, realloc:");
			exit(1);
		}
		ps->arr = newstack;
		ps->capacity = newcapacity;
	}
}
 
//实现入栈操作
void StackPush(stack* ps, SDataType x)
{
	assert(ps);
	CheckCapacity(ps);
	ps->arr[ps->top++] = x;//ps->表示栈中有效数据的个数，每插入数据一次，ps->top就+1
}

2.3.2压栈函数的测试： 

 

2.4 出栈函数的实现

2.4.1 void StackPop(stack* ps)函数的定义和实现

//出栈函数的实现
void StackPop(stack* ps);

实现出栈函数其实就和顺序表元素的尾删相似：

 在这里我们需要注意尾删的前提就是必须要有数据可删

bool IsEmpty(stack *ps)
{
	return ps->top == 0;
}
//出栈操作只能在栈顶进行
void StackPop(stack* ps)
{
	assert(ps);
	assert(!IsEmpty(ps));
	ps->top--;
}

 

出栈，就是将当前的栈顶元素排除在有效的数据范围之外，使栈不再包含该数据，在后面插入数据时，新的数据会直接将原来的数据覆盖，不会对栈产生什么影响。

2.4.2 出栈函数的测试：

 2.5获取栈顶元素

2.5.1 GetTop(satck* ps)函数的定义和实现

定义：

SDataType GetTop(stack *ps);

 实现：

SDataType GetTop(stack* ps)
{
	assert(ps && !IsEmpty(ps));
	return ps->arr[ps->top - 1];
}

得到栈顶元素十分的简单，这里实现他，是为下面一个能够展示栈的重要特性的函数的实现做好铺垫！！

2.5.2 获取栈顶元素测试：

2.6 展示栈中的元素

 2.6.1 StackShow 函数的定义和实现

定义：

void StackShow(stack* ps);

实现：

注意：根据栈的特性，栈中的数据不能被遍历也不能被随机访问，只能从栈顶依次取出。

void StackShow(stack* ps)
{
	assert(ps);
//所以在ps->不为NULL的前提下，依次出栈，使所有的数据都有机会成为栈顶元素，这样才能被取出
//这是栈结构的特性！！！
	while (!IsEmpty(ps))
	{
		SDataType data = GetTop(ps);
		printf("%d ", data);
		StackPop(ps);
	}
}

因此，一个栈的数据只能展示一次，之后，栈中的数据全部出栈，失去了访问权限！！

2.6.2 栈元素展示测试：

 

 接下来我们来实现最后一个栈函数。

2.7 获取栈中元素的个数

这个函数的实现十分的简单，因为栈中的元素个数就是ps->top

定义：

SDataType StackCount(stack* ps);

实现：

SDataType StackCount(stack* ps)
{
	assert(ps);
	return ps->top;
}

2.7.1 StackCount 函数的测试

到这里，栈的结构就是实现完了，虽然栈相比于前的链表和顺序表要简单，但他在数据结构中的地十分的重要，在后面的学习中，我们经常会使用栈来解决问题，所以大家一定要认真地理解栈！！ 

结语

今天关于栈的学习就到这里，如果你喜欢我的内容就请不要吝啬自己的三连哟！！

咱们下期再见！！！