手写先进先出队列

心已赠人 2022-11-01 13:55 221阅读 0赞

这里采用的是双端链表来实现的先进先出对列。

package com.yanling.queue;
    
    /**
     * 队列（先进先出）
     * @author yanling
     * @date 2021-2-14
     */
    public class MyFIFO {
    
        public int size;
        /**
         * 尾指针
         */
        private Node last;
        /**
         * 头指针
         */
        private Node first;
    
        /**
         * 队列添加元素
         * @param e
         */
        public void add(int e) {
            Node f = last;
            Node newNode = new Node(f, e, null);
            last = newNode;
            if (f == null) {
                first = newNode;
            } else {
                f.gNext = last;
            }
            size++;
        }
    
        /**
         * 弹出第一个元素
         * @return
         */
        public Integer poll(){
            if (first == null) {
                return null;
            }
            Node team = first;
            first = first.gNext;
            if (first != null) {
                // 断开连接
                first.lNext = null;
            }
            size--;
            return team.val;
        }
    
        /**
         *  双向链表
         */
        class Node {
    
            int val;
            Node lNext;
            Node gNext;
    
            public Node(Node lNext, int val, Node gNext) {
                this.val = val;
                this.lNext = lNext;
                this.gNext = gNext;
            }
        }
    }

完成了对列的实现，线面测试下

public static void main(String[] args) {
            MyFIFO fifo = new MyFIFO();
            fifo.add(1);
            fifo.add(2);
            fifo.add(3);
            for (; 1 < fifo.size;) {
                System.out.println(fifo.poll());
            }
            fifo.add(4);
            fifo.add(5);
            for (; 0 < fifo.size;) {
                System.out.println(fifo.poll());
            }
            System.out.println(fifo.poll());
        }

控制台打印结果

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0OTk2NzI3_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0OTk2NzI3_size_16_color_FFFFFF_t_70]: /images/20221024/fa3d17b130f84dec899b4539916f72d3.png