栈
先进后出，后进先出。栈是一种操作受限的线性表，只允许在一端插入和删除。用数组实现的栈叫做顺序栈，用链表实现的栈叫做链式栈。
复杂度分析
- 空间复杂度：栈在操作过程中，存储空间是提前申请好的，空间复杂度是 $O(1)$
- 时间复杂度：栈的操作只涉及个别元素的操作，所以时间复杂度是 $O(1)$
顺序栈、链式栈扩容
- 顺序栈：顺序栈在栈满之后如果需要扩容需要重新申请一个更大的数组，将数据迁移过去
- 链式栈：栈支持动态扩容，但是需要存储后继节点的地址指针，内存消耗较多
栈的应用
函数调用、表达式求值、括号匹配
利用栈实现浏览器的前进后退
需要使用两个栈：前进栈 X，后退栈 Y，将一次浏览的页面（a、b、c）按顺序压入前进栈 X，在 c 页面点后退则将 c
从 X 出栈，然后放入后退栈 Y 中；再点后退的话同理，将 b 放入 Y 中，此时点前进 则把 b 从Y中出栈，放入 X 中，需要注意的是前进栈 X 入栈时将入栈的元素和 Y 栈的栈顶元素比较，如果相同则 Y 栈顶出栈，不相同则将 Y 栈清空。