栈

1. 定义

Stack（堆栈），是限定在表的一端进行插入删除操作的线性表。将进行插入或删除的一段称为站定，另一端称为栈底。插入操作称为入栈，删除元素称为出栈。

2. 实现

栈是运算受限的线性表，所以线性表的存储结构对栈也是适用的，顺序存储方式实现的栈称为顺序栈。链式存储方式的栈称为链栈。

3. 应用

对A+B进行运算，原式称为中缀形式。
将运算符放在运算数的前面叫逆波兰式+AB，将运算符放在运算数的后面称为后缀形式也叫波兰式，如AB+;
编译系统处理算数表达式时，依据下列原则：
(1) 若是运算数，压入S1栈
(2) 若是运算符且S2是空栈，压入S2栈
(3)若是运算符且S2是非空栈，且运算符级别高于S2栈顶元素，压入S2栈
(4)若不属于上述情况，将S2栈顶运算符与S1栈最上面两个运算数出栈进行运算，并将结果压入S1栈。

4. 代码(来源：https://www.cnblogs.com/CherishFX/p/4608880.html)

顺序栈

/**
 * 基于数组实现的顺序栈
 * @param <E>
 */
public class Stack<E> {
    private Object[] data = null;
    private int maxSize=0;   //栈容量
    private int top =-1;  //栈顶指针
    
    /**
     * 构造函数：根据给定的size初始化栈
     */
    Stack(){
        this(10);   //默认栈大小为10
    }
    
    Stack(int initialSize){
        if(initialSize >=0){
            this.maxSize = initialSize;
            data = new Object[initialSize];
            top = -1;
        }else{
            throw new RuntimeException("初始化大小不能小于0：" + initialSize);
        }
    }
    
    //判空
    public boolean empty(){
        return top==-1 ? true : false;
    }
    
    //进栈,第一个元素top=0；
    public boolean push(E e){
        if(top == maxSize -1){
            throw new RuntimeException("栈已满，无法将元素入栈！");
        }else{
            data[++top]=e;
            return true;
        }    
    }
    
    //查看栈顶元素但不移除
    public E peek(){
        if(top == -1){
            throw new RuntimeException("栈为空！");
        }else{
            return (E)data[top];
        }
    }
    
    //弹出栈顶元素
    public E pop(){
        if(top == -1){
            throw new RuntimeException("栈为空！");
        }else{
            return (E)data[top--];
        }
    }
    
    //返回对象在堆栈中的位置，以 1 为基数
    public int search(E e){
        int i=top;
        while(top != -1){
            if(peek() != e){
                top --;
            }else{
                break;
            }
        }
        int result = top+1;
        top = i;
        return result;      
    }
}

链栈

public class LinkStack<E> {
    //链栈的节点
    private class Node<E>{
        E e;
        Node<E> next;
        
        public Node(){}
        public Node(E e, Node next){
            this.e = e;
            this.next = next;
        }
    }
    
    private Node<E> top;   //栈顶元素
    private int size=0;  //当前栈大小
    
    public LinkStack(){
        top = null;
    }
    
    //当前栈大小
    public int length(){
        return size;
    }
    
    //判空
    public boolean empty(){
        return size==0;
    }
    
    //入栈：让top指向新创建的元素，新元素的next引用指向原来的栈顶元素
    public boolean push(E e){
        top = new Node(e,top);
        size ++;
        return true;
    }
    
    //查看栈顶元素但不删除
    public Node<E> peek(){
        if(empty()){
            throw new RuntimeException("空栈异常！");
        }else{
            return top;
        }
    }
    
    //出栈
    public Node<E> pop(){
        if(empty()){
            throw new RuntimeException("空栈异常！");
        }else{
            Node<E> value = top; //得到栈顶元素
            top = top.next; //让top引用指向原栈顶元素的下一个元素 
            value.next = null;  //释放原栈顶元素的next引用
            size --;
            return value;
        }
    }
}

基于LinkedList的栈

import java.util.LinkedList;

/**
 * 基于LinkedList实现栈
 * 在LinkedList实力中只选择部分基于栈实现的接口
 */
public class StackList<E> {
    private LinkedList<E> ll = new LinkedList<E>();
    
    //入栈
    public void push(E e){
        ll.addFirst(e);
    }
    
    //查看栈顶元素但不移除
    public E peek(){
        return ll.getFirst();
    }
    
    //出栈
    public E pop(){
        return ll.removeFirst();
    }
    
    //判空
    public boolean empty(){
        return ll.isEmpty();
    }
    
    //打印栈元素
    public String toString(){
        return ll.toString();
    }
}