栈
栈
栈是一种操作受限的线性表数据结构，它只允许在一端插入和删除数据。
特定数据结构是对特定场景的抽象，当一个数据集合只涉及在一端插入和删除数据，并且满足后进先出，先进后出的特性，就应该选择“栈”。
数组实现的栈叫做顺序栈。
链表实现的栈叫做链式栈。
不支持动态扩容的栈
时间复杂度：
O(1)空间复杂度：
O(1)
支持动态扩容的顺序栈
空间复杂度：
O(1)最好情况时间复杂度：
O(1)最坏情况时间复杂度：
O(n)平均情况时间复杂度：
O(1)
函数调用栈
操作系统给每个线程分配了一块独立的内存块，这种内存被组织成“栈”，用来存储函数调用时的临时变量。
每进入一个函数，就会将临时变量作为一个栈帧入栈，函数调用结束后，再将这个函数对应的栈帧出栈。
函数调用也可以使用其他数据结构，只是这种栈帧后进先出的的特性，与栈最为契合。
表达式求值
使用两个栈，一个保存操作数，一个保存运算符。
从左向右遍历表达式，如果遇到操作数，就将操作数入栈，如果遇到运算符，就与运算符栈的栈顶元素比较。
如果比运算符栈的栈顶元素优先级高，就将运算符入栈。
如果优先级低或者相等，就将栈顶元素出栈，然后从操作数栈取2个操作数，进行计算并将结果压入操作数栈，继续比较。
括号匹配
从左向右扫描字符串，如果遇到左括号，压入栈中，如果遇到右括号，则将栈顶元素出栈进行比较。
如果匹配，则继续扫描，如果栈为空或者不匹配，说明字符串非法。
扫描结束后，如果栈为空，说明字符串合法，如果栈非空，说明字符串非法。
浏览器前进、后退功能
使用两个栈X、Y，并且将首次浏览的页面压入X。
当点击后退按钮，将页面从X出栈，压入Y栈，如果X栈为空，则无法继续后退。
当点击前进按钮，将页面从Y出栈，压入X栈，如果Y栈为空，则无法继续前进。
如果点击了新页面，将Y栈清空。
Last updated
Was this helpful?