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

一、栈的定义

栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶(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,斐波那契数列的递归实现

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

所经过的月数123456789101112
兔子对数1123581321345589144

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

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

 迭代实现如下:

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(2n),太高,还可能会引起内存栈溢出,所以应该用别的方法求解。这篇文章主要讲由栈引出递归,所以先挖个坑,在后面的文章中我会单独讨论递归和斐波那契数列的其他解法。

参考: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) ;
    }
}

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

相关推荐