队列与栈三

栈也是一种常见的数据结构，栈的特点就是后进先出。

栈的数组实现

package com.lei.payment.java.base.algorithm.list.statck;

import com.lei.payment.java.base.algorithm.exception.AlgorithmException;
import com.lei.payment.java.base.algorithm.exception.ErrorCode4Algorithm;
import com.lei.payment.java.base.algorithm.list.AbstractList;

public class ArrayStack<T> extends AbstractList<T> {
    private Object[] stack;

    private int DEFAULT_STACK_SIZE = 32;

    private int size = 0;

    /**
     * 有参构造函数
     *
     * @param size size
     */
    public ArrayStack(int size) {
        if (size < 1) {
            throw new AlgorithmException(ErrorCode4Algorithm.INDEX_OUT_OF_RANGE);
        }
        this.stack = new Object[size];
        this.size = 0;
    }

    /**
     * 无参构造函数
     */
    public ArrayStack() {
        new ArrayStack<T>(DEFAULT_STACK_SIZE);
    }

    @Override
    public T pop() throws AlgorithmException {
        if (this.isEmpty()) {
            throw new AlgorithmException(ErrorCode4Algorithm.INDEX_OUT_OF_RANGE);
        }
        return (T) stack[this.size--];
    }

    @Override
    public void push(T t) throws AlgorithmException {
        if (stack.length == this.size) {
            resize(this.stack, this.size + DEFAULT_STACK_SIZE);
        }
        this.stack[this.size++] = t;
    }

    @Override
    public int size() throws AlgorithmException {
        return this.size;
    }

    @Override
    public T fist() throws AlgorithmException {
        if (this.isEmpty()) {
            throw new AlgorithmException(ErrorCode4Algorithm.INDEX_OUT_OF_RANGE);
        }
        return (T) this.stack[this.size - 1];
    }

    @Override
    public T last() throws AlgorithmException {
        if (this.isEmpty()) {
            throw new AlgorithmException(ErrorCode4Algorithm.INDEX_OUT_OF_RANGE);
        }
        return (T) this.stack[0];
    }

    @Override
    public boolean isEmpty() throws AlgorithmException {
        return this.size <= 0;
    }

    /**
     * resize stack
     *
     * @param oldStack old stack
     * @param newSize  new size
     */
    private void resize(Object[] oldStack, int newSize) {
        Object[] newStack = new Object[newSize];
        for (int i = 0; i < this.size; i++) {
            newStack[i] = oldStack[i];
        }
        this.stack = newStack;
    }
}

栈的链表实现

package com.lei.payment.java.base.algorithm.list.statck;

import com.lei.payment.java.base.algorithm.exception.AlgorithmException;
import com.lei.payment.java.base.algorithm.exception.ErrorCode4Algorithm;
import com.lei.payment.java.base.algorithm.list.AbstractList;
import com.lei.payment.java.base.algorithm.node.ListNode;

public class LinkedStack<T> extends AbstractList<T> {
    /**
     * 栈顶
     */
    ListNode<T> head;

    /**
     * 栈底
     */
    ListNode<T> end;

    /**
     * 栈大小
     */
    private int size;

    /**
     * 构造函数
     */
    public LinkedStack() {
        this.init();
    }

    /**
     * init stack
     */
    private void init() {
        this.head = new ListNode();
        this.head.setNext(null);
        this.head.setVal(null);
        this.end = this.head;
        this.size = 0;
    }

    @Override
    public T pop() throws AlgorithmException {
        if (this.isEmpty()) {
            throw new AlgorithmException(ErrorCode4Algorithm.INDEX_OUT_OF_RANGE);
        }
        ListNode<T> currentNode = this.end;
        while (currentNode.getNext() != this.head) {
            currentNode = currentNode.getNext();
        }
        T t = this.head.getVal();
        this.head = currentNode;
        this.size--;
        return t;
    }

    @Override
    public void push(T t) throws AlgorithmException {
        ListNode<T> newNode = new ListNode<T>();
        newNode.setVal(t);
        newNode.setNext(null);
        this.head.setNext(newNode);
        this.head = this.head.getNext();
        this.size++;
    }

    @Override
    public int size() throws AlgorithmException {
        return this.size;
    }

    @Override
    public T fist() throws AlgorithmException {
        if (this.isEmpty()) {
            throw new AlgorithmException(ErrorCode4Algorithm.INDEX_OUT_OF_RANGE);
        }
        return this.head.getVal();
    }

    @Override
    public T last() throws AlgorithmException {
        if (this.isEmpty()) {
            throw new AlgorithmException(ErrorCode4Algorithm.INDEX_OUT_OF_RANGE);
        }
        return this.end.getVal();
    }

    @Override
    public boolean isEmpty() throws AlgorithmException {
        return this.head == this.end;
    }
}