[从今天开始修炼数据结构]栈、斐波那契数列、逆波兰四则运算的实现

一、栈的定义

栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）。栈又称后进先出的线性表，简称LIFO结构。

注意：首先它是一个线性表，也就是说栈元素有前驱后继关系。

栈的插入操作，叫做进栈，也称压栈、入栈

栈的删除操作，叫做出栈，也叫弹栈。

注意：最先入栈，不代表就要最后出栈。因为栈没有限制出栈的时间，例如可以先入栈两个元素，再出栈两个元素，后入栈其他元素。

二、栈的抽象数据类型

ADT Stack
Data
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继。
Operation
    InitStack(S) : 初始化操作，建立一个空栈
    DestroyStack(S):若栈存在，销毁它。
    ClearStack(S):将栈清空
    StackEmpty:若栈为空，返回true，否则返回false。
    GetTop(S,e):若栈存在且非空，用e返回栈顶元素。
    Push(S,e):若栈S存在，插入新元素e到栈顶
    Pop(S,e):删除S中栈顶元素，并用e返回其值
    StackLength(S):返回栈S中的元素个数
endADT

三、栈的顺序结构

1，栈的顺序存储结构是什么样子

栈的顺序存储结构也是用数组来实现的。让下标0的一端作为栈底，另一端作为栈顶。若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top = 0.因此通常把空栈的判定条件定为top = - 1。

2，顺序结构栈的实现

package Stack;

public class ArrayStack<T>{
    private Object[] list;
    private int top;
    private int size;
    private static int DEFAULT_SIZE = 10;

    public ArrayStack(int size){
        list = new Object[size];
        this.size = size;
        top = -1;
    }

    public ArrayStack(){
        this(DEFAULT_SIZE);
    }

    public void push(T data){

        if (!isFull()){
                list[++top] = data;
        }else {
            System.out.println("栈满了");
        }
    }

    public T pop(){
        if (!isEmpty()){
                T obj = (T)list[top];
                list[top] = null;
                top--;
                return obj;

        }else {
            System.out.println("栈是空的");
        }
        return null;
    }

    private boolean isEmpty(){
        return top == -1;
    }

    private boolean isFull() {
        return top >= size;
    }

    public int size(){
        return size;
    }

    public int getTop(){
        return top;
    }
}

 四、共享栈

1，共享栈是指两栈共享一片空间的栈。如下图所示

 　　两个栈共用一块数组，以两头为栈底，中间为栈顶。可以节省空间。判断满的方法是top1 + 1 = top2.

2，共享栈的实现。

package Stack;

public class ShareStack<T> {
    private Object[] list;
    private int top1;
    private int top2;
    private int capacity;
    private static int DEFAULT_SIZE = 10;
    //private boolean isFull = false;

    public ShareStack(int capacity){
        list = new Object[capacity];
        this.capacity = capacity;
        top1 = -1;
        top2 = capacity;
    }

    public ShareStack(){
        this(DEFAULT_SIZE);
    }

    public boolean pushStackOne(T data){
        if (!isFull()){
            list[++top1] = data;
            //isFull = isFull();
            return true;
        }else{
            System.out.print("栈满了！");
            return false;
        }
    }

    public boolean pushStackTwo(T data){
        if (!isFull()){
            list[--top2] = data;
            //isFull = isFull();
            return true;
        }else{
            System.out.print("栈满了！");
            return false;
        }
    }

    public T popStackOne(){
        if (!isEmptyOne()){
            T data = (T)list[top1--];
            return data;
        }else {
            System.out.println("栈一是空的!");
            return null;
        }
    }

    public T popStackTwo(){
        if (!isEmptyTwo()){
            T data = (T)list[top2++];
            return data;
        }else {
            System.out.println("栈二是空的！");
            return null;
        }
    }

    private boolean isEmptyTwo() {
        return top2 == capacity;
    }

    private boolean isFull() {
        return top1 == (top2 - 1);
    }

    private boolean isEmptyOne(){
        return top1 == -1;
    }

}

五、栈的链式存储及实现　

1，栈的链式存储简称链栈，把栈顶放在单链表的头部。如下图

 2，链栈的实现

public class LinkedStack<T> {
    private Node<T> top;

    public void push(T data){
        Node<T> newNode = new Node<>(data, null);
        Node<T> t = top;
        top = newNode;
        top.next = t;
    }

    public T pop(){
        Node<T> t = top;
        if (!isEmpty()){
            top = top.next;
            return t.data;
        }else {
            System.out.println("栈为空！");
            return null;
        }
    }

