Java Collection 05 - Stack

关于 java.util.Stack<E> 的部分笔记，这是一种先进后出的数据结构，对外暴露的操作方法API数量有限。本文演示代码段的执行环境基于JDK版本1.7。

概述

Stack是一种以Vector为基础，具有先进后出(last-in-first-out或者LIFO)特性的数据结构。Stack只有为数不多的方法可以实现元素的存储和输出操作，其中push()方法用于将一个元素存储到Stack集合的顶部位置， pop()方法则从顶部取出一个元素并将次顶部的元素推到顶部位置， peek()仅仅是获取到顶部的元素， empty()方法用来判断当前Stack是否为空， search()方法则用来计算某个特定元素到Stack顶部的距离。

如果需要用到LIFO特性的数据结构，Deque是一种比Stack更能满足要求的数据结构。Deque能够提供比Stack更为丰富的操作方法API，在实际使用时可以优先考虑Deque。

继承关系

// Stack<E>
--java.lang.Object
  --java.util.AbstractCollection<E>
    --java.util.AbstractList<E>
      --java.util.Vector<E>
        --java.util.Stack<E>

实现接口

类名	实现接口
Stack<E>	Iterable<E>, Collection<E>, List<E>, RandomAccess, Serializable, Cloneable

Stack

Constructor Summary

public Stack()

1 2	public Stack() { }

初始化一个Stack集合。初始化之后，Stack是一个不含有任何元素的空集合。

部分方法

public E push(E item)

public E push(E item) {
    addElement(item);

    return item;
}

将元素item压入到Stack栈顶部位置。实际调用的是Vector的addElement(E obj)方法。

public synchronized E pop()

public synchronized E pop() {
    E       obj;
    int     len = size();

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

    return obj;
}

返回并退出Stack栈顶部位置的元素。首先通过Vector的size()方法获取栈顶位置下标，然后peek()方法会返回处于栈顶位置的元素，最后通过Vector的removeElementAt(int index)方法删除len-1（也就是栈顶位置）的元素。

public synchronized E peek()

public synchronized E peek() {
    int     len = size();

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

返回Stack栈顶部位置的元素。该方法仅返回顶部位置的元素，不会执行删除操作。通过Vector的size()方法得到栈顶位置下标，然后通过Vector的elementAt(int index)直接返回栈顶元素。

public boolean empty()

1
2
3

public boolean empty() {
    return size() == 0;
}

判断当前栈是否为空。

public synchronized int search(Object o)

public synchronized int search(Object o) {
    int i = lastIndexOf(o);

    if (i >= 0) {
        return size() - i;
    }
    return -1;
}

返回元素o在栈中的位置。实际返回的当前元素o与栈顶位置之间的距离，且返回的是栈中距离栈顶位置最近的元素o的位置。如果元素o不存在与栈中，那么就返回-1。

Mr.Muzi