算法第四版 P95 算法1.3 基于链表数据结构LinkedList实现队列Queue

爱被打了一巴掌 2022-03-19 14:56 138阅读 0赞

# 原理 #

使用链表数据结构  
enqueue()插入元素到队列的尾巴  
dequeue()取出队列开始的元素,返回,然后再删除  
先进先出,后进后出  
利用链表实现队列

# java代码 #

package book1_3;
    
    import java.util.Iterator;
    
    /**
     * @description: ${description}
     * @create: 2019-02-17
     * 方法isEmpty size dequeue enqueue iterator
     * 成员变量
     **/
    public class LinkListQueue<Item> implements Iterable {
        private class QueueIterator implements Iterator {
            private Node current = first;
    
            @Override
            public boolean hasNext() {
                return current != null;
            }
    
            @Override
            public Object next() {
                Item item = current.item;
                current = current.next;
                return item;
            }
    
            @Override
            public void remove() {
                //blank
            }
        }
    
        @Override
        public Iterator iterator() {
            return new QueueIterator();
        }
    
        private class Node {
            Item item;
            Node next;
        }
    
        private Node first;
        private Node last;
        private int n;
    
        public boolean isEmpty() {
            return n == 0;
        }
    
        public int size() {
            return n;
        }
    
        public void enqueue(Item item) {//在集合的尾巴加入元素
            Node old = last;
            last = new Node();
            last.item = item;
            last.next = null;
            if (isEmpty()) {//当集合为空的时候,first和last都指向新建的第一个Node
                first = last;
            } else {//当集合为空的时候old是null,下面的语句不正确,当不为空的时候,old才有内容
                old.next = last;
            }
            n++;//集合数量无论如何都增加1
        }
    
        public Item dequeue() {//把集合第一个元素的值返回出来,然后删了第一个元素,把第二个元素当成第一个元素
            Item item = first.item;
            first = first.next;
            if (n == 1) {
                last = null;
            }
            n--;
            return item;
        }
    
        public static void main(String[] args) {
            LinkListQueue<String> queue = new LinkListQueue<String>();
            String exp = "to be or not to - be - - that - - - is";
            String[] split = exp.split(" ");
            for (String s : split
            ) {
                if (!s.equals("-")) {
                    queue.enqueue(s);
                } else if (!queue.isEmpty()) {
                    String dequeue = queue.dequeue();
                    System.out.print(dequeue + " ");
                }
            }
            System.out.println();
            System.out.println(queue.size());//队列里面的元素的个数
            //打印队列里面剩余的元素
            for (Object ele : queue
            ) {
                System.out.print(ele + " ");
            }
        }
    }

# 运行结果 #

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

# 心得 #

1.类似于LinkedListStack  
2.利用2个变量.first和last  
3.插入和删除的时候要判断是否为空

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]: /images/20220319/5e3b6ad06d1746afa1e67a263d152966.png