    private boolean isEmpty() {
        return top == null;
    }

    private class Node<T> {
        private T data;
        private Node next;

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

}

以表头为栈顶，降低了弹栈操作的时间复杂度。若以表尾为栈顶则弹栈只能遍历找到top-1位置，或者用双向链表牺牲空间。如下

public T pop(){
        if (!isEmpty()){
            Node<T> newTop = bottom;
            while (newTop.next != top){
                newTop = newTop.next;
            }
            T data = top.data;
            top = newTop;
            top.next = null;
            return data;
        }else {
            System.out.println("栈是空的！");
            return null;
        }
    }

五、栈的应用 —— 递归

1，斐波那契数列的递归实现

引例：如果兔子在出生两个月后就有繁殖能力，一对兔子每个月能生出一对小兔子。假设所有兔子都不死，那么一年后有多少对兔子？分析得出兔子数量按天数增加如下表

表中数列有明显的特点：相邻前两项之和等于后一项。抽象成函数表达如下

 迭代实现如下：

public class Fibonacci {    public static void main(String[] args) throws Exception {        System.out.println(Fibonacci(12));    }    public static int Fibonacci(int month) throws Exception {        if (month < 0){            throw new Exception();        }        if (month < 2){            return month == 0 ? 0 : 1;        }else {            return (Fibonacci(month - 1) + Fibonacci(month - 2));        }    }}

代码执行过程如下：

递归实现法的时间复杂度为O(2ⁿ)，太高，还可能会引起内存栈溢出，所以应该用别的方法求解。这篇文章主要讲由栈引出递归，所以先挖个坑，在后面的文章中我会单独讨论递归和斐波那契数列的其他解法。

参考：https://blog.csdn.net/sofia_m/article/details/78796084

https://blog.csdn.net/IronWring_Fly/article/details/100050016

https://blog.csdn.net/Bob__yuan/article/details/84956740

2，在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。

六、栈的应用 —— 四则运算表达式求值

1，后缀（逆波兰）表示法定义

对于会计计算器，不能表达复杂的带括号和多种运算符号复合的表达式；而对于科学计算器，我们可以一次将一个复杂的带括号的四则运算输入进去，计算器是怎么做到的呢？

这就引入了一种不需要括号的后缀表达法 —— 逆波兰表达法。举个例子来看 对于 “ 9 + （ 3 - 1） * 3 + 10 / 2”这个表达式，转换成后缀表达式应该变为 “ 9 3 1 - 3 * + 10 2 / + ”。 叫做后缀的原因就是所有的符号都在被运算的数字后面出现。

2，我们先来看看后缀表达式是如何计算的 

规则： 从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到符号，就把数字栈栈顶的两个数字出栈，栈顶元素放在运算符后面，栈顶下面一个元素放在运算符前面。再将运算结果进栈，如此往复，直到获得最终结果。

步骤精解：我们以上面的 “ 9 3 1 - 3 * + 10 2 / + ” 为例

（1）初始化一个空栈，用来对要运算的数字进行进出使用

（2）后缀表达式中前三个都是数字，所以将9 3 1 依次进栈。

 　　（3）接下来是运算符“ - ”，所以将1， 3 出栈，运算3 - 1得到2 ，将2进栈，然后遇到3 ，将3进栈

 　　（4）后面遇到“ * ”，将3， 2出栈，计算2 * 3，得到6，将6进栈

（5）遇到“ + ”，将6 ， 9出栈，计算9 + 6，得到15，将15进栈

 　　（6）将10， 2 进栈

 　　（7）遇到符号“ / ” 将2， 10出栈，计算10/2得到5，将5压栈

 　　（8）最后一个符号 “ + ”，将15，5出栈，计算15 + 5，得到20，将20压栈

 　　（9）表达式读取完成，将结果20出栈，栈变为空。

这就是通过后缀表达式计算四则运算的结果。那么下面我们再来讨论如何将中缀表达式（也就是我们平时数学课上计算的形式）转换为方便计算机运算的后缀表达式呢？

3，中缀转后缀

规则：从左到右遍历中缀表达式，如果是数字就存入后缀表达式，如果是符号就判断其与栈顶符号的优先级，如果优先级不高于栈顶符号，则栈顶元素依次出栈并输出，并将当前符号进栈。特殊的，遇到左括号就进栈，左括号的优先级不做判断；当遇到右括号时，将与其匹配的左括号以上的全部符号依次出栈。直到最终输出后缀表达式为止。

具体步骤：我们还是以上面的 “ 9 + （ 3 - 1） * 3 + 10 / 2”这个表达式为例

（1）初始化一个空栈。遇到第一个字符是数字9，输出9，遇到符号“ + ”，进栈。

