1.4 栈

栈（stack）是一种 先进后出 的数据结构，栈的实现比队列更简单，栈只能在栈顶进行操作，要么入栈要么出栈。就像把书一本本地摞起来，最先放的书肯定是摞在下面，最后放的书肯定是摞在上面，摞的时候不允许从中间放进去，拿的时候也是先从最上面开始，不允许从下面或中间抽出来，如图1-19所示。栈的操作虽然简单，但使用还是很广泛的，在算法中经常使用单调栈，比如括号匹配问题，还有中序表达式求值等。