引言：在本篇博客中，我们将学到数据结构——栈，讲到栈的含义与关于栈的数据操作代码。栈可以在顺序表、双向链表以及单链表的基础上实现，而于本篇博客中，我们选择在顺序表的基础上实现栈。

更多有关C语言和数据结构知识详解可前往个人主页：计信猫

目录

 

一，栈的含义

二，栈的结构体的定义

三，栈数据操作函数

1，栈的初始化

2，栈的销毁

3，入栈

 

4，出栈

5，取栈顶的数据

6，获取栈中数据的个数

7，判断栈是否为空

四，结语

---

一，栈的含义

        栈是一种特殊的线性表，只允许在表中固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端成为栈顶，另一端成栈底。

压栈：栈的数据插入操作。

出栈：栈的数据删除操作。

        而因为栈特殊的数据插入和删除遵循LIFO（后进先出）的原则，使得栈可以被比作一个羽毛筒。（因为羽毛球里边的球都是从最上边开始使用的，类比于栈顶）

二，栈的结构体的定义

        这次，我们仍然使用三文件操作法，分别创建stack.h、stack.c、test.c三个文件。

         因为前文提到，栈是一种特殊的顺序表，那么栈的定义应该和顺序表的定义方式极其相似，所以在stack.h中，我们如下定义栈：

//包含实现栈的操作函数所要用到的头文件
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int STDataType;
//创建栈结构体
typedef struct Stack
{
	STDataType* a;//动态数组
	int top;//栈顶的下一位
	int capacity;//数组总空间大小
}ST;

        可能大家会不理解栈中top的含义，那么请看如下的图片讲解吧。

 

        如果栈里边没有元素的时候，那么此时top便指向数组中下标为零的地方。 

三，栈数据操作函数

        因为栈是在顺序表的基础上实现的，所以栈的数据操作函数与顺序表及其类似，甚至更简单，好好听吧，一定可以听懂！

1，栈的初始化

        对于栈的初始化，其实就是将栈结构体中的指针类型赋值为NULL，整型类型赋值为0就可以了，我们直接上代码：

// 初始化栈 
void StackInit(ST* ps)
{
    //断言判断栈不为NULL
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;//top指向栈顶数据的下一位
}

2，栈的销毁

        在该函数中，我们所需要做的就是释放掉动态数组所开辟的空间，再将指针置空，防止野指针的出现，最后将整型类型改为0就可以了。代码如下：

// 销毁栈 
void StackDestroy(ST* ps)
{
	free(ps->a);//释放动态数组空间
	ps->a = NULL;//防止野指针的出现
	ps->capacity = ps->top = 0;
}

3，入栈

        入栈顾名思义，就是在栈顶插入数据。

        而在插入数据之前，我们就需要先判断动态数组的空间是否足够，不够我们就使用realloc函数进行空间大小的修改。判断空间代码如下：

//判断空间是否足够
	if (ps->top == ps->capacity)//top==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!");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}

        于此段代码之中，有两个非常巧妙之处：1，空间是否足够的判断：让我们仔细想想，当top变量等于capacity变量时是什么情况？

         对，就是如上图所示，当两者相等的时候，也就意味着整个动态数就只有一个空间以供使用了，而这时，我们就需要进行空间的动态开辟了。 

         2，三目操作符的使用：仔细想想，以下两种代码有什么不一样的呢？

代码一：
int newcapacity = ps->capacity * 2；
代码二：
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

        其实答案十分简单，在我们对栈进行初始化的时候，我们将top和capacity变量都初始化为了0，那如果是代码一，0*2就为0，则不就乱套了吗？所以我们便使用代码二，用到了三目操作符来避免0*2为0的尴尬情况。

        而之后的入栈函数就十分简单了，但千万别忘了要对top进行++处理！！ 

// 入栈 
void StackPush(ST* ps, STDataType data)
{
	assert(ps);
	//判断空间是否足够
	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!");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = data;//top处加入新的元素
	ps->top++;//栈顶的移动
}

4，出栈

        对于出栈函数，其实我们所需要做的就是删除掉栈顶的元素，并且将栈顶向后移动一位。而对于栈顶元素的删除，我们也无需像链表一样使用free函数，我们只需要将top减1即可，十分的简单。直接上代码！

// 出栈 
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

5，取栈顶的数据

        因为栈顶是一个栈中及其特殊的位置，所以我们也就时不时会用到栈顶的数据，而这个函数就很好的帮我们解决了这个问题。

        在这个函数中，我们唯二需要注意的就是栈不可以为空指针，栈的数据个数不可以为零。代码走起！

// 获取栈顶元素 
STDataType StackTop(ST* ps)
{
	assert(ps);//栈不为空指针
	assert(ps->top > 0);//栈的数据个数不能为零
	STDataType tmp = ps->a[ps->top - 1];//top-1才为栈顶元素的下标
	return tmp;
}

6，获取栈中数据的个数

        这个函数是关于栈的数据操作函数中最简单的一个函数。栈中的数据个数不就是top的值吗，所以我们直接返回top就可以了。代码如下：

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

7，判断栈是否为空

        该函数比较特殊，它使用到的是布尔类型。如果栈为空，就返回true；反之则返回false。而对于是否为空的判断，我们只需要观察top是否为零就可以了。所以代码如下：

// 检测栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;//若top为零，则为true;反之则为false
}

四，结语

        这是有关数据结构中栈的讲解，是不是易如反掌呢？之后我也会接着更新数据结构中另一个知识点——队列的讲解。

        博客不仅是我记录所学习到的知识点的工具，也是我找到同样有学习编程爱好的人的朋友圈，希望我的博客可以对你有所帮助，也希望你可以留下你的鼓励，你的鼓励就是我最大的动力！！加油！