原本今天想给大家讲讲快速选择算法的，但是发现一连写了好几篇排序相关了，所以临时改了题目，今天聊点数据结构，来看看经典并且简单的数据结构——栈。
栈这个结构我想大家应该都耳熟能详，尤其是在很多地方将和堆并列在一起，称作“堆栈”就更广为人知了。但其实堆和栈本质上是两种不同的数据结构，我们不能简单地混为一谈。让我们先从比较简单的栈开始。
栈和队列的本质其实都是数组（严格地说是线性表）。只不过我们在数组上增加了一些限制，使得它满足一定的条件而已，所以很多对数据结构畏首畏尾的同学可以放宽心，栈没什么特别的花样，就是一种特殊的数组。
和其他广义上的线性表数据结构比起来，栈的特殊性只有两条，一条是先进后出，另一条是只能从数组的一侧读写。但本质上来说这两条是一样的，由于我们只能从一侧读写元素，所以进的越早出的越晚，当然是先进后出。从下面这张图应该很容易能看明白。
栈规定了我们只能从一侧进行读写，常规上我们将能够读写的一侧称作是栈顶。不能读写的另一侧称为是栈底。从上面的图可以看到，只有栈顶的元素出栈了之后，才能访问到栈底的元素。
我们用Python的数组来实现栈这个数据结构，去掉注释真的只有30行不到，可以说是非常简单，我们先来看代码。
class Stack(object): def __init__(self, size_limit=None): self._size_limit = size_limit self.elements = [] self._size = 0 # 进栈，判断是否越界 def push(self, value): if self._size_limit is not None and len(self.elements) > self._size_limit: raise IndexError("Stack is full") else: self.elements.append(value) self._size += 1 # 判断栈是否为空 def is_empty(self): return self._size == 0 # 栈清空 def clear(self): self.elements = [] self._size = 0 # 访问元素数量 def size(self): return self._size # 查询栈顶元素 def top(self): return self.elements[-1] # 弹出栈顶元素 def pop(self): val = self.elements.pop() self._size -= 1 return val本质上来说，一般的栈实现只有以上这么几个方法，可能会更少。因为有些语言当中的栈，top和弹出是合并的。意味着访问必须要弹出，不支持非弹出访问。所以栈的实现逻辑是非常简单的，甚至可以说是毫无技术含量，非常适合入门数据结构。
当然，从另一个方面也可以说栈的实现原理并不太重要，相比之下更重要的是栈一般会用在什么地方。
栈最广泛的应用就是在操作系统当中，比如在程序执行调用方法的时候，在编译器内部，其实是记录了一个当前调用的方法栈。举个例子，比如当前调用到的方法是A，如果在A方法中又去调用了方法B，那么计算机就会在系统方法栈当中存储一个指向B方法的指针，如果B方法又调用到了C方法，那么又会新增一个C的指针。当C方法执行结束，那么C就会弹出，计算机会将C的结果带入B，继续执行之前的B，以此类推，直到栈空为止。
那么，问题来了，如果一个方法A自己调用自己会怎么样？
答案是计算机会创建一个新的A的指针填入栈中，如果A继续递归，那么系统再创建一个新的指针入栈……
从上面这个过程，我们可以确定两个事情。第一，我们写程序时候的递归，在编译器内部其实是以栈的形式执行的。第二，如果我们用一个死循环去不停地递归，由于栈存在大小限制，所以当栈的深度超过限制的时候，就会出现SystemStackExceed的错误。也就是说递归并不是无限的，因为除了操作系统对于运行内存的限制之外，编译器还会有最大递归深度的限制，防止递归中死循环导致系统崩溃。虽然各个语言实现机制不完全一样，但是有一点是肯定的，递归深度是有限的，我们不能无限制递归。
那问题来了，如果我们系统就是会存在大规模的递归怎么办？难道还要手动给机器加内存吗？
这是ACM玩家在赛场上经常遇到的问题之一，有经验的选手在第一天的热身赛时一定会做的事情除了配置vim或者其他IDE之外，就是会测试一下电脑的最大递归深度。在C++当中，是支持通过汇编语言强行打开递归深度限制的，但是即使如此也是有限的，并且据我所知只有C++可以这么干，对于其他语言，以及开大了递归深度还是不够用的情况，就只有一种办法，就是手动建栈模拟递归。
许多同学可能觉得递归痛苦，但是如果他们试着手动建栈来模拟递归的话，会发现要更加痛苦。不仅要额外增加变量存储中间状态，并且对于编程也是一个巨大的挑战。