堆栈（stack）又称为栈或堆叠，是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作。

栈类似于我们现实中的客栈，用于临时存储数据。但它 LIFO 的性质不太符合人类的行为，不过却非常符合人类存放东西的行为，这导致它对于数据的临时处理非常有用。可以把它想象成子弹的弹夹、装小球的试管、咖啡店堆叠的纸杯等…

栈的基本操作

操作	API	描述
添加数据	Push	向栈中压入数据
移除数据	Pop	从栈中弹出数据
查看栈顶	Peek	查看栈顶部的数据

一个基本的栈必须实现以上的 API，有的地方会写道最基本的操作是 Push 和 Pop，但这两个仅仅只是对栈的数据操作，但我们对栈的所有操作并非一直都是数据读写操作。

Peek 操作是对栈的状态的描述之一，Peek 操作可以让我们知道栈是否为空，栈顶元素的状态，而栈的长度、栈顶一下的其他元素这些信息并不是我们必须关心的。

栈的实现

栈的实现分为两种：链表实现和顺序表实现

链表实现并不需要关心栈的容量，实现起来较为方便。顺序表实现由于在初始化栈的时候需要设定顺序表的长度，因此涉及到了判断是否栈满和是否扩容的操作。

先定义一个栈的虚基类，继承 Vector，设定好必需的 API：

public abstract class Vector<E> {

    /**
     * 容器当前元素数量
     */
    protected int size = 0;

    /**
     * 判断该容器是否为空
     *
     * @return 为空则返回 true
     */
    public synchronized boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 获取概况容器中元素的数量
     *
     * @return 元素的数量
     */
    public synchronized int getSize() {
        return this.size;
    }
}

public abstract class Stack<E> extends Vector<E> {

    /**
     * 将元素压入栈
     * 
     * @param element 待入栈元素
     * @return 若成功入队返回 true
     */
    public abstract boolean push(E element);

    /**
     * 弹出栈顶的元素
     *
     * @return 栈顶的元素
     */
    public abstract E pop();

    /**
     * 获取栈顶部的元素
     *
     * @return 容器头部的元素
     */
    public abstract E peek();
}

栈的链表实现

/**
 * 栈的链表实现
 * 
 * @param <E> 元素类型
 */
public class LinkedListStack<E> extends Stack<E> {

    SingleLinkedListNode<E> head = new SingleLinkedListNode<>(null, null);

    public LinkedListStack() {}

    @Override
    public synchronized boolean push(E element) {
        this.head.next = new SingleLinkedListNode<>(element, this.head.next);
        this.size += 1;
        return true;
    }

    @Override
    public synchronized E peek() {
        if (isEmpty()) {
            return null;
        }
        return this.head.next.data;
    }

    @Override
    public synchronized E pop() {
        if (isEmpty()) {
            return null;
        }
        SingleLinkedListNode<E> res = this.head.next;
        this.head.next = res.next;
        res.next = null;
        this.size -= 1;
        return res.data;
    }
}

栈的顺序表实现

import java.util.Arrays;

/**
 * 栈的数组实现
 *
 * @param <E> 栈内元素类型
 */
public class ArrayStack<E> extends Stack<E> {
    /**
     * 栈初始容量
     */
    private int capacity;

    /**
     * 当前栈顶元素的下标，若栈为空则为 -1
     */
    private int top = -1;

    /**
     * 是否可扩容，若为 false，则数组容量固定无法扩容，默认可扩容
     */
    private boolean isExtendible = true;

    /**
     * 负载因子，当数量达到容量乘以负载因子，则数组进行扩容，默认存储满员才扩容
     */
    private int factor = 1;
    
    /**
     * 栈数组
     */
    private Object[] elements;

    /**
     * 关闭无参构造函数
     */
    private ArrayStack(){}

    /**
     * 顺序栈，默认可拓展，拓展因子为 1
     *
     * @param capacity 初始容量
     */
    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.elements = new Object[capacity];
    }

    /**
     * 顺序栈，默认可拓展
     *
     * @param capacity 初始容量
     * @param factor 拓展因子
     */
    public ArrayStack(int capacity, int factor) {
        this.capacity = capacity;
        this.elements = new Object[capacity];
        this.factor = factor;
    }

    public ArrayStack(int capacity, boolean isExtendible, int factor) {
        this.capacity = capacity;
        this.isExtendible = isExtendible;
        this.factor = isExtendible ? factor : 1;
        this.elements = new Object[capacity];
    }

    @Override
    public synchronized boolean push(E element) {
        return isExtendible ? pushWithExtension(element) : pushWithoutExtension(element);
    }

    /**
     * 入栈操作，如果栈容量不够则进行拓展
     *
     * @param element 待入栈元素
     * @return 成功入栈返回 true
     */
    private boolean pushWithExtension(E element) {
        ensureCapacity();
        this.size += 1;
        this.elements[++top] = element;
        return true;
    }

    /**
     * 入栈操作，不进行容量拓展
     *
     * @param element 待入栈元素
     * @return 成功入栈返回 true
     */
    private boolean pushWithoutExtension(E element) {
        if (this.size == this.capacity)
            return false;
        this.size += 1;
        this.elements[++top] = element;
        return true;
    }

    @Override
    @SuppressWarnings("unchecked")
    public synchronized E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) this.elements[top];

    }

    @Override
    @SuppressWarnings("unchecked")
    public synchronized E pop() {
        if (isEmpty()) {
            return null;
        }
        this.size -= 1;
        return (E) this.elements[top--];
    }

    /**
     * 调节容量，如果容量超出调节因子，则进行扩容
     */
    private void ensureCapacity() {
        if (this.size + 1 <= this.capacity * factor) {
            return;
        }
        capacity += 1;
        this.elements = Arrays.copyOf(this.elements, capacity);
    }
}