問題: 使用兩個單向鏈表(隊列),完成堆棧

實際上,這個問題非常簡單,我已經(jīng)寫過很多遍了,可是面試官問的時候,突然忘記了. 其實我一開始想到就是可行的~~~ 這個問題反應的本質是:我依然對基礎不夠熟悉,沒有形成"肌肉記憶",故重擼一下

簡單原理:

• 堆棧中用于兩個隊列A,B.
• Push的時候,都Push在A的隊列中.
• Pop的時候, 循環(huán)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;
            }
        }
    }