【集合】Stack 源码分析

曾经终败给现在 2022-12-19 00:49 198阅读 0赞

# 前言 #

Github：[https://github.com/yihonglei/jdk-source-code-reading][https_github.com_yihonglei_jdk-source-code-reading]（java-collection）

# 一 概述 #

Java 里面的 Stack 底层基于数组实现，叫**顺序栈**，栈也可以用链表实现，叫**链式栈**，是一种后进先出的容器。

# 二 实例 #

package com.jpeony.collection.stack;
    
    import java.util.Stack;
    
    /**
     * @author yihonglei
     */
    public class StackTest {
        public static void main(String[] args) {
            Stack<String> stack = new Stack<>();
    
            // 入栈
            stack.push("one");
            stack.push("two");
    
            // 出栈
            System.out.println(stack.pop());
        }
    }

**运行结果**

![20201104200237931.png][]

# 三 Stack 底层实现 #

**重点分析 push() 和 pop() 方法。**

## 类结构 ##

public class Stack<E> extends Vector<E> {
    	......
    }

从类的结构可以看到，Stack 继承了 Vector，Vector 底层基于数组实现，所以 Java 的 Stack 也是基于数组实现。

## 默认构造器 ##

/**
     * Creates an empty Stack.
     */
    public Stack() {
    }

创建一个空栈，看上去啥都没有？不急，Stack 继承了 Vector，初始化时会调用 Vector 构造器，创建一个10的默认数组，详情看 [Vector 源码分析][Vector]。

## Stack\#push() ##

public E push(E item) {
    	// 入栈
        addElement(item);
        // 返回入栈元素
        return item;
    }

添加的具体实现在Vector\#addElement()，添加元素，实现入栈操作：

public synchronized void addElement(E obj) {
    	// 容器操作次数加1
        modCount++;
        // 负责扩容判断，确保容器够量
        ensureCapacityHelper(elementCount + 1);
        // 往容器数组添加元素
        elementData[elementCount++] = obj;
    }

扩容，可以参考Vector实现。

## Stack\#pop() ##

public synchronized E pop() {
    	// 出栈元素
        E       obj;
        // 栈元素个数
        int     len = size();
        // 取出栈顶元素
        obj = peek();
        // 从栈顶移出元素，即数组的尾部元素
        removeElementAt(len - 1);
        // 返回出栈元素，完成出栈操作
        return obj;
    }

peek() 取栈顶元素。

public synchronized E peek() {
        int     len = size();
    
        if (len == 0)
            throw new EmptyStackException();
        // 数组最后元素下标，即栈顶元素的下标
        return elementAt(len - 1);
    }

elementAt() 根据数组最后元素下标，获取栈顶元素值。

public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }
    
        return elementData(index);
    }

#  四 总结 #

1、Java 栈基于数组实现，后进先出，基于 Vector 实现，通过 synchronized 实现线程安全，并发度低；

2、实际开发应用不算太多，但是栈这种数据结构在 jvm 里面方法的函数依赖的就是虚拟机栈和本地方法栈；

3、栈也常用于字符串匹配，表达式求值，浏览器的前进后退功能等成对处理的场景；

[https_github.com_yihonglei_jdk-source-code-reading]: https://github.com/yihonglei/jdk-source-code-reading
[20201104200237931.png]: /images/20221120/b4e7a27d9565490182f9595ea7e60a36.png
[Vector]: https://jpeony.blog.csdn.net/article/details/109426679