栈
（一）后进者先出，先进者后出
1，栈的结构特点
后进者先出，先进者后出
2，栈的操作特点
栈是一种“操作受限”的线性表，只允许在一端插入和删除数据，即入栈和出栈。
3，栈的类型
①基于数组的顺序栈
②基于链表的链式栈
（二）复杂度分析
1，固定栈操作的复杂度分析
空间复杂度：O(1)
①(无论顺序栈还是链式栈，存储数据只需要一个大小为n的数组，入栈和出栈操作只需要一两个临时变量存储空间）
②时间复杂度：O(1)
(无论顺序栈还是链式栈，入栈和出栈操作只涉及栈顶个别数据操作）
2，支持动态扩容的顺序栈操作的复杂度分析
①空间复杂度分析：O(1）
②时间复杂度：最好时间复杂度O(1），最坏时间复杂度O(n)，均摊时间复杂度O(1)
出栈：不涉及数据的搬移和内存的重新申请，出栈的时间复杂度仍然为O(1)
入栈：当栈中有剩余空间，时间复杂度为O(1)（最好时间复杂度），当无剩余空间时，则需要搬移数据和重新申请内存，时间复杂度为O(n)（最坏时间复杂度）。
均摊时间复杂度分析：
若当前栈大小为 K，并且已满，当再有新的数据要入栈时，就需要重新申请 2 倍大小的内存空间，并且做 K 个数据的搬移操作，然后再入栈。但是，接下来的 K-1 次入栈操作，我们都不需要再重新申请内存和搬移数据，所以这 K-1 次入栈操作都只需要一个 simple-push操作就可以完成。
这 K 次入栈操作，总共涉及了 K 个数据的搬移，以及 K 次 simple-push 操作。将 K 个数据搬移均摊到 K 次入栈操作，那每个入栈操作只需要一个数据搬移和一个 simple-push 操作。以此类推，入栈操作的均摊时间复杂度就为 O(1)。