算法第四版P88算法1.1 下压(LIFO)栈(能够动态调整数组大小的实现) ResizingArrayStack

绝地灬酷狼 2022-03-19 11:37 143阅读 0赞

# 简介 #

集合类抽象数据类型实现的模板,动态调整数组的大小.实现了泛型,避免了游离.实现了可迭代

# java代码 #

package book1_3;
    
    import edu.princeton.cs.algs4.Stack;
    
    import java.util.Iterator;
    
    /**
     * @description: ${description}
     * @create: 2019-02-16
     * 一,member variables :
     * 1 范型数组
     * 2 指针N
     * 二,methods:
     * 1 void push(String item)
     * 2 String pop()
     * 3 boolean isEmpty()
     * 4 int size()
     * 5 resize
     * 6 迭代方法
     * 三,类自身 实现迭代
     **/
    //<T>代表着声明这个类用到了泛型
    public class ResizingArrayStack<T> implements Iterable {
        private T[] a = (T[]) new Object[1];//数组长度默认是1.随着数据变多,可以动态的增加来扩容,而且利用到了泛型
        private int n = 0;
    
        private void resize(int max) {
            T[] b = (T[]) new Object[max];
            for (int i = 0; i < n; i++) {//这里用n而不用a.length可以提高效率,少遍历没用的下标
                b[i] = a[i];
            }
            a = b;//将扩容后且内容一样的数组,赋值给a
        }
    
        public boolean isEmpty() {
            return n == 0;
        }
    
        public int size() {
            return n;
        }
    
        public void push(T t) {
            if (n == a.length) {
                resize(a.length * 2);//当n这个指针达到数组的长度时候,就将数组扩容两倍
            }
            a[n] = t;
            n++;//把指针指向下一个位置
        }
    
        public T pop() {
            n--;//指针n指向的有值的后一个位置,先移回来一个位置,然后再取值
            T result = a[n];
            a[n] = null;//取出来以后,避免游离就删了
            if (n > 0 && n == a.length / 4) {
                resize(a.length / 2);//如果指针只有数组长度的1/4,那么就把数组的容量减半,提高效率
            }
            return result;
        }
    
        @Override
        public Iterator iterator() {
            return new ReverseArrayIterator();
        }
    
        private class ReverseArrayIterator implements Iterator {
    
            @Override
            public boolean hasNext() {
                return n > 0;
            }
    
            @Override
            public Object next() {
                n--;
                T ttt = a[n];
                return ttt;
            }
    
            @Override
            public void remove() {
                //blank
            }
        }
    
        public static void fnPrint(String exp) {
            String[] split = exp.split(" ");
            //使用我们自己定义的数据结构.注意:当new对象的时候要定义好泛型
            ResizingArrayStack<String> ras = new ResizingArrayStack<String>();
            for (String s : split) {
                //这里要多判断一下,f函数的成员变量n是否为零.如果为零,则说明数组里面没东西了,不能用pop()去取数据,否则则会报错
                if (s.equals("-") && !ras.isEmpty()) {
                    String pop = ras.pop();//取数据的前提是:数组里面还有数据才可以
                    System.out.println(pop);
                } else {
                    ras.push(s);
                }
            }
            System.out.println("-----------------end-------------------");
            System.out.println(ras.size() + " left on stack ");
            /*由于我们这个类implements Iterable,
            * 并且实现了public Iterator iterator()这个方法
            * 在方法内返回了自定义的ReverseArrayIterator类(继承Iterator)
            * ReverseArrayIterator重写了两个方法
            * 因此对比FixedCapacityStackOfStrings多了遍历的功能
            * */
            System.out.println("the date left in ResizingArrayStack are:");
            for (Object s:ras
                 ) {
                System.out.println(s);
            }
        }
    
        public static double cal(String expression){
            String[] stringArray = expression.split(" ");
            ResizingArrayStack<String> fuhao=new ResizingArrayStack<String>();//1操作符号栈 这里就不是Stack了.是用我们自己做的数据格式
            ResizingArrayStack<Double> number=new ResizingArrayStack<Double>();//2数字栈 同上,由于有了泛型,适用性就更广了
            for (String s:stringArray) {
                //表达式从左往右.逐个读取
                //第一种情况,遇到左括号,则什么都不做
                if(s.equals("(")){
    
                }else if (s.equals("+")){//第二种情况,遇到加减乘除,则放到1操作符号栈里面
                    fuhao.push("+");
                }else if (s.equals("-")){//第二种情况,遇到加减乘除,则放到1操作符号栈里面
                    fuhao.push("-");
                }else if (s.equals("*")){//第二种情况,遇到加减乘除,则放到1操作符号栈里面
                    fuhao.push("*");
                }else if (s.equals("/")){//第二种情况,遇到加减乘除,则放到1操作符号栈里面
                    fuhao.push("/");
                }else if(s.equals(")")){//第三种情况,遇到右括号.则从操作符号栈中取出1个操作符号,从数字栈中取出2个数字
                    double pop1 = number.pop();
                    double pop2 = number.pop();
                    String jisuanfu = fuhao.pop();
                    double result=0.0;
                    //根据操作符号来计算这两个数字
                    //注意:栈是后进先出的,因此先取的pop1要放到pop2的后面
                    /*举例:12/4
                     * 数字栈放进去后是:
                     * 4
                     * 12
                     * 数字栈取出来后是:
                     * pop1=4    pop2=12
                     * 所以是pop2/pop1 而不是pop1/pop2
                     * */
                    if(jisuanfu.equals("+")){
                        result=pop2+pop1;
                    }else if(jisuanfu.equals("-")){
                        result=pop2-pop1;
                    }else if(jisuanfu.equals("*")){
                        result=pop2*pop1;
                    }else if(jisuanfu.equals("/")){
                        result=pop2/pop1;
                    }
                    number.push(result);
                }else {//第四种情况,排除了左右括号和操作符号以外.只剩下一种情况,数字,数字无脑放到数字栈
                    number.push(Double.valueOf(s));
                }
            }
            /*
             * 全部计算完毕后,数字栈只剩下一个数字了,就是计算的结果.取出来返回即可
             * */
            return number.pop();
        }
        public static void main(String[] args) {
            String exp = "to be or not to - be - - that - - - is";
            fnPrint(exp);
            System.out.println("2...............");
            String expression1="( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )";
            double cal = cal(expression1);
            System.out.println(cal);
        }
    }

# 结果 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]

# 心得 #

优点:  
1.数组长度动态调整  
2.可迭代  
3.避免游离  
4.支持泛型,可以用不同的类型  
缺点:  
1.push和pop可能会调整数组的大小,这就导致操作耗时和栈的大小成正比

引入链表的概念

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]: /images/20220319/e6c7c327022f4c64bc87590a413b0b30.png