 　　（2）遇到字符“ （ ”进栈，然后遇到了数字3，输出，又遇到了符号“ - ”，进栈。如下图

 　　（3）遇到符号“  ） ”，根据规则，匹配前面的“ （ ”，并将其上的符号依次出栈并输出，直到“ （ ”出栈。

 　　（4）下面遇到了符号“ * ”，比较其与栈顶元素 “ + ”的优先级。* 的优先级更高，所以压栈。 后面遇到了数字3 ，输出。

 　　（5）之后遇到了符号 “ + ”，与栈顶元素“ * ”比较， + 的优先级低，所以将 * 弹栈，再与现在的栈顶 + 比较，与新来的 + 优先级相同，所以将栈顶+也出栈，将新来的 + 弹栈。如下图

 　　（6）紧接着数字10，输出，后面是符号“ / ”，进栈。 最后一个数字2 输出。原表达式读取完成，将栈内剩余的符号都出栈，得到

 4，实现逆波兰四则运算（静态方法调用）

package Stack;

import java.util.Stack;
import java.util.regex.Pattern;

public class RPNmethod {
    private static Stack<String> charStack = new Stack<>();
    private static Stack<Integer> intStack = new Stack<>();

    public static int RPN(String exp){
        String behindEXP = convert(exp);
        String[] chars = behindEXP.split(" ");
        for (int i = 0; i < chars.length; i++){
            String thisOne = chars[i];
            if (isNum(thisOne)){
                intStack.push(Integer.parseInt(thisOne));
            }else if (isSymbol(thisOne)){
                int a = intStack.pop();
                int b = intStack.pop();
                int result;
                switch (thisOne){
                    case "+": result = b + a;
                        intStack.push(result);
                        break;
                    case "-": result = b - a;
                        intStack.push(result);
                        break;
                    case "*": result = b * a;
                        intStack.push(result);
                        break;
                    case "/": result = b / a;
                        intStack.push(result);
                        break;
                }
            }
        }
        return intStack.pop();
    }

    /**
     * 将中缀表达式转为后缀表达式
     * @param middle
     * @return
     */
    private static String convert(String middle){
        String rpnEXP = "";
        String[] chars = middle.split(" ");
        for(int i = 0; i < chars.length; i++){
            String thisOne = chars[i];
            if (isNum(thisOne)){
                rpnEXP = rpnEXP + thisOne + " ";
            }else if (isSymbol(thisOne)) {
                /*
                三个分支 ： 是左括号，是右括号，不是括号
                 */
                if (isLeftPar(thisOne)) {
                    charStack.push(thisOne);
                } else if (isRightPar(thisOne)) {//Here
                    while (!isLeftPar(thisOne)) {
                        thisOne = charStack.pop();
                        if (!isLeftPar(thisOne)) {
                            rpnEXP = rpnEXP + thisOne + " ";
                        }
                    }
                } else {
                    if (charStack.isEmpty() || !lowerPriority(thisOne, charStack.peek())) {
                        charStack.push(thisOne);
                    } else {
                        do {
                            rpnEXP = rpnEXP + charStack.pop() + " ";
                        }
                        while (!charStack.isEmpty() && lowerPriority(thisOne, charStack.peek()));
                        charStack.push(thisOne);
                    }
                }
            }
        }
        while(!charStack.isEmpty()){
            rpnEXP = rpnEXP + charStack.pop() + " ";
        }
        return rpnEXP;
    }

    private static boolean isLeftPar(String aChar) {
        return aChar.equals("(");
    }

    /**
     * 返回新来的优先级是不是不大于栈顶.aChar > peek 就返回false，peek >= aChar 就返回true
     * @param aChar
     * @param peek
     * @return 返回true就弹栈，返回false就将新来的压栈
     */
    private static boolean lowerPriority(String aChar, String peek) {
        if(peek.equals("(")){
            return false;
        }
        else if (aChar.equals("+") || aChar.equals("-")){
            return true;
        }else {
            if (peek.equals("*") || peek.equals("/")){
              return true;
            }else {
                return false;
            }
        }
    }

    private static boolean isRightPar(String c) {
        return c.equals(")");
    }

    private static boolean isNum(String c){
        Pattern pattern = Pattern.compile("[\\d]*$");
        return pattern.matcher(c).matches();
    }

    private static  boolean isSymbol(String c){
        String pattern = "[-/*+()]";
        return Pattern.matches(pattern,c) ;
    }
}