问题: 使用两个单向链表(队列),完成堆栈

实际上,这个问题非常简单,我已经写过很多遍了,可是面试官问的时候,突然忘记了. 其实我一开始想到就是可行的~~~ 这个问题反应的本质是:我依然对基础不够熟悉,没有形成"肌肉记忆",故重撸一下

简单原理:

• 堆栈中用于两个队列A,B.
• Push的时候,都Push在A的队列中.
• Pop的时候, 循环Pop A得到Node, 将Push 该 Node 到B的队列,直到A被清空
• 最后,Pop B 得到堆栈的返回值

    static class Stack {

        MyLink a = new MyLink();
        MyLink b = new MyLink();

        public void push(int value) {
            a.add(value);
        }

        public int pop() {
            while (!a.isEmpty()) {
                MyLink.Node aRemoveNode = a.remove();
                b.add(aRemoveNode);
            }
            MyLink.Node bRemove = b.remove();
            if (bRemove != null) {
                return bRemove.value;
            } else {
                throw new RuntimeException();
            }
        }

    }


    static class MyLink {
        Node header;
        Node tail;

        void add(int val) {
            if (header == null && tail == null) {
                header = new Node(val);
                tail = header;
            }
            Node node = new Node(val);
            tail.next = node;
            tail = node;
        }

        void add(Node node) {
            if (header == null && tail == null) {
                header = new Node(node.value);
                tail = header;
            }
            tail.next = node;
            tail = node;
        }

        Node remove() {
            if (header == null) {
                return null;
            }
            if (header == tail) {
                Node tmp = this.header;
                this.header = null;
                this.tail = null;
                return tmp;
            }
            Node tmp = this.header;
            this.header = header.next;
            return tmp;
        }

        boolean isEmpty() {
            return this.header == null;
        }


        static class Node {

            Node next;
            int value;

            public Node(int value) {
                this.value = value;
            }

            public Node(Node next, int value) {
                this.next = next;
                this.value = value;
            }
        }
    }