【初阶数据结构】深入解析栈:探索底层逻辑

🔥引言

本篇将深入解析栈:探索底层逻辑，理解底层是如何实现并了解该接口实现的优缺点，以便于我们在编写程序灵活地使用该数据结构。

🌈个人主页：是店小二呀
🌈C语言笔记专栏：C语言笔记
🌈C++笔记专栏： C++笔记
🌈初阶数据结构笔记专栏： 初阶数据结构笔记

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅

一、栈的概念及结构

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

这里主要分享的是跟数据结构相关的栈，而不是指存储内存一块内存区域栈区，栈区是指CPU寄存器里的某个指针所指向的一片内存区域(存放函数的参数值，局部变量的值等)

其中有两个核心操作压栈和出栈(出入数据在栈顶实现）

• 压栈:栈的插入操作叫做进栈/压栈/入栈。入数据在栈顶

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

由于栈的特殊结构特性，所以出栈有多种方式，而入栈只有一种

2.一个栈的入栈序列为ABCDE，则不可能的出栈序列为（ ）
A.ABCDE
B.EDCBA
C.DCEBA
D.ECDBA
答案:D

二、关于实现栈的分析

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。在顺序表章节，说明了静态顺序表的实用价值不大，通常是使用动态，这里实现栈的也是是实现动态栈

三、实现栈的相关接口(Satck.h)

3.1 关于top的定义

在实现之前，对top需要有一个定义。当对栈顶元素修改的时候，top作为一个下标。既然top是一个下标，**那么top为0是代表栈为空还是栈存储一个元素，这个是需要我们去定义的(**在顺序表中，也是需要定义的)。所以栈有两种关于栈顶的定义。

• top为-1代表空，top为0代表一个元素

• top为0代表空，top指向下一个元素下标

其实上面的两种方式都可以的，在插入过程顺序会出现差异

下列的实现都是采用第二种top为0代表空，top指向下一个元素下标

3.2 栈的初始化

void STInit(ST *pst)
{
	assert(pst);//指向一个有效的结构体
	pst->a = NULL;
    pst->top =pst->capacity= 0;
}

3.3 入栈操作

void STPush(ST* pst, StackDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		StackDataType *tmp = (StackDataType*)realloc(pst->a, sizeof(StackDataType)*newcapacity);
		if (tmp==NULL)
		{
			perror("realloc fail!!!");
			return 1;
		}
		pst->capacity = newcapacity;
		pst->a = tmp;//保证安全返回
	}
	pst->a[pst->top] = x;//插入 
	pst->top++;//注意top的意义--之后里面为1没有给数值
}

这里需要注意的是:这里插入就是相当于顺序表的尾插，只有栈顶进行插入，所以没有必要单独实现扩容接口，直接在插入时需要空间进行扩容操作

3.4 出栈操作

void STPop(ST* pst)//跳出
{
	assert(pst);
	assert(pst->top > 0);//top为0，则是为空
	pst->top--;//元素个数--
}

这里需要注意的是:相当于顺序表的尾删，同时要满足保证有数据给你删除

3.5 得到栈顶元素

StackDataType STTOP(ST* pst)//得到栈顶元素
{
	assert(pst);
	return pst->a[pst->top-1];//这里减的话就会有问题
}

这里需要注意的是:这里top是指向下一个元素的下标，需要-1到达栈顶元素下标

3.6 得到栈里面元素个数

int STSize(ST* pst)
{
	return pst->top;//个数
}

3.7 判断栈是否为空

bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;//为0就是空,为真
}

3.8 栈的打印

void STPrintf(ST* pst)
{
	while(!STEmpty(pst))
	{
		printf("%d", STTOP(pst));
		STPop(pst);
		printf("\n");
	}
}

这里需要注意的是:打印是打印栈顶元素，为了下次打印，需要出栈得到新栈顶元素。当栈里面没有数据时，就不要再打印数据，没有数据打印。

3.9 栈的销毁

void STDestroy(ST* pst)//销毁
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top =pst->capacity = 0;
}

---

以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二初阶数据结构笔记，希望对你在学习初阶数据结构中有所帮助！