当前位置：首页 > news >正文

数据结构--＞栈

news 2025/9/11 14:22:04

💕休对故人思故国，且将新火试新茶，诗酒趁年华💕

作者：Mylvzi

文章主要内容：详解链表OJ题

前言：

前面已经学习过顺序表，链表。他们都是线性表，今天要学习的栈也是一种线性表。那么，什么是栈呢？栈又是如何实现对数据的管理呢，下面进行讲解。

栈的定义：

栈就是一种只能在栈顶进行元素的添加删除的线性表。具有“后进先出”的特性，就是后面进入的元素反而首先被删除！所以栈的这种结构又被称为LIFO结构（Last In First Out）;

我们可以把栈理解为枪的的弹夹，试想，每次压子弹的时候是不是只能从一端插入？先插入的子弹会被先打出去，子弹装填的过程对应着数据的进入，被称为“入栈”，而子弹的射出，对应着数据的删除，被称为“出栈”！

栈的结构：

我们知道，栈的最大特点就是只能在一端进行数据的添加和删除，那栈应该使用哪种结构来实现呢？是数组，还是链表呢？其实，最常使用的应该是数组。因为数组进行尾部数据的删除更简单！（数组的尾部就相当于栈顶），如果使用单链表，我们要保存上一结点的地址；如果使用双向链表，其结构没有数组简单；而且，数组对缓存的利用率要高于链表！能提高效率！

栈的实现：

定义栈元素：

//定义栈元素
typedef int STDataType;typedef struct Stack
{STDataType* a;//存储数据int top;//栈顶int capacity;//容量
}ST;

栈的初始化与删除：

//初始化栈
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;//代表栈顶下一个位置ps->capacity = 0;
}//删除栈
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}

入栈和出栈

//入栈
void STPush(ST* ps, STDataType x)
{assert(ps);//栈满要扩容if (ps->top == ps->capacity){//要考虑最开始top == capacity为0的情况//使用了三目运算符:为0，则新的容量值为4；不为0，新的容量值为原来的2倍int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*newcapacity);if (tmp == NULL){perror("realloc");exit(-1);}//重新赋值ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}//出栈
void STPop(ST* ps)
{assert(ps);//空assert(ps->a);ps->top--;//不需要管原来数据，直接让栈顶向前移动
}

返回栈顶元素：

//返回栈顶元素
STDataType STTPop(ST* ps)
{assert(ps);assert(ps->a);//设置的top位最后一个元素的下一个位置return ps->a[ps->top - 1];
}

计算元素个数和判断是否为空栈

//计算有效值个数
int STSize(ST* ps)
{assert(ps);//top就是栈内的数据个数return ps->top;
}//判断是否为空栈
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

总结：

大家刚接触栈可能很疑惑栈的应用场景有哪些呢？举个例子，在我们上网时在某个网页遇到了一个吸引人的链接，你忍不住好奇心，点了进去，发现是不良网站，你想退到你原先浏览的界面，这是你就可以点击浏览器上方的后退键，就自动退回到原先的浏览界面。其实在这个过程中，一个一个的网页被“入栈”，你进去的不良网站就是栈顶元素，后退键其实是实现了“出栈”的一个过程；

再比如画图软件中的“撤销”操作，本质上也是进行了“出栈”的操作；所以，栈的应用还是很广泛的，其他应用还需要大家自己摸索！

前言：