定义

后进者先出，先进者后出，这就是典型的“栈”结构。

image.png

从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。

从功能上来说，数组或链表确实可以替代栈，但特定的数据结构是对特定场景的抽象，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，更容易出错。

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选“栈”这种数据结构。

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

存储空间复杂度O(n)
栈操作的时间复杂度和空间复杂度为O(1)

可扩容顺序栈

顺序栈扩容：申请新的数组空间并复制元素，扩容时间复杂度为O(n)
image.png

顺序栈入栈时间复杂度：O(1)

顺序栈入栈时间复杂度：
image.png
均摊时间复杂度：O(1)