导读
为什么要学习数据结构？
数据结构是关于如何组织（存储）数据的！编程实践中经常涉及到组织（存储）数据，所以要学习数据结构。
那么为啥还要学习抽象数据类型（Abstract Data Type，ADT）呢？
ADT描述了数据集、指明了在数据集上可能执行的操作。ADT是一种规范，它和具体的编程语言无关。尽管Java API提供多种数据结构，但是如果遇到不适用的情形，就需要针对这种情形定义ADT，然后使用Java实现它。况且如果不深入全面地掌握数据结构这方面的知识，就无法理解和合理的使用Java API提供的数据结构。
数据结构和ADT是什么关系呢？
ADT是一个规范，用于一组值以及对这组值执行的操作。而数据结构是使用编程语言对ADT的实现。
那么如何描述ADT呢？
我们仅描述数据和操作，不指明如何保存数据以及如何实现操作，会考虑一些实现的细节，但与具体编程语言无关。
我们借助UML以及对他们的说明来描述ADT。还可以使用伪代码，不过UML足以说明问题。
设计ADT的步骤是什么呢？
确定行为，然后指定数据和操作，并且考虑特殊情况。
ADT Stack（栈）简介
先让我们看看新华字典对栈这个字的解释：
储存货物或供旅客住宿的房屋：货栈。客栈。栈房。
竹木编成的遮蔽物或其他东西：马栈（养马的竹木棚）。栈车（古代用竹木编成棚的车子）。
用木料或其他材料架设的通道：栈道。栈桥（一种形似桥梁的建筑物，用于装卸货物、上下旅客等）。
生活中的栈不考虑对象进出顺序，客人到了客栈，他什么时候走可以，只要他交足了租金，住多久都行，他可能比其他人来的都晚，也比其他人住的久一些。而数据结构当中的栈是一种对象先进后出（Last-In First-Out，LIFO）的集合。
栈更像弹夹，最后压入弹夹的子弹最先被射出。
我们称栈中最上面的位置为栈顶，称栈顶的对象为栈顶对象或栈顶项。
ADT Stack（栈）的规格说明
ADT Stack（栈）操作细节阐述
+push(newEntry:T):void
大家有没有考虑过，如果待操作的栈满了，无法再向里面添加对象了，这时执行入栈操作，我们该如何提示客户呢？是该抛出异常，还是该置之不理。
似乎都有道理，抛出异常可以提醒客户，不要再作入栈操作了。但是，抛出异常后，客户就要处理异常，似乎还不如置之不理，然后客户在入栈前判断是否栈满。
+pop():T与+peek():T
如果出栈的时候，栈已空，怎么办呢？应该返回一个null值吗？还是应该抛出异常，提示客户呢？
如果栈中允许存储null，那么通过返回null来提示栈已空就不合适了，这样作客户无法区分是栈已空还是弹出的对象是null。这种情况下，抛出异常是好方法。
还有一种办法就是先判断栈是否为空，然后在决定是否作出栈操作，这样就不必通过抛出异常来提示客户了，不过要客户自己调用isEmpty方法，这样作等同于将部分实现细节暴露给客户。
ADT Stack（栈）转换为接口
让我们将ADT Stack映射为接口，然后只要实现了这个接口，就可以使用栈这种数据结构了。
栈的应用-程序栈
让我们来看一下栈在实际中的使用情况
程序栈在Java中被称为Java栈，它有什么用呢？
假如，在方法a中调用了方法b，当程序执行到调用方法b的语句时就开始执行方法b，这时b接管了控制权；当方法b执行完，控制权重新回到方法a中，继续执行方法a中尚未执行的语句。那么为了保证这种控制权转换过程中，代码依然能按预想的正确顺序执行，使用了Java栈。
Java栈中的项是什么呢？
Java栈中的项是一种被称为活动记录的对象。这种对象包含了方法的指向当前指令的引用、实参、局部变量，一般地，我们称当前指令的地址为程序计数器。而活动记录中包含的是对程序计数器的引用。
看下面的例子
假设我们以行号代表计数器（缩写为PC），当开始执行main方法时，有一个活动记录对象被压入栈中，当执行到funcA时又有一个活动记录对象被压入栈中，当执行到funcB又有一个活动记录对象被压入栈中，如下图，按时间顺序从左到右的Java栈的变化。
閱讀更多 甜橙很酸 的文章
