特点
先进后出,后进先出
一种操作受限的线性表,只允许在一端插入和删除数据
两种操作: 入栈push和出栈pop
复杂度分析
空间复杂度为O(1)
时间复杂度为O(1)
底层实现分类
顺序栈: 用数组实现的有界栈
链式栈: 用链表实现的无界栈
应用场景
函数调用
操作系统给每个线程分配一块独立内存空间(“栈”数据结构),来存储函数调用时的临时变量。
每进入一个函数,就会将临时变量作为一个栈帧入栈;
当被调用函数执行完成,返回之后将这个函数对应的栈帧出栈。
表达式求值
编译器就是通过两个栈来实现的。
其中一个保存操作数的栈,另一个是保存运算符的栈。
我们从左向右遍历表达式,当遇到数字,我们就直接压入操作数栈;
当遇到运算符,就与运算符栈的栈顶元素进行比较;
如果比运算符栈顶元素的优先级高,就将当前运算符压入栈;
如果比运算符栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈的栈顶取2个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较。
示例: 3+5*8-6计算表达式
还可以适用于类似应用场景:括号匹配