如何理解栈

类似摞在一起的盘子，放的时候一个个放，取的时候从最上面取。
栈的特点：后进先出，先进后出
从操作特性上看，栈是一种操作受限的线性表。

如何实现一个栈

栈既可以用数组也可以用链表实现，用数组实现的栈叫顺序栈，用链表实现的栈，叫链式栈。

如果用数组实现一个栈的操作，当存储空间不够的时候，会无法入栈。
动态扩展，是栈空间不够时，重新申请内存和数据搬移。

栈在函数调用中的应用

函数调用栈
操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对于的栈帧出栈。

栈在表达式求值中的应用

用两个栈来实现，一个保存操作数，一个保存运算符，当栈顶元素的优先级低或者相同，从运算符去除栈顶运算符，操作数栈取出两个操作数，进行计算，然后再入栈。
image.png

栈在括号匹配中的应用

比如{}都为合法格式，而{[}()}为不合法，使用栈来检测
当扫描到做括号时，将其压入栈中，当扫描到右括号时，从栈中取出一个左括号。如果能匹配成一对，则继续扫描剩下的字符串，如果没有匹配到则说明为非法格式。

如何实现浏览器的前进后退

是使用栈的方式来实现的
使用两个栈，当前进的时候从Y出栈，在X入栈，当后退的时候，从X出栈，入Y栈。
image.png

思考

函数调用栈为什么用栈来保存临时变量，其他数据结构不行吗
用别的也行，只不过符合后进先出，用栈比较合适

LeetCode练习题 20,155,232,844,224,682,496