栈

特点：

栈的最大特点就是后进先出（LIFO）。对于栈中的数据来说，所有操作都是在栈的顶部完成的，只可以看栈顶元素，只能够向栈的顶部压入数据，也只能从栈的顶部弹出数据。

实现：

利用一个单链表来实现栈的数据结构。而且，因为我们都只针对栈顶元素进行操作，所以借用单链表的头就能让所有栈的操作在O(1)的时间内完成。

S为栈顶指针 如果打算用一个数组外加一个指针来实现相似的效果，那么，一旦数组的长度发生了改变，哪怕只是在最后添加一个新的元素，时间复杂度都不再是 O(1)，而且，空间复杂度也得不到优化。

应用场景

在解决某个问题的时候，只要求关心最近一次的操作，并且在操作完成了之后，需要向前查找到更前一次的操作。

典型题目

求解算数表达式的结果（LeetCode 224、227、772、770)求解直方图中最大的矩形区域（LeetCode 84）