栈的初步介绍

栈（stack）又名堆栈，它是一种运算受限的线性表。其只允许在固定的⼀端进行插⼊和删除元素操作

这一端被称为栈顶。相对地，把另一端称为栈底

压栈：栈的插⼊入操作叫做进栈/压栈/入栈，⼊数据在栈顶

它是把新进入的元素放到栈顶元素的上面，使之成为新的栈顶元素

出栈：栈的删除操作叫做出栈。出数据也在栈顶

从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素

其实，我们可以把栈操作理解为我们以前上学的时候，给老师交作业这一简单过程：

有的同学把作业先交上去，他的作业就放在一摞本子的下面，在老师批阅后，比较晚发下来

而有的同学，作业交的迟了点，把他的作业本放在前面交过同学的作业本上面，老师批阅后，却是先发下来

即“先交后发，后交先发” —— LIFO —— Last In First Out

为什么要使用“栈”？

相⽐数组和链表，“栈”这一操作有很大的限制，即，只允许在⼀端插入和删除数据

既然有限制，那我们为什么还要去使用“栈”这一操作呢？

事实上，从功能上来说，数组或链表确实可以替代栈，但你要知道，特定的数据结构是对特定场景的抽象

⽽且，数组或链表暴露了太多的操作接口，操作上的确灵活⾃由，但使⽤时就难免不可控，自然也更容易出错

所以，当某个数据集合只涉及在⼀端插入和删除数据，并且满足后进先出、先进后出（LIFO）的特性，

我们就应该⾸选“栈”这种数据结构

下面给出“栈”的两种实现方式 ——

// 基于链表实现栈 —— 链式栈

public class LinkedStack<T> implements Stack<T> {
    // 栈顶元素
    private Node top;
    private int currentSize;
    private class Node {
        private T t;
        private Node next;
        public Node(T t, Node next) {
            this.t = t;
            this.next = next;
        }
    }

    @Override
    public boolean push(T t) {
        // 创建新节点
        Node newNode = new Node(t,null);
        if (top == null) {
            top = newNode;
        }else {
            newNode.next = top;
            top = newNode;
        }
        currentSize++;
        return true;
    }

    @Override
    public T pop() {
        if (isEmpty()) {
            System.err.println("当前栈为空！");
            return null;
        }
        T result = top.t; // 取回当前栈顶的元素
        top = top.next; // 维护当前 result —— 出栈时，把栈顶后面的元素重新设置为 top
        currentSize--;
        return result; // 将栈顶元素 pop出栈
    }

    @Override
    public T peek() {
        if (isEmpty()) {
            System.err.println("当前栈为空！");
            return null;
        }
        return top.t;
    }

    @Override
    public int getSize() {
        return currentSize;
    }

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

// 基于数组实现栈 —— 顺序栈
 
public class ArrayStack<T> implements Stack<T> {
    // 存放数据
    private Object[] elementData;
    // 最多存放的元素个数
    private int maxSize;
    // 当前栈中的元素个数
    private int currentSize;

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        elementData = new Object[maxSize];
    }

    @Override
    public boolean push(T t) {
        if (currentSize == maxSize) {  // 栈已满
            // 动态扩容
            int oldSize = maxSize;
            int newSize = oldSize << 1;
            if (newSize + 8 > Integer.MAX_VALUE) {
                System.err.println("栈太大！");
                return false;
            }
            maxSize = newSize;
            elementData = Arrays.copyOf(elementData,maxSize);
//            System.err.println("栈已满，无法放置新的元素！");  // 数组扩容前
//            return false;                                    // 数组扩容前
        }
        elementData[currentSize++] = t;
        return true;
    }

    @Override
    public T pop() {
        if (isEmpty()) {
            System.err.println("栈为空");
            return  null;
        }
        return (T) elementData[--currentSize];
    }

    @Override
    public T peek() {
        if (isEmpty()) {
            System.err.println("栈为空");
            return  null;
        }
        return (T) elementData[currentSize - 1];
    }

    @Override
    public int getSize() {
        return currentSize;
    }

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