Stack源码分析（JDK1.8）

这篇文章，实际上不应该算是源码分析，这是在源码的思想基础上自己实现的Stack.但是方法与思想是一致。这里先介绍一下栈的特点：先进后出，后进先出。

  1. Stack变量以及常量分析
        /**
     * 存储数据
     */
    Object[] elementData;
    /**
     * 数据大小：这样elementData[0]可以作为栈底。elementData[elementCount-1]可以作为栈顶
     */
    int elementCount;
    /**
     * 容量增长系数
     */
    int capacityIncrement;
    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

这应该不算是一种源码分析，而是参照源码的思想实现的一种栈。

  1. Stack的常见创建方式
    2.1 空构造函数
public SimpleStack() {
        this(10, 0);
}

2.2 带参数的构造函数

public SimpleStack(int initialCapacity, int capacityIncrement){
        if (initialCapacity < 0 ) {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
        this.capacityIncrement = capacityIncrement;
        this.elementData = new Object[initialCapacity];
    }

从无参构造函数知道：无参构造函数默认数组长度为10.

  1. 集合扩容操作
/************************************************************扩容操作 *********************************************************************/
    /**
     * 扩容
     */
    public synchronized void ensureCapacityHelper(int minCapacity){
        //什么时候需要扩容呢？
        if (minCapacity > elementData.length) {
            grow(minCapacity);
        }
    }
    /**
     * 如何扩容
     * @param minCapacity
     */
    public synchronized void grow(int minCapacity){
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);//扩容为原来的一倍
        if (newCapacity < minCapacity ) {
            newCapacity = minCapacity;//如果扩容之后的大小还不足以添加元素，则扩容为最大的那个
        }
        if (newCapacity > MAX_ARRAY_SIZE) {
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    public synchronized int hugeCapacity(int minCapacity){
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        }
        return minCapacity > MAX_ARRAY_SIZE ?Integer.MAX_VALUE:MAX_ARRAY_SIZE;
    }

这里我们可以知道，其实Stack扩容就是增加了原来数组长度的一倍。

  1. 集合操作：增加元素
/******************************************************************基本操作***********************************************************************/
    /**
     * 添加元素
     * @param e
     */
    public synchronized void addElement(E e){
        //第一步：扩容
        ensureCapacityHelper(elementCount+1);
        //第二步：添加
        elementData[elementCount++] = e;//基于数组的，所以是线性顺序的。
    }
    /**
     * 取出元素
     * @return
     */
    public E getElement(){
        if (elementData == null) {
            return null;
        }
        
        int head = elementCount -1;
        E obj = elementData(head);
        //需要删除该位置元素
        removeElementAt(head);
        return obj;
    }
    /**
     * 获取指定位置的元素
     * @param index
     * @return
     */
    @SuppressWarnings("unchecked")
    public E elementData(int index){
        return (E) elementData[index];
    }
    /**
     * 删除指定位置的元素
     * @param index
     * @return
     */
    public synchronized E removeElementAt(int index){
        if (index < 0 ) {
            throw new ArrayIndexOutOfBoundsException();
        }
        E oldElement = elementData(index);
        int j = elementCount - index -1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount --;
        return oldElement;
    }
  1. 完整源码
package com.wang.list;

import java.util.AbstractList;
import java.util.Arrays;
import java.util.List;
import java.util.RandomAccess;

/**
 * 栈：入栈，出栈。先进后出（字符串反转:'i love you'）
 * @author Administrator
 *
 */
public class SimpleStack<E> extends AbstractList<E>
                implements List<E>, RandomAccess, Cloneable, java.io.Serializable{

    private static final long serialVersionUID = 5960789704116302371L;
    
    /***************************************************************变量,常量，构造器*********************************************************************/
    /**
     * 存储数据
     */
    Object[] elementData;
    /**
     * 数据大小：这样elementData[0]可以作为栈底。elementData[elementCount-1]可以作为栈顶
     */
    int elementCount;
    /**
     * 容量增长系数
     */
    int capacityIncrement;
    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    public SimpleStack(int initialCapacity, int capacityIncrement){
        if (initialCapacity < 0 ) {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
        this.capacityIncrement = capacityIncrement;
        this.elementData = new Object[initialCapacity];
    }
    
    public SimpleStack() {
        this(10, 0);
    }
    /************************************************************扩容操作 *********************************************************************/
    /**
     * 扩容
     */
    public synchronized void ensureCapacityHelper(int minCapacity){
        //什么时候需要扩容呢？
        if (minCapacity > elementData.length) {
            grow(minCapacity);
        }
    }
    /**
     * 如何扩容
     * @param minCapacity
     */
    public synchronized void grow(int minCapacity){
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);//扩容为原来的一倍
        if (newCapacity < minCapacity ) {
            newCapacity = minCapacity;//如果扩容之后的大小还不足以添加元素，则扩容为最大的那个
        }
        if (newCapacity > MAX_ARRAY_SIZE) {
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    public synchronized int hugeCapacity(int minCapacity){
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        }
        return minCapacity > MAX_ARRAY_SIZE ?Integer.MAX_VALUE:MAX_ARRAY_SIZE;
    }
    /******************************************************************基本操作***********************************************************************/
    /**
     * 添加元素
     * @param e
     */
    public synchronized void addElement(E e){
        //第一步：扩容
        ensureCapacityHelper(elementCount+1);
        //第二步：添加
        elementData[elementCount++] = e;//基于数组的，所以是线性顺序的。
    }
    /**
     * 取出元素
     * @return
     */
    public E getElement(){
        if (elementData == null) {
            return null;
        }
        
        int head = elementCount -1;
        E obj = elementData(head);
        //需要删除该位置元素
        removeElementAt(head);
        return obj;
    }
    /**
     * 获取指定位置的元素
     * @param index
     * @return
     */
    @SuppressWarnings("unchecked")
    public E elementData(int index){
        return (E) elementData[index];
    }
    /**
     * 删除指定位置的元素
     * @param index
     * @return
     */
    public synchronized E removeElementAt(int index){
        if (index < 0 ) {
            throw new ArrayIndexOutOfBoundsException();
        }
        E oldElement = elementData(index);
        int j = elementCount - index -1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount --;
        return oldElement;
    }
    
    /*******************************************************************未实现**********************************************************/
    @Override
    public E get(int index) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public E set(int index, E element) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public E remove(int index) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public int size() {
        // TODO Auto-generated method stub
        return 0;
    }
    
    public void print(){
        for (int i = 0; i < elementData.length; i++) {
            System.out.print(elementData[i]);
            System.out.print(",");
        }
    }
    
    
    public static void main(String[] args){
        //逆序输出
        String testStr = "hello word!";
        char[] testChars = testStr.toCharArray();
        SimpleStack<Character> stack = new SimpleStack<Character>(); 
        for (int i = 0; i < testChars.length; i++) {
            stack.addElement(testChars[i]);
        }
        
        stack.print();
        System.out.println();
        
        for (int i = 0; i < testChars.length; i++) {
            System.out.print(stack.getElement()+",");
        }
        
    }
    
}
  1. 总结

6.1 特点

  • 基于数组实现的。
  • 有序集合，而且允许null值存在。
  • 线程安全，对于具有修改属性的方法都加了synchronized关键字。
    其实，分析完ArrayList再来分析Stack就简单多了，因为Stack的实现很大程度借鉴了ArrayList的思想，包括底层数组实现，都需要扩容等等。那下面我们来详细来分析一下。

6.2 区别ArrayList与Stack

  • 构造方法相似（无参构造，有参构造（数组大小））
    无参构造时，Stack默认数组大小为10。ArrayList默认为空数组。
  • 底层都是数组来实现
    /**
     * 存储数据
     */
    Object[] elementData;
  • 添加操作都需要扩容处理
    6.1.1 判断是否需要扩容方法不一致
    由于在无参构造的时候，我们默认ArrayList数组大小为0，那么扩容的时候首先需要判断一下是否为空数组，然后再考虑什么情况下需要扩容
public void ensureCapacityInternal(int minCapacity) {
        // 解决第一个问题：什么时候需要扩容?如果为空数组，默认数组长度为10
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        if (minCapacity > elementData.length) {
            // 如果扩容大于新建数组的长度（数组的长度，非集合中元素的大小），这个时候需要扩容。
            grow(minCapacity);
        }
    }

而Stack默认数组大小为10，所以扩容开始时需要判断什么情况下需要扩容。

    /**
     * 扩容
     */
    public synchronized void ensureCapacityHelper(int minCapacity){
        //什么时候需要扩容呢？
        if (minCapacity > elementData.length) {
            grow(minCapacity);
        }
    }

6.1.2 扩容大小不一致
每一次扩容大小是不一致的，ArrayList每次扩容为原来的一半，就是说新扩容后的大小是原来的1.5倍。而Stack扩容之后新扩容后的大小是原来大小的2倍。
ArrayList扩容代码如下：

/**
     * 实际扩容操作
     * 
     * @param minCapacity
     */
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length; // 原来数组长度
        int newCapacity = oldCapacity + (oldCapacity >> 1);// 扩容新数组大小，为什么选择扩容原来的1.5倍？难道是这是为了节省空间最佳方案。
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity; // 从这里可以看出来，实际扩容大小，有可能不止1.5倍大小。
        }
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            // 如果MAX_ARRAY_SIZE大小都不能满足扩容之后的新容量大小，则需要进一步扩容
            newCapacity = hugeCapacity(minCapacity);
        }

        elementData = Arrays.copyOf(elementData, newCapacity);// 最后一步最重要的是，把原来数组复制到扩容之后的数组中。这里需要使用到jdk本地库，
                                                                // 不可避免需要IO操作，如果频繁的扩容，会影响ArrayList的性能，因此如果我们知道list大小，可以直接构造出指定容量的数组
    }

Stack扩容代码如下：

public synchronized void grow(int minCapacity){
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);//扩容为原来的一倍
        if (newCapacity < minCapacity ) {
            newCapacity = minCapacity;//如果扩容之后的大小还不足以添加元素，则扩容为最大的那个
        }
        if (newCapacity > MAX_ARRAY_SIZE) {
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
  • Stack是线程安全的，而ArrayList是非线程安全的，多线程环境下容易引起问题。但是Stack由于有修改操作方法都添加了Syschronized关键字，因此执行效率比较低。
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 219,039评论 6赞 508
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 93,426评论 3赞 395
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 165,417评论 0赞 356
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,868评论 1赞 295
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,892评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,692评论 1赞 305
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,416评论 3赞 419
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,326评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,782评论 1赞 316
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,957评论 3赞 337
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,102评论 1赞 350
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,790评论 5赞 346
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,442评论 3赞 331
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,996评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,113评论 1赞 272
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,332评论 3赞 373
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 45,044评论 2赞 355