思维导图

什么是栈：

  堆栈（英语：stack）又称为栈或堆叠，是计算机科学中一种特殊的串列形式的抽象数据类型，其特殊之处在于只能允许在链表或数组的一端（称为堆栈顶端指针，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。另外堆栈也可以用一维数组或链表的形式来完成。堆栈的另外一个相对的操作方式称为队列。

特点：

•栈也是一种线性结构
•相比数组，栈对应的操作是数组的子集
•只能从一端添加元素，也只能从一端取出元素
•由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

操作：

堆栈数据结构使用两种基本操作：推入（压栈，push）和弹出（弹栈，pop）：

推入：将数据放入堆栈的顶端（数组形式或串列形式），堆栈顶端top指针加一。
弹出：将顶端数据数据输出（回传），堆栈顶端数据减一。

图示：

代码实现：

从上文我们知道栈的功能属于数组的一部分，我们可以调用第一篇文章实现的数组来实现栈的代码，但是数组有的功能栈用不到，所以我们不采用这种方法，而是直接写，当然你觉得那样更简单也可以直接在栈的代码中调用数组中的代码，下面代码也是使用泛型实现，以后均是。

public class ArrayStack<E> implements Stack<E> {
    E[] arraystack;
    int size;//栈元素个数

    /**
     * capacity为栈初始容量
     *
     * @param capacity
     */
    public ArrayStack(int capacity) {
        arraystack = (E[]) new Object[capacity];
    }

    //初始容量默认为10
    public ArrayStack() {
        this(10);
    }

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

    //获取栈元素个数
    @Override
    public int size() {
        return size;
    }

    //获取栈的容量大小
    public int getCapacity() {
        return arraystack.length;
    }

    //指定元素压栈
    @Override
    public void push(E e) {
        if (size == arraystack.length) {
            throw new IllegalArgumentException("arrayStack is full");
        }
        arraystack[size] = e;
        size++;
    }

    //栈顶元素出栈
    @Override
    public E pop() {
        if (size == 0) {
            throw new IllegalArgumentException("No element,pop is failed");
        }
        E e = arraystack[size - 1];
        arraystack[size - 1] = null;
        size--;
        return e;
    }

    //查看栈顶元素
    @Override
    public E peek() {
        return arraystack[size - 1];
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Stack size = %d ,capacity = %d\n", size, arraystack.length));
        res.append('[');
        for (int i = 0; i < size; i++) {
            res.append(arraystack[i]);
            if (i != size - 1) {
                res.append(',');
            }
        }
        res.append(']');
        return res.toString();
    }
}

为了使该栈能动态增减，加入以下优化：

//将旧栈指向一个新栈（新栈长度可以自定义）
    public void resize(int newCapacity){
        E[] newArrayStack =(E[])new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newArrayStack[i] = arraystack[i];
        }
        arraystack = newArrayStack;
    }

push代码优化：

//指定元素压栈
    @Override
    public void push(E e) {
        if (size == arraystack.length) {
            //元素满栈则将栈扩容（容量为旧栈2倍）
            resize(2 * arraystack.length);
        }
        arraystack[size] = e;
        size++;
    }

pop代码优化：

 //栈顶元素出栈
    @Override
    public E pop() {
        if (size == 0) {
            throw new IllegalArgumentException("No element,pop is failed");
        }
        E ret = arraystack[size - 1];
        arraystack[size - 1] = null;
        size--;
        //如果栈元素个数为容量的四分之一（考虑到复杂度震荡），将该栈指向一个新栈（容量为旧栈一半）
        if(size == arraystack.length / 4 && arraystack.length / 2 !=0){
            resize(arraystack.length / 2);
        }
        return ret;
    }

测试结果：

链表实现栈代码：

public class LinkedListStack<E> implements Stack<E>{
    LinkedList<E> linkedList = new LinkedList<>();

    public int getSize() {
        return linkedList.getSize();
    }

    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

    public void push(E e){
       linkedList.addFirst(e);
    }


    public E pop() {
        return linkedList.removeFirst();
    }

    public E peek() {
        return linkedList.getFirst();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("LinkedListStack top:");
        res.append(linkedList);
        return res.toString();
    }
}

测试结果：

时间复杂度(上述2者相同)：