数据结构之栈

MyStack.java：
public class MyStack<E> extends MyVector<E> {


    /**
     * 压栈：在数组末尾添加元素
     * @param item
     * @return
     */
    public E push(E item) {
        addElement(item);
        return item;
    }


    /**
     * 出栈：在数组末尾删除元素
     * @return
     */
    public synchronized E pop() {
        E obj;
        int len = size();
        obj = peek();
        removeElementAt(len - 1);


        return obj;
    }


    /**
     * 查看栈顶元素，不删除
     * @return
     */
    public synchronized E peek() {
        int len = size();
        //如果数组为空，则抛出异常
        if (len == 0)
            throw new RuntimeException("空栈");
        return elementAt(len - 1);
    }
}


MyVector.java:
public class MyVector<E> implements List<E> {


    //扩容系数
    protected int capacityIncrement;


    //元素数组
    protected Object[] elementData;


    //数组中元素个数
    protected int elementCount;


    //修改次数
    protected transient int modCount = 0;


    //最大数组大小
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;


    /**
     * 指定初始容量和扩容系数
     * @param initialCapacity
     * @param capacityIncrement
     */
    public MyVector(int initialCapacity, int capacityIncrement) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("非法容量大小参数");
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }


    public MyVector(int initialCapacity) {
        this(initialCapacity, 0);
    }


    /**
     * ① 默认容量大小是10
     * ② 这里不同于ArrayList，它是在创建时就分配了容量为10的数组，但是ArrayList在第一次调用add时才生成一个容量为10数组。
     */
    public MyVector() {
        this(10);
    }
    /**
     * 添加元素：线程安全
     * @param obj
     */
    public synchronized void addElement(E obj) {
        modCount++;
        //扩容
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }


    /**
     * 判断是否需要扩容
     * @param minCapacity
     */
    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }


    /**
     * 动态扩容：
     * ① 扩容机制：如果指定了扩容系数capacityIncrement，就按照这个指定的系数扩大容量，扩大后容量为oldCapacity+capacityIncrement，
     *             如果没有指定就默认扩大到原来一倍。
     * @param minCapacity
     */
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        //如果指定了capacityIncrement，则容量大小为：oldCapacity + capacityIncrement
        //若未指定，则容量大小为：oldCapacity + oldCapacity
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }


    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)
            throw new OutOfMemoryError("数组越界");
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }


    /**
     * 返回数组大小
     * @return
     */
    public synchronized int size() {
        return elementCount;
    }


    /**
     * 返回指定索引位置元素
     * @param index
     * @return
     */
    public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException("下标越界异常");
        }


        return elementData(index);
    }


    E elementData(int index) {
        return (E) elementData[index];
    }


    /**
     * 删除指定索引位置元素
     * @param index
     */
    public synchronized void removeElementAt(int index) {
        modCount++;
        //先检查下标是否合法
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException("下标越界异常");
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException("下标越界异常");
        }


        //获取删除某所索引位置元素后续需要移动的元素个数
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--;
        //便于GC回收
        elementData[elementCount] = null;
    }
}

public class MyLinkedList<E> implements Deque<E> {


    transient int size = 0;


    //头结点
    transient Node<E> first;


    //尾节点
    transient Node<E> last;


    protected transient int modCount = 0;


    private static class Node<E>{
        private Node<E> prev;
        private E item;
        private Node<E> next;


        private Node(Node<E> prev,E item,Node<E> next){
            this.prev = prev;
            this.item = item;
            this.next = next;
        }
    }


    /**
     * 压栈：在链表头插入元素（表头相当于栈顶）
     * @param e
     */
    public void push(E e) {
        addFirst(e);
    }


    public void addFirst(E e) {
        linkFirst(e);
    }


    //将插入元素作为首节点
    private void linkFirst(E e) {
        final Node<E> f = first;
        //创建新加入节点为首节点
        final Node<E> newNode = new Node<E>(null, e, f);
        first = newNode;
        //如果是空链表，则尾节点也指向该创建的节点
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }


    /**
     * 出栈：删除链表首节点
     * @return
     */
    public E pop() {
        return removeFirst();
    }


    /**
     * 删除链表首节点，如果链表为空，会抛出异常
     * @return
     */
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }


    private E unlinkFirst(Node<E> f) {
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null;
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }
}