算法第四版 P84定容栈 FixedCapacityStackOfStrings的算法实现

不念不忘少年蓝@ 2022-03-19 10:24 148阅读 0赞

# 题目 #

简单版本的实现栈(LIFO)后进先出

# JAVA代码 #

package book1_3;
    
    /**
     * @description: ${description}
     * @create: 2019-02-16
     * FixedCapacityStackOfStrings(int cap)
     * void push(String item)
     * String pop()
     * boolean isEmpty()
     * int size()
     * param:
     * 1.String[] a
     * 2.size
     **/
    public class FixedCapacityStackOfStrings {
        private String[] a;
        private int n=0;
    
        public FixedCapacityStackOfStrings(int capacity) {
            a=new String[capacity];
        }
        public void push(String item){
            //a[n++]=item
            a[n]=item;
            n++;
        }
        public String pop(){
            //return a[--m]
            n=n-1;
            return a[n];
        }
        public boolean isEmpty(){
            return n==0;
        }
        public int size(){
            return n;
        }
    
        public static void fnPrint(String exp){
            String[] split = exp.split(" ");
            FixedCapacityStackOfStrings f=new FixedCapacityStackOfStrings(20);
            for (String s:split) {
                //这里要多判断一下,f函数的成员变量n是否为零.如果为零,则说明数组里面没东西了,不能用pop()去取数据,否则则会报错
                if(s.equals("-") && !f.isEmpty()){
                    String pop = f.pop();//取数据的前提是:数组里面还有数据才可以
                    System.out.println(pop);
                }else{
                    f.push(s);
                }
            }
            System.out.println("-----------------end-------------------");
            System.out.println(f.size()+" left on stack ");
    
        }
    
        public static void main(String[] args) {
            String exp="to be or not to - be - - that - - - is";
            fnPrint(exp);
        }
    }

# 运行结果 #

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

# 心得 #

优点:  
1.栈的乞丐版本  
2.push和pop和栈的长度无关  
缺点:  
1.不支持各种类型的(泛型);  
2.数组大小被写死了.没办法动态的改变  
3.对象游离了没有被回收  
4.不支持迭代

改进版本:算法1.1 下压栈 能够动态调整数组大小

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]: /images/20220319/47e97c54cdcc49d4a222097c5a63cdf0.png