栈

概念

1. 一种“操作受限”的线性表，只允许从一端插入删除数据
2. 后进先出，先进后出
3. 顺序栈(数组)，链式栈(链表)

操作

• 入栈 O(1)
• 出栈 O(1)

动态扩容

底层动态扩容数组，栈满后申请更大空间，进行数据搬移

应用

1. 函数调用栈
2. 表达式求值
3. 括号匹配