算法入门05

栈

1、栈是一种「操作受限」的线性表，只允许在一端插入和删除数据。

2、栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。不管基于数组还是链表，入栈、出栈的时间复杂度都为 O(1)。

3、均摊时间复杂度一般都等于最好情况时间复杂度。动态扩容的顺序栈，需要重点掌握它的均摊时间复杂度分析方法。