前言

棧和隊列作為兩種典型的線性表，有著非常鮮明甚至可以說是相互對立的特點；棧先進(jìn)后出（后進(jìn)先出），隊列先進(jìn)先出（后進(jìn)后出）。因此，對相同的輸入，兩者會產(chǎn)生恰好截然相反的輸出。例如，對于給定的序列"ABCDE",如果按照字母順序?qū)⑦@個5個元素依次入棧，然后再依次出棧，那么得到的輸出將是"EDCBA",而如果將5個元素意思壓入隊列，然后依次彈出，那么得到的輸出將是"ABCDE"。

正是因為這種截然相對的輸出，使得他們彼此之間有了更多的聯(lián)系；使得他們之間可以相互實現(xiàn)對方。就是說我們可以用棧模擬出隊列的輸出，同樣也可以用隊列模擬出棧的輸出。下面就來看看。

棧實現(xiàn)隊列

先說容易理解也是大家最容易想到實現(xiàn)方式的：用兩個棧實現(xiàn)一個隊列。

現(xiàn)在有棧Stack1和棧Stack2，假設(shè)現(xiàn)在輸入序列"ABCDE"已經(jīng)依次壓入到棧Stack1，A處于棧底，E處于棧頂，那么怎樣才可以得到輸出序列也為“ABCDE"呢，我們很容易想到，把棧Stack1倒過來就可以了，那么怎樣倒過來呢？這時候就要借助Stack2，我們把Stack1的內(nèi)容依次彈出，然后再依次壓入到Stack2不就相當(dāng)于把Stack1 倒過來了嗎？這時候Stack2 依次彈出，輸出序列就是隊列形式了。總結(jié)一下：

• 入棧只進(jìn)棧Stack1
• 出棧時，如果Stack2 不為空，則直接從Stack2彈出；如果Stack2 為空，則把Stack1的內(nèi)容依次彈出，并壓入Stack2，然后從Stack2彈出棧頂元素。

原理很簡單，實現(xiàn)起來也不難：

/**
 * Created by engineer on 2017/10/22.
 * <p>
 * 用棧實現(xiàn)隊列
 */

public class Stack2Queue {


    private static class SQueue<E> {
        //只負(fù)責(zé)進(jìn)棧元素
        private Stack<E> mTStackA;
        //負(fù)責(zé)中轉(zhuǎn)
        private Stack<E> mTStackB;

        public SQueue() {
            mTStackA = new Stack<>();
            mTStackB = new Stack<>();
        }


        public int getSize() {
            return mTStackA.size() + mTStackB.size();
        }

        private boolean enqueue(E e) {
            return mTStackA.add(e);

        }

        private E dequeue() {
            //兩個棧都為空時，則隊列也為空
            if (mTStackA.isEmpty() && mTStackB.isEmpty()) {
                return null;
            }


            if (mTStackB.isEmpty()) {
                while (!mTStackA.isEmpty()) {
                    mTStackB.push(mTStackA.pop());
                }
            }

            return mTStackB.pop();
        }
    }


    //測試類
    public static void main(String[] args) {
        SQueue<String> mSQueue = new SQueue<>();

        mSQueue.enqueue("A");
        mSQueue.enqueue("b");
        System.out.println("出對列:"+mSQueue.dequeue());
        mSQueue.enqueue("B");
        mSQueue.enqueue("C");
        System.out.println("出隊列:"+mSQueue.dequeue());
        mSQueue.enqueue("D");

        int size = mSQueue.getSize();

        System.out.printf("%d 個元素出隊：\n", size);
        for (int i = 1; i <= size; i++) {

            System.out.println(mSQueue.dequeue());
        }

    }

}

得到輸出：

出對列:A
出隊列:b
3 個元素出隊：
B
C
D

用隊列實現(xiàn)棧

