How did JDK implement the stack?

This article comes from the public number: Java Chinese Community Author: Lei ge

The previous article, "Motion Map Demonstration: Two Ways to Implement the Hand Stack!" W e use arrays and linked lists to implement custom stack structures, so how do we officially implement stacks in JDK? Let's take a look.

Before this officially begins, explain the meaning of the word "stack" to everyone, because there have been some doubts about the word before.

Stack translates as Chinese means stack, but in order to be able to distinguish it from Heap we generally refer to Stack simply as stack. So when stacks are connected together, it is possible to represent Stack and when there is a semicolon in the middle of Stacks, Heap and Stack stacks are represented, as shown in the following image:

The implementation of the JDK stack

The conversation is on the right track, so let's look at how the stack is implemented in JDK.

In JDK, the implementation class of the stack is Stack and its inheritance relationship is shown in the following diagram:

Stack contains methods as follows:

The most important of these methods are:

• push:in-stack method (add data);
• pop: out of the stack and return the current element (remove the data);
• peek: Query the top element of the stack.

Stack implements the source code as follows:

public class Stack extends Vector {
    /**
     * 创建一个空栈
     */
    public Stack() {
    }


    /**
     * 入栈方法，调用的是 Vector#addElement 的添加方法
     */
    public E push(E item) {
        addElement(item);
        return item;
    }


    /**
     * 出栈并返回当前元素，调用的是 Vector#removeElementAt 的移除元素方法
     */
    public synchronized E pop() {
        E       obj; // 返回当前要移除的栈顶元素信息
        int     len = size();
        obj = peek(); // 查询当前栈顶元素
        removeElementAt(len - 1); // 移除栈顶元素
        return obj;
    }


    /**
     * 查询栈顶元素，调用 Vector#elementAt 的查询方法
     */
    public synchronized E peek() {
        int     len = size(); // 查询当前栈的长度
        if (len == 0) // 如果为空栈，直接抛出异常
            throw new EmptyStackException();
        return elementAt(len - 1); // 查询栈顶元素的信息
    }


    /**
     * 判断栈是否为空
     */
    public boolean empty() {
        return size() == 0;
    }
    // 忽略其他方法...
}

As can be seen from the source above, the core methods in Stack call the methods in the parent Vector Vector and the vector class's core source code:

public class Vector
    extends AbstractList
    implements List, RandomAccess, Cloneable, java.io.Serializable
{
 protected Object[] elementData; // 存储数据的容器
    protected int elementCount; // 存储数据的容量值

    
    /**
     * 添加数据
     */
    public synchronized void addElement(E obj) {
        modCount++; // 统计容器被更改的参数
        ensureCapacityHelper(elementCount + 1); // 确认容器大小，如果容量超出则进行扩容
        elementData[elementCount++] = obj; // 将数据存储到数组
    }

    
    /**
     * 移除元素（根据下标移除）
     */
    public synchronized void removeElementAt(int index) {
        modCount++; // 统计容器被更改的参数
        // 数据正确性效验
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) { // 删除的不是最后一个元素
         // 把删除元素之后的所有元素往前移动
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--; // 数组容量 -1
        elementData[elementCount] = null; // 将末尾的元素赋值为 null（删除尾部元素）
    }

    
    /**
     * 查询元素（根据下标）
     */
 public synchronized E elementAt(int index) {
     // 安全性验证
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }
        // 根据下标返回数组中的元素
        return elementData(index);
    }
    // 忽略其他方法...
}

The most difficult thing to understand about the above source code is System#arraycopy method, which actually moves the subsequent elements of the deleted element (non-end element) forward in turn, such as the following code:

Object[] elementData = {"Java", "Hello", "world", "JDK", "JRE"};
int index = 3;
int j = elementData.length - index - 1;
System.arraycopy(elementData, index + 1, elementData, index, j);
//  System.arraycopy(elementData, 4, elementData, 3, 1);
System.out.println(Arrays.toString(elementData));

The result of its operation is:

[Java, Hello, world, JRE, JRE]

That is, when we want to remove an element labeled 3, we need to move the element after 3 forward, so the value of the array changes from {"Java", "Hello", "world", "JDK", "JRE"} to [Java, Hello, world, JRE, JRE] and finally we just need to remove the tail element to achieve the function of removing non-end elements from the array.

brief summary

As can be seen from the above source code, the stack in the JDK is also implemented through the array of physical structures, we operate the physical array to achieve the function of the logical structure stack, see the physical structure and logical structure for details in the Motion Picture Demonstration: two implementation methods of the hand-to-hand stack! 》 。

The app of the stack

After the previous study we have a certain understanding of the stack, that stack in our ordinary work what applications? Next we'll have a look.

Browser fallback

The features of the stack are LIFO (Last In Out First, LIFO), so the browser's fallback capabilities can be implemented with this feature, as shown in the following image:

The function call stack

One of the most classic applications of stacks in a program is the function call stack (or method call stack), such as the operating system allocating a separate piece of memory space to each thread, which is organized into a "stack" structure that stores temporary variables when a function is called. E ach time a function is entered, the temporary variable is put into the stack as a stack frame, and when the called function is executed and returned, the corresponding stack frame for the function is taken out of the stack. To give you a better understanding, let's take a look at how this code is executed.

int main() {
   int a = 1; 
   int ret = 0;
   int res = 0;
   ret = add(3, 5);
   res = a + ret;
   System.out.println(res);
   reuturn 0;
}
int add(int x, int y) {
   int sum = 0;
   sum = x + y;
   return sum;
}

As we can see from the code, the main() function calls the add() function, gets the result of the calculation, adds to the temporary variable a and finally prints the value of the res T o give you a clear picture of the operation of stacking out and into the stack of functions corresponding to this process, I drew a diagram. The figure shows how the function calls the stack when executing to the add() function.

The complexity of the stack

Complexity is divided into two dimensions:

• Time dimension: refers to the time it takes to execute the current algorithm, which we usually describe as "time complexity";
• Spatial dimension: Refers to how much memory space is required to execute the current algorithm, which we usually describe as "space complexity".

Both of these complexities are expressed in large O notations, such as the following code:

int[] arr = {1, 2, 3, 4};
for (int i = 0; i < arr.length; i++) {
    System.out.println(i);
}

In the case of a large O notation, its time complexity is O(n), whereas the time complexity of the following code is O (1):

int[] arr = {1, 2, 3, 4};
System.out.println(arr[0]); // 通过下标获取元素

So if you use a large O notation to represent the complexity of the stack, the result is as follows:

That's W3Cschool编程狮 says about how JDK actually implements the stack? Related to the introduction, I hope to help you.