栈的原理与特性

栈其实是一种特殊的线性表，因为栈只限定了一头进行增加和删除，其实这种应用场景还是蛮广的，比如递归操作，运算符匹配，只要是符合先进后出的队列都可以用栈来表达。因为限定了只能是一头进行增删，如果用顺序存储来实现，也减少了删除结点移动的带来的开销，所以栈如何能确定大小，使用顺序存储来实现也是高效的。

因为栈是一种特殊的线性表，所以跟线性表一样都可以使用顺序存储和链式存储来实现。

栈接口

/** * 自定义栈接口定义 **/
public interface Stack<T> {

    /** * 向栈中添加元素 */
    void push(T e);

    /** * 从栈中删除元素 */
    T pop();

    /** * 获取栈顶元素 * * @return */
    T peek();

    /** * 获取栈中元素个数 * * @return */
    int getSize();

    /** * 判断栈中是否为空 * * @return */
    boolean isEmpty();

    /** * 判断栈是否满 * @return */
    boolean isFull();

    /** * 销毁栈 */
    void stackDestroy();
}

顺序存储实现方式

package com.lineardatastructure.stack;

public class ArrayStack<T> implements Stack<T> {

    private int stackSize; //栈最大容量,自动扩容
    private int base = -1; //栈底指针
    private int top; //栈顶指针
    private int popNum;//弹栈次数
    private final int CLEARTRASH = 1000; //垃圾个数

    //构建一个栈
    private Object[] arrayStack;

    //初始化栈
    public ArrayStack(Object... objects) {
        this.arrayStack = objects;
        this.stackSize = objects.length;

        this.top = objects.length - 1;
    }
    public ArrayStack(int stackSize) {
        this.stackSize = stackSize;
        this.top = -1;
        this.arrayStack = new Object[stackSize];
    }

    @Override
    public synchronized void push(T t) {
        if (!isFull()) {
            this.arrayStack[++top] = t;
        } else {
            //栈已满-进行扩容
            this.stackSize = this.stackSize + (int) (this.stackSize * 0.75 + 1);
            Object[] target = new Object[this.stackSize];
            //java最快数组copy方式
            System.arraycopy(this.arrayStack, 0, target, 0, this.arrayStack.length);
            this.arrayStack = target;//将原数组替换
            this.arrayStack[++top] = t;
        }
    }

    @Override
    public synchronized T pop() {
        if (!isEmpty()) {
            T t = (T) this.arrayStack[top--];
            if (popNum == CLEARTRASH) {
                //清除多余空间的内容
                this.stackSize = this.top + (int) (this.top * 0.75 + 1);
                if (stackSize != -1) {
                    Object[] target = new Object[stackSize];
                    System.arraycopy(this.arrayStack, 0, target, 0, top + 1);
                    this.arrayStack = target;
                }
                popNum = 0;
            }
            popNum++;
            return t;
        }
        System.out.println("栈为空，返回null");
        return null;
    }

    @Override
    public synchronized T peek() {
        if (!isEmpty()) {
            return (T) this.arrayStack[top];
        } else {
            System.out.println("栈为空，返回null");
            return null;
        }
    }

    @Override
    public synchronized int getSize() {
        return top - base;
    }

    //判断栈是否为空
    @Override
    public synchronized boolean isEmpty() {
        return base == top;
    }

    //判断栈是否满了
    @Override
    public synchronized boolean isFull() {
        return (top - base) >= stackSize;
    }

    @Override
    public synchronized void stackDestroy() {
        this.arrayStack = null;
        top = -1;
    }
}

链式存储实现方式

package com.lineardatastructure.stack;

public class LinkedStack<T> implements Stack<T> {
    int currLength; //栈大小
    StackNode top; //栈顶指针，也是头结点
   private class StackNode{
        T nodeData; //结点值
        StackNode next; //指向下一个结点的引用
    }
    public LinkedStack() {
        currLength = 0;
        top = new StackNode();
    }

    @Override
    public synchronized void push(T e) {
        if (isEmpty()) {
            //说明这是一个空栈
            this.top.nodeData = e;

        } else {
            //将当前节点进行压栈,原来节点放入当前节点的下一个节点
            StackNode insertNode = new StackNode();
            insertNode.nodeData = e;
            insertNode.next = top;
            top = insertNode;
        }
        //列表深度
        currLength++;
    }

    @Override
    public synchronized T pop() {
        if (isEmpty()){
            return null;
        } else{
            if (top!=null) {
                //获取当前节点值
                T returnData = top.nodeData;
                //将下一个节点切换到顶节点
                top = top.next;
                //节点深度减少
                currLength--;
                return returnData;
            }
        }
        return null;
    }

    @Override
    public synchronized T peek() {
        return  this.top.nodeData;
    }

    @Override
    public synchronized int getSize() {
        return this.currLength;
    }

    @Override
    public synchronized boolean isEmpty() {
        return this.currLength==0;
    }

    @Override
    public synchronized boolean isFull() {
        return false;
    }

    @Override
    public synchronized void stackDestroy() {
        this.top.nodeData=null;
        this.top.next=null;
        this.top=null;
        this.currLength=0;
    }
}