有了上面的經(jīng)驗，我們可以再想想怎樣用兩個隊列實現(xiàn)棧呢？其實，思路或者說是原理，都是一樣，就是利用兩個容器，實現(xiàn)數(shù)據(jù)的翻轉(zhuǎn)，假設(shè)現(xiàn)有隊列DequeA和DequeB;剛開始兩個隊列都為空，現(xiàn)有輸入序列"ABCDE"，有元素A要入隊，那么這個時候，可以隨機一個隊列使用，假設(shè)我們選隊列DequeB,元素A進(jìn)入隊列DequeB,接著元素B,C,D進(jìn)入隊列DequeB,這個時候，如果要求有元素輸出，如果直接從隊列DequeB頭部輸出元素，那么就不符合棧后進(jìn)先出的原則，此時，需要輸出的元素是D,而他此時在隊列DequeB的尾部，因此為了輸出他，必須把他前面的ABC拿走，拿走的元素放在哪里呢？隊列DequeA恰好是空的，放進(jìn)去就好了。此時，隊列DequeB中只有一個B,讓他出隊列就好了，最后隊列DequeB空了。接著E要入隊，此時他應(yīng)該放在哪里呢？應(yīng)該放入隊列DequeA中。同樣，此時需要輸出了，再次按照剛才的思路，把隊列DequeA 中除了E之外的所有元素放入隊列DequeB中，這樣以此類推，就實現(xiàn)了棧的輸出。總結(jié)一下：

• 當(dāng)兩個隊列都為空時，有元素需要插入時，任選一個插入即可。
• 當(dāng)需要元素出棧時，從非空隊列中，除了最后一個處于隊尾的元素之外，其余元素都壓入到另一個空隊列中，并從隊列中彈出最后一個元素
• 每次入棧、出棧操作完成后，總有一個隊列是完全空的

按照上面的思路：

/**
 * Created by engineer on 2017/10/22.
 * <p>
 * 隊列實現(xiàn)棧
 */

public class Queue2Stack {


    private static class QStack<E> {
        private Deque<E> mEQueueA;
        private Deque<E> mEQueueB;


        private QStack() {
            mEQueueA = new LinkedList<E>();
            mEQueueB = new LinkedList<E>();
        }

        private int getSize() {
            return mEQueueA.size() + mEQueueB.size();
        }

        private void push(E e) {
            if (mEQueueA.isEmpty()) {
                mEQueueB.addLast(e);
            } else {
                mEQueueA.addLast(e);
            }
        }

        private E pop() throws Exception {
            if (mEQueueA.isEmpty() && mEQueueB.isEmpty()) {
                return null;
            }

            if (mEQueueA.isEmpty() && !mEQueueB.isEmpty()) {
                return swapDeque(mEQueueA, mEQueueB);
            } else if (mEQueueB.isEmpty() && !mEQueueA.isEmpty()) {
                return swapDeque(mEQueueB, mEQueueA);
            } else {
                //This should never happen
                throw new RuntimeException("At least One of Deque must be empty");
            }

        }

        private E swapDeque(Deque<E> A, Deque<E> B) {
            while (B.size() != 1) {
                //隊列B從隊頭出隊，壓入隊列A的尾部
                A.addLast(B.removeFirst());
            }
            //從隊列B隊頭返回最后的一個元素
            return B.removeFirst();

        }
    }

    public static void main(String[] args) throws Exception {
        QStack<String> mQStack = new QStack<>();

        mQStack.push("A");
        mQStack.push("b");
        System.out.println("棧頂元素pop:"+mQStack.pop());
        mQStack.push("B");
        mQStack.push("C");
        mQStack.push("D");
        System.out.println("棧頂元素pop:"+mQStack.pop());
        mQStack.push("E");

        int size = mQStack.getSize();
        System.out.printf("%d 個元素出棧：\n", size);
        for (int i = 1; i <= size; i++) {
            System.out.printf("第 %d 個出棧元素：%s\n", i, mQStack.pop());
        }
    }
}

得到輸出：

棧頂元素pop:b
棧頂元素pop:D
4 個元素出棧：
第 1 個出棧元素：E
第 2 個出棧元素：C
第 3 個出棧元素：B
第 4 個出棧元素：A

好了，這就是棧和隊列的相互實現(xiàn)。