Java源码阅读Stack

Stack（栈）实现了一个后进先出（LIFO）的数据结构。该类继承了Vector类，是通过调用父类Vector的方法实现基本操作的。

Stack共有以下五个操作：

put：将元素压入栈顶。

pop：弹出栈顶元素（返回栈顶元素，并删除）。

peek：取栈顶元素（不删除）。

empty：判断栈是否为空。

search：搜索一个元素是否在栈里，并返回其到栈顶的距离。

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

    public Stack() {

    }

    public E push(E item) {

        addElement(item);

        return item;

    }

    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;

    }

    public synchronized int search(Object o) {

        int i = lastIndexOf(o);

        if (i >= 0) {

            return size() - i;

        }

        return -1;

    }

    /** use serialVersionUID from JDK 1.0.2 for interoperability */

    private static final long serialVersionUID = 1224463164541339165L;

}

在之前源码阅读中我们知道vector是通过数组实现的。这里Stack又是通过Vector实现的，接下来我们挨个看其方法的实现。首先明确一点，stack是线程安全的。

（1）put

put方法并没有被synchronized修饰，因为该方法里面只有一条语句，调用Vector的addElement(item)方法，意思是在数组末尾插入一个元素，而addElement是被synchronized修饰的，所以put方法也是线程安全的。

（2）peek

首先获取数组的size，若为0，则报EmptyStackException异常。然后返回数组的最后一个元素。

（3）pop

先通过peek获取栈顶元素（数组最后一个元素），然后调用removeElementAt方法删除栈顶元素，最后返回之前获取的栈顶元素。

（4）search

通过lastIndexOf方法从后往前遍历找到匹配元素并获取所在位置的索引号i，然后通过size() - i返回其深度（到栈顶的距离）。若没有找到则返回-1。

总结

其实栈这种数据结构可以简单的通过一个数组进行模拟。

下面是我自己用1个数组实现的可扩容的栈MyStack

package com.ouym.test;

import java.util.Arrays;

import java.util.EmptyStackException;

public class MyStack<E> {

    private Object[] elementData;

    private int elementCount; //表示当前栈存放的数据量

    public MyStack() {

        this(10);

    }

    public MyStack(int initialCapacity) {

        if (initialCapacity < 0)

            throw new IllegalArgumentException("Illegal Capacity:"+initialCapacity);

        elementData = new Object[initialCapacity];

    }

    //扩容栈，扩容方式：新容量=旧容量*2

    private void grow() {

        int capacity = elementData.length;

        capacity = capacity << 1;

        if (capacity < 0) {

            throw new OutOfMemoryError();

        }

        elementData = Arrays.copyOf(elementData, capacity);

    }

    public E put(E item) {

        if (elementCount == elementData.length) {

            grow();

        }

        elementData[elementCount++] = item;

        return item;

    }

    @SuppressWarnings("unchecked")

    public E peek() {

        if (empty()) {

            throw new EmptyStackException();

        }

        return (E) elementData[elementCount - 1];

    }

    public E pop() {

        E item = peek();

        elementData[elementCount--] = null;

        return item;

    }

    public boolean empty() {

        return elementCount == 0;

    }

    public int size(){

        return elementCount;

    }

    public int search(E item) {

        if (item == null) {

            for (int i = elementCount - 1; i >= 0; i--)

                if (elementData[i] == null)

                    return i;

        } else {

            for (int i = elementCount - 1; i >= 0; i--) {

                if (item.equals(elementData[i])) {

                    return elementCount - i;

                }

            }

        }

        return -1;

    }

}

--------------------THE END--------------------

巴特西

Java源码阅读Stack

最新文章

热门文章