2.5　栈

图2-22　栈的结构示意图

栈是一种只允许在一端进行插入或删除的线性表，即栈只允许先进后出（First In Last Out，FILO）或者后进先出（Last In First Out，LIFO）。栈的操作端通常被称为栈顶，另一端被称为栈底，栈的插入操作称为压栈（Push），栈的删除操作称为出栈（Pop）。压栈是把新元素放到当前栈顶元素的上面，并使之成为新的栈顶元素；出栈则是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。栈的结构如图2-22所示。

栈的实现方式主要分为两种：一种是基于顺序结构实现的；另一种是基于链式结构实现的。基于顺序结构存储的栈称为顺序栈，基于链式结构存储的栈称为链式栈。无论是基于何种形式实现的栈，一般都要实现这几个方法，分别是判断栈是否为空、判断栈是否已满、压栈操作和出栈操作。值得说明的是，由于链表离散存储的特性，在链式栈中无须检测栈是否已满，只要内存足够大，理论上链式栈是不会满的。

将栈的相关操作定义成Stack接口，代码如下：

下面分别介绍栈的两种实现方式。

2.5.1　顺序栈

基于数组的顺序栈存储模型如图2-23所示。

图2-23　基于数组的顺序栈结构示意图

顺序栈是基于顺序结构实现的，顺序结构添加元素、查找元素和删除元素等操作可参考2.2节顺序表相关实现。顺序栈的实现如下：

创建顺序栈测试类，验证顺序栈的功能。测试代码如下：

执行顺序栈测试类，测试结果如下：

    ----------顺序栈是否为空----------
    false
    ----------顺序栈是否已满----------
    true
    ----------打印顺序栈的元素----------
    9 8 7 6 5 4 3 2 1 0

2.5.2　链式栈

基于链表的链式栈存储模型如图2-24所示。

图2-24　基于链表的链式栈结构示意图

链式栈是基于链式结构实现的，链式存储结构添加元素、查找元素和删除元素等操作可参考2.3节单链表相关实现。链式栈的实现如下：

创建链式栈测试类，验证链式栈的功能。测试代码如下：

执行链式栈测试类，测试结果如下：

    ----------链式栈是否为空----------
    false
    ----------链式栈元素个数----------
    10
    ----------打印链式栈元素----------
    9 8 7 6 5 4 3 2 1 0

2.5.3　栈常见面试考点

（1）栈的概念：栈是只允许在一端进行操作的线性表。

（2）栈的特点：先进后出／后进先出。

（3）栈的存储：

·　顺序栈：顺序存储结构。

·　链式栈：链式存储结构。

·　栈的相关算法：如软件开发人员使用的编辑器中的括号匹配问题。

（4）JDK中的实现：JDK中的Stack类实现了栈，并实现了线程安全的API供开发人员使用。 TievZczBSDxz+ZFVjN4fzQ71dsYnP1ntrucBKKCoToJwia6y2rJm3hFlCydtUZIx