java collection [13] - a wave of Stack source code analysis


Collection source code analysis series: Java collection source code analysis

The vector, ArrayList and LinkedList have been analyzed. I wanted to start Map, but I looked at the following interface design framework diagram: the whole interface framework relationship is as follows (from Baidu Encyclopedia):

It turns out that there is another fish that has slipped through the net. The Stack is hung under the Vector. We have analyzed the Vector before. By the way, analyze the Stack. 2022 without writing:

Stack introduction

Stack is a kind of data structure, which is not unique to Java. It is embodied in the stack class in Java. Its essence is first in and last out. It is like a bucket, which can only be continuously placed on it. When it is taken out, it can only continuously take out the top data. If you want to take out the underlying data, you can do it only when the above data is taken out. Of course, if there is such a demand, we will generally use two-way queues.

The following is a demonstration of stack features:

Stack inherits from Vector in Java. This is version 1.8. It shares the underlying data structure of Vector. The underlying data structure is implemented using arrays. It has the following characteristics:

  • First in, last out (` FILO)
  • It inherits from Vector and is also implemented based on array
  • Since almost all vectors are used, and Vector operations are thread safe, Stack operations are also thread safe.

Class definition source code:

class Stack<E> extends Vector<E> {

Member variables have only one serialized variable:

    private static final long serialVersionUID = 1224463164541339165L;

Method interpretation

Stack doesn't have many methods of its own, almost all of which are inherited from Vector. We can take a look at the five methods expanded by stack:

  • E push(E item): stack pressing
  • synchronized E pop(): out of stack
  • synchronized E peek(): get stack top element
  • boolean empty(): judge whether the stack is empty
  • int search(Object o): search the index position of an object in the stack

push method

At the bottom, the addElement() method is actually called, which is the method of Vector:

    public E push(E item) {

        return item;

We have analyzed the source code of Vecor earlier. If you are interested, please refer to:

addElement is thread safe. At the bottom, it actually adds an element to the back of the array, but it helps us ensure the capacity. If the capacity is insufficient, it will trigger the automatic capacity expansion mechanism.

    public synchronized void addElement(E obj) {
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;

pop method

The bottom layer is to call the peek() method to get the top element of the stack, and then call the removeElementAt () method to remove the top element of the stack to achieve the out of stack effect.

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

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

        return obj;

removeElementAt(int index) is also a Vector method. It is decorated with synchronized and thread safe. Since the last element of the array is removed, element replication will not be triggered here, that is, system arraycopy(elementData, index + 1, elementData, index, j);:

    public synchronized void removeElementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        elementData[elementCount] = null; /* to let gc do its work */

peek method

Get the top element of the stack. First get the size of the array, and then call E elementAt(int index) of Vector to get the elements of the index:

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

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

The source code of E elementAt(int index) is as follows. The logic is relatively simple, and only the judgment of array out of bounds:

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

        return elementData(index);

empty method

It is mainly used to judge whether there are elements in the element stack. It mainly calls the size() method:

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

The size() method is also a Vector method, and the returned value is also a class variable. The number of elements:

    public synchronized int size() {
        return elementCount;

search method

This method is mainly used to query the index of an element. If there are multiple elements, the index of the last element will be returned:

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

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

Using synchronized decoration is also thread safe. Why do you need this method?

We know that the stack is first in first out. If you need to find the position of an element in it, you need to take it out one by one and then judge it, which is too troublesome. The bottom layer uses array for storage. You can directly use this feature to quickly find the index position of the element.

So far, looking back, do you wonder if there is no data in the ` Stack, but it is constantly operating the data, thanks to the data structure of Vector:

        // Underlying array
    protected Object[] elementData;

    // Number of elements
    protected int elementCount;

The bottom layer uses an array to save the number of elements. In fact, the operation of elements is just to continuously insert elements into the array or take out the last element.


stack inherits Vector, so it is thread safe. The bottom layer uses array to save data, and most API s use Vector to save data. Its most important attribute is first in first out. As for array expansion, the expansion logic in Vector is used.

If we implement it ourselves, the bottom layer does not necessarily use arrays. Using linked lists can also achieve the same functions, but there are the same parts in the whole set source code system, which is a good choice.

[about the author]:
Qin Huai, the official account of Qin Huai grocery store, author's personal website: , the road of technology is not for a while, with high mountains and long rivers. Even if it is slow, it will not stop.

Sword finger Offer all questions PDF

Open source programming notes

Keywords: Java source code

Added by masalastican on Mon, 10 Jan 2022 02:44:46 +0200