算法第四版P94 算法1.2 下压堆栈(链表实现LinkedList)

谁践踏了优雅 2022-03-19 14:49 141阅读 0赞

# 说明 #

基于链表数据结构实现Stack

# java代码 #

package book1_3;
    
    import java.util.Iterator;
    
    /**
     * @description: ${description}
     * @create: 2019-02-16
     * 利用链表来实现Stack
     * 1 内部嵌套类Node:内容Item;指向Node
     * 2 成员变量:栈顶Node first   指针n
     * 3 方法:isEmpty size push pop resize没了 iterator
     **/
    public class LinkedListStack<Item> implements Iterable {
    
        private class Node{
            Item item;
            Node next;
        }
        private Node first;//栈顶,最近添加元素,也是个类,有两个属性
        private int n;//元素数量,类似指针
    
        public void push(Item item){
            Node old=first;
            first=new Node();
            first.item=item;
            first.next=old;
            n++;
        }
        public Item pop(){
            n--;
            Item item = first.item;
            first=first.next;
            return item;
        }
        public int size(){
            return n;
        }
        public boolean isEmpty(){
            return n==0;
        }
    
        @Override
        public Iterator iterator() {
            return new ListIterator();
        }
        private class ListIterator implements Iterator<Item>{
            private Node current=first;
    
            @Override
            public boolean hasNext() {
                return current!=null;
            }
    
            @Override
            public Item next() {
                Item item = current.item;
                current=current.next;
                return item;
            }
    
            @Override
            public void remove() {
                //blank
            }
        }
    
        public static void fn(String exp) {
            String[] split = exp.split(" ");
            //使用我们自己定义的数据结构.注意:当new对象的时候要定义好泛型
            LinkedListStack<String> linkedListStack = new LinkedListStack<String>();
            for (String s : split) {
                //用pop()去取数据,先判断下
                if (s.equals("-") && !linkedListStack.isEmpty()) {
                    String pop = linkedListStack.pop();//取数据的前提是:数组里面还有数据才可以
                    System.out.println(pop);
                } else {
                    linkedListStack.push(s);
                }
            }
            System.out.println("-----------------end-------------------");
            System.out.println(linkedListStack.size() + " left on stack ");
            System.out.println("the date left in linkedListStack are:");
            for (Object s:linkedListStack
            ) {
                System.out.println(s);
            }
        }
        public static void main(String[] args) {
            String exp = "to be or not to - be - - that - - - is";
            fn(exp);
        }
    }

# 运行结果 #

![idea][]

# 心得 #

比较简单的数据结构.但是有点抽象,  
重点是怎么操作表头first

[idea]: /images/20220319/f5698deb0d5d40fc93ec6cc4d76079a4.png