栈(stack)，是一张特殊的表，特殊之处在于限制了插入和删除只能在固定的位置。它在我们平时开发和维护系统中很少直接用到，所以很多人对它并不了解，但是在JDK中，栈是一个很重要的表结构，因此我们还是有必要对它进行了解。

1．栈的简介

前面说到，栈是对表的插入和删除进行了位置限制，这个位置叫做顶(top)，对栈的基本操作只有进栈(push)和出栈(top)，如示意图。这就是我们常说的后进后出表(LIFO表)。

栈既然是表，能够实现表的都可以实现栈，典型的有两种：数组实现(如ArrayList)和 链表 实现(类似LinkedList)，之所以是类似LinkedList，是因为栈的链表是 单链表 结构，而LinkedList是双链表结构。实现原理很简单，只允许对最后一个元素进行操作即可。例如：在Arraylist的添加方法中，只允许使用add(e)方法，其他重载方法不实现。

2．接下来，为大家举几个实用例子。

应用一：平衡符合

代码编译器在检查语法时，如符号“{ [ ] }”是合法的，而“{ [ } ]”就是错误的，显然还有更复杂的情况。我们不可能为此检查编写一个大型程序，更何况你也不可能考虑到所有的异常情况。这时栈就起到了作用，具体流程如下：

首先，我们将向右开口的符号称为开放符号，向左开口的符号称为封闭符号。现在我们从开头检查一段代码：先做一个空栈，当读到第一字符时，如果是一个开发符号，则推入栈中，如果是一个封闭符号，则报错；然后接着向下读，读到开放符号就推入栈中，读到封闭符号就弹出栈顶的符号，如果不是对应的开放符号就报错；就这样一直读下去，直到报错或者代码检查完毕。

应用二：后缀表达式

先举一个简单的例子，我们来计算3 + 4 + 5 * 6的结果是多少，我相信没上过学的也知道等37，但是我们的计算机并不具备这种计算能力，除非有人告诉它。在没人告诉它之前，他的结果是72，那是因为它是从左向右顺序计算的。就算现在有人告诉它乘号具有优先计算权，它的运算过程是3 + 4 = 7，然后将7 存入，再计算5 * 6 = 30 存入，最后才能得出37。这消耗了很大的资源，并且对于复杂的计算，有大括号，小括号，幂次方等等，你不可能针对每一种情况都写一套代码。

这时，我们就会用到后缀记法或者叫逆波兰记法，所使用的的表达式叫后缀表达式。例如同样计算3 + 4 + 5 * 6，他的后缀表达式写为：” 3 4 + 5 6 * + ”(这种表达式是如何得来的，请看应用三)。首先建一个空栈，从左向右读这个表达式，读到一个数字就将其推入栈中，读到运算符合就弹出栈顶的两个数进行运算，将其结果推入栈中。具体 算法 是，将3和4推入栈中，读到+号，就将3和4弹出，并将计算的结果7推入栈中，向后读到5和6，将5和6推入栈中，之后读到*号，将5和6弹出将结果30推入栈中，最后读到+号，就将7和30弹出结果为37结束。图例如下(没有合适图形，用Excel代替，大家勉强看吧，总比没有强。)：

这种算法就是后缀记法，或者叫逆波兰记法。

应用三、 中缀 转后缀

如应用二所示，这种后缀表达式是如何得来的呢，当然是由中缀表达式转化而来，我们将3 + 4 + 5 * 6这种 运算符 号在中间的表达式称作中缀表达式，这种3 4 + 5 6 * + 运算符在后面的称作后缀表达式。中缀转后缀同样是用到了栈原理。同样的例子：

首先我们先定义运算符号的有限级，+ – 为低级，* / 为高级，括号为更高级；然后建一个空栈，一个输出流；第三步开始读数据，读到3放入输出流，接着读到 + 号，推入栈中，读到4 ，放入输出流，再读到 + 号，因为加号是平级了，则将栈中的 + 号写入输出流，将新读到的 + 号推入栈中。接着读到5 ，放入输出流，读到 * 号，放入栈中，再将读到的6放入输出流，由于 * 号比 + 号优先级高，所以将 * 号弹出放入流中，已经读到了最后，所以将栈中的 + 号弹出放入流中，具体流程图如下：

复杂一点的算法也是如此，如果相邻的两个运算符是同级的，就输出前一个运算符，如果后一个比前一个高级，就再向后相比，如果后一个比前一个低级，就输出前一个运算符。

应用四：方法的调用

方法的调用类似于检测平衡符号，不同的是，当调用一个新方法时，调用一个新方法时，主调例程所有的 局部变量 需要由系统存储起来，否则被调用的新方法将会重写主调例程的变量所使用的的内存；并且主调例程的当前位置也需要保存起来，否则新方法运行完之后不知道向哪里转移。方法的调用和返回基本上类似于应用一的开放符号和封闭符号。(这样看起来是不是就明白多了)

栈也是有一定的内存空间的，如果有太多同时运行的着的方法，栈空间是很容易用尽的。很多语言系统并没有检测栈溢出的功能，但是 Java 除外，一旦栈内存溢出，Java就会抛出一个异常。

关于栈就介绍到这了，如果不妥之处敬请斧正。