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

🔥引言

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

🌈个人主页：是店小二呀

🌈C语言笔记专栏：C语言笔记

🌈C++笔记专栏： C++笔记

🌈初阶数据结构笔记专栏： 初阶数据结构笔记

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

文章目录

• 一、栈的概念及结构
• 二、关于实现栈的分析
• 三、实现栈的相关接口(Satck.h)
• • 3.1 关于top的定义
  • 3.2 栈的初始化
  • 3.3 入栈操作
  • 3.4 出栈操作
  • 3.5 得到栈顶元素
  • 3.6 得到栈里面元素个数
  • 3.7 判断栈是否为空
  • 3.8 栈的打印
  • 3.9 栈的销毁

    一、栈的概念及结构

    栈是指一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出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;
        }
        

        ---

        

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