Java集合系列[6]-Stack分析与源码解析

发表于

概述

上次学习了Vector,今天学习Stack,这也是Collecton集合下最后解析的一个了.Stack比较简单,它直接继承自Vector. 学习内容分为下面几个部分:

  1. Stack简介
  2. 数据结构分析
  3. 源码解析(基于JDK1.8)

Stack简介

1
public class Stack<E> extends Vector<E>

Stack是栈,直接继承自Vector,它的特点是先进后出(FILO,first in last out).

java工具包的Stack是继承矢量队列的,由于Vector是通过数组实现的,这意味着Stack也是通过数组实现的,而非链表.当然我们也可以把LinkedList作为栈来使用看这里!!

Stack的构造方法

Stack只有一个构造方法,如下:

1
public Stack()

Stack的API

1
2
3
4
5
public E push(E item);//把元素置到栈顶
public synchronized E pop();//移除栈顶的元素,并返回该元素
public synchronized E peek();//返回栈顶元素,不删除
public boolean empty();//判断栈是否为空
public synchronized int search(Object o);//返回对象在栈中的位置,栈底元素的位置为1,往上推

数据结构分析

在Java集合系列[5]-Vector分析与源码解析一文已经详细介绍过Vector的数据结构了,这里就不对Stack的数据结构进行说明,因为Stack的数据结构和Vector的一模一样的.

Stack的继承关系

1
2
3
4
5
java.lang.Object
    java.util.AbstractCollection<E>
        java.util.AbstractList<E>
            java.util.Vector<E>
                java.util.Stack<E>

Stack与Collection的关系

Stack与Collection的关系

源码解析

源码解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package java.util;
public
class Stack<E> extends Vector<E> {
    //构造一个空栈
    public Stack() {
    }
    //把元素item置到栈顶
    public E push(E item) {
        addElement(item);
        //返回刚添加的元素
        return item;
    }
    //删除栈顶的元素,并返回删除的元素
    //好奇这里的内部为什么不直接使用Vector的remove方法,仅仅是因为remove方法是List接口的方法吗?
    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);
    }
    //判断栈是不是为空
    public boolean empty() {
        return size() == 0;
    }
    //查找元素o在栈中的位置,从栈底往栈顶的方向开始计算,以1为基数
    public synchronized int search(Object o) {
        //找出该元素在队列中的位置
        int i = lastIndexOf(o);
        
        //计算从底部为1开始到该元素的距离
        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }
    //版本ID,这个用于版本升级控制,这里不理会
    private static final long serialVersionUID = 1224463164541339165L;
}

总结

  1. Stack实际上也是通过数组去实现的.
    • 执行push时,是通过将元素添加到数组为末尾;
    • 执行peek时,是返回数组末尾的元素;
    • 执行pop时,是删除并返回数组末尾的元素;
  2. Stack继承Vector,意味着Vector所拥有的属性和功能,Stack都拥有.

Stack设计上存在的问题

根据JDK官方文档的介绍:

1
2
3
A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:
   Deque<Integer> stack = new ArrayDeque<Integer>();

Deque接口及其实现提供了LIFO堆栈的操作,它们提供了更完整和更一致的操作.所以应该优先使用这个接口,而不是Stack.比如ArrayDeque.

其实,JDK通过Vector来实现Stack这个设计是存在问题的.理由如下:

  1. Stack仅仅是为了使用Vector的几个方法,而其他大部分方法都没有使用,造成很多方法冗余,要知道Stack和Vector在设计理念上毫无关系啊;
  2. 鉴于1,Stack设计上的不严谨,Vector中有个方法public void add(int index, E element),它可以在栈中任意位置添加元素,这于Stack的设计理念相冲突;
  3. Stack大部分是增加和删除操作,很少查找元素,这很应该用链表去实现,而不是Vector的数组(效率受影响),这里也是很多人质疑Stack的地方;

参考文档