栈

计算机科学中，stack是一种线性的数据结构，只能在其一端添加数据和移除数据。习惯来说，这一端称之为栈顶，另一端不能操作数据的称之为栈底，就如同生活中的一摞书

LIFO，后进先出

接口

栈可以使用多种方式实现，链表或者数组

public interface Stack<T> {

    /**
     * 向栈顶压入元素
     */
    boolean push(T t);

    /**
     * 从栈顶顶出元素
     */
    T pop();

    /**
     * 返回栈顶元素不移除
     */
    T peek();

    /**
     * 是否为空
     */
    boolean isEmpty();

    /**
     * 是否已满
     */
    boolean isFull();

    class Node<T> {

        Node<T> next;
        T value;

        public Node(T value, Node<T> next) {
            this.next = next;
            this.value = value;
        }

        public static <T> Node<T> of(T... t) {
            Node<T> res = new Node<>(null, null);
            for (T node : t) {
                res = new Node<>(node, res.next);
            }
            return res.next;
        }
    }

}

链表实现（单向）

/**
 * 单向链表实现栈
 */
public class LinkedListStack<T> implements Stack<T> {

    private int size;

    private int capacity;

    private Node<T> head = new Node(null, null);

    public LinkedListStack(int capacity) {
        this.capacity = capacity;
    }

    @Override
    public boolean push(T t) {
        if (isFull()) {
            return false;
        }
        size++;
        head.next = new Node<>(t, head.next);
        return true;
    }

    @Override
    public T pop() {
        if (isEmpty()) {
            return null;
        }
        Node<T> node = head.next;
        size--;
        head.next = node.next;
        return node.value;
    }

    @Override
    public T peek() {
        if (isFull()) {
            return null;
        }
        Node<T> node = head.next;
        size--;
        return node.value;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

}

数组实现

刚开始栈顶和栈尾的指针都相同，随着放入元素，栈顶的执行向下偏移，当超过容量放入失败，获取内容也是从栈顶位置依次向下获取

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

    private int capacity;
    //栈顶指针
    private int top;
    private T[] arrs;

    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.arrs = (T[]) new Object[capacity];
    }

    @Override
    public boolean push(T t) {
        if (isFull()) {
            return false;
        }
        arrs[top++] = t;
        return true;
    }

    @Override
    public T pop() {
        if (isEmpty()) {
            return null;
        }
        return arrs[--top];
    }

    @Override
    public T peek() {
        return arrs[top];
    }

    @Override
    public boolean isEmpty() {
        return top == 0;
    }

    @Override
    public boolean isFull() {
        return top == capacity;
    }

}