第九十二章 Java标准库－栈(Stack)

1 概述

栈是一种先进后出(First In Last Out)的数据结构。栈常常用于实现函数调用或者表达式的解析过程。Java标准库中提供了java.util.Stack类，用于帮助开发人员实现栈的功能。Stack继承自java.util.Vector类，所以，Stack也实现了Collection接口、List接口和java.util.RandomAccess接口。

Java标准库中包含的、与Stack相关类的结构如下图所示。

图一 Stack相关类结构图

2 栈的接口

因为Stack继承自Vector类，所以Stack类可以使用所有Vector已实现的接口。作为栈，Stack类还提供了peak()、pop()和push()方法。

push()方法实现了压栈操作，即将新元素压入栈顶。pop()则将栈顶元素弹出。如果此时栈为空，则会抛出EmptyStackException异常。

peek()方法则返回栈顶元素，但是并不弹出栈顶元素。如果栈为空的话，则抛出EmptyStackException异常。

empty()方法判断当前Stack对象是否为空。search()方法查找给定元素是否在栈中。如果存在的话，返回这个元素到栈顶的距离。

如下是使用Stack的一个简单示例。

Stack<Integer> stack = new Stack<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop();

System.out.println(stack.empty()); // 打印false，stack不为空
System.out.println(stack.search(1)); // 元素1离栈顶的距离为1

3 栈的实现

在OpenJDK 15中，java.util.Stack的实现非常简洁。Stack继承自java.util.Vector。Stack不包含任何成员变量。所有的元素都存放在父类Vector中。push()、pop()和peek()分别调用了父类的addELement()、removeElementAt()和elementAt()方法。Vector类的实现细节可参考这里。

// OpenJDK 15
package java.util;

public
class Stack<E> extends Vector<E> {
    ...
    public E push(E item) { // 入栈操作
        addElement(item);

        return item;
    }

    public synchronized E pop() { // 出栈操作
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    public synchronized E peek() { // 查看栈顶元素
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
    ...
}

4 小结

本章介绍了Stack类的使用方法和实现细节。Stack类实现了堆栈数据结构。它提供了压栈和出栈操作，用于实现先进后出的数据处理特点。Stack类继承自Vector类。因此，Stack并未声明任何成员变量来保存元素，所有的数据都保存在父类Vector中。