# 栈

## 栈

栈是一种操作受限的线性表数据结构，它只允许在一端插入和删除数据。

特定数据结构是对特定场景的抽象，当一个数据集合只涉及在一端插入和删除数据，并且满足后进先出，先进后出的特性，就应该选择“栈”。

数组实现的栈叫做`顺序栈`。

链表实现的栈叫做`链式栈`。

## 不支持动态扩容的栈

* 时间复杂度：`O(1)`
* 空间复杂度：`O(1)`

## 支持动态扩容的顺序栈

* 空间复杂度：`O(1)`
* 最好情况时间复杂度：`O(1)`
* 最坏情况时间复杂度：`O(n)`
* 平均情况时间复杂度：`O(1)`

## 函数调用栈

操作系统给每个线程分配了一块独立的内存块，这种内存被组织成“栈”，用来存储函数调用时的临时变量。

每进入一个函数，就会将临时变量作为一个栈帧入栈，函数调用结束后，再将这个函数对应的栈帧出栈。

函数调用也可以使用其他数据结构，只是这种栈帧后进先出的的特性，与栈最为契合。

## 表达式求值

使用两个栈，一个保存操作数，一个保存运算符。

从左向右遍历表达式，如果遇到操作数，就将操作数入栈，如果遇到运算符，就与运算符栈的栈顶元素比较。

如果比运算符栈的栈顶元素优先级高，就将运算符入栈。

如果优先级低或者相等，就将栈顶元素出栈，然后从操作数栈取2个操作数，进行计算并将结果压入操作数栈，继续比较。

## 括号匹配

从左向右扫描字符串，如果遇到左括号，压入栈中，如果遇到右括号，则将栈顶元素出栈进行比较。

如果匹配，则继续扫描，如果栈为空或者不匹配，说明字符串非法。

扫描结束后，如果栈为空，说明字符串合法，如果栈非空，说明字符串非法。

## 浏览器前进、后退功能

使用两个栈X、Y，并且将首次浏览的页面压入X。

当点击后退按钮，将页面从X出栈，压入Y栈，如果X栈为空，则无法继续后退。

当点击前进按钮，将页面从Y出栈，压入X栈，如果Y栈为空，则无法继续前进。

如果点击了新页面，将Y栈清空。
