实现先进后出栈

太过爱你忘了你带给我的痛 2022-11-01 13:57 130阅读 0赞

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

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

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

public static void main(String[] args) {
            MyFILO fifo = new MyFILO();
            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/2a9f66371aab45f585127f97cb74f6cb.png