栈和队列的相互实现

前言

栈和队列作为两种典型的线性表，有着非常鲜明甚至可以说是相互对立的特点；栈先进后出（后进先出），队列先进先出（后进后出）。因此，对相同的输入，两者会产生恰好截然相反的输出。例如，对于给定的序列"ABCDE",如果按照字母顺序将这个5个元素依次入栈，然后再依次出栈，那么得到的输出将是"EDCBA",而如果将5个元素意思压入队列，然后依次弹出，那么得到的输出将是"ABCDE"。

正是因为这种截然相对的输出，使得他们彼此之间有了更多的联系；使得他们之间可以相互实现对方。就是说我们可以用栈模拟出队列的输出，同样也可以用队列模拟出栈的输出。下面就来看看。

栈实现队列

先说容易理解也是大家最容易想到实现方式的：用两个栈实现一个队列。

现在有栈Stack1和栈Stack2，假设现在输入序列"ABCDE"已经依次压入到栈Stack1，A处于栈底，E处于栈顶，那么怎样才可以得到输出序列也为“ABCDE"呢，我们很容易想到，把栈Stack1倒过来就可以了，那么怎样倒过来呢？这时候就要借助Stack2，我们把Stack1的内容依次弹出，然后再依次压入到Stack2不就相当于把Stack1 倒过来了吗？这时候Stack2 依次弹出，输出序列就是队列形式了。总结一下：

• 入栈只进栈Stack1
• 出栈时，如果Stack2 不为空，则直接从Stack2弹出；如果Stack2 为空，则把Stack1的内容依次弹出，并压入Stack2，然后从Stack2弹出栈顶元素。

原理很简单，实现起来也不难：

/**
 * Created by engineer on 2017/10/22.
 * <p>
 * 用栈实现队列
 */

public class Stack2Queue {


    private static class SQueue<E> {
        //只负责进栈元素
        private Stack<E> mTStackA;
        //负责中转
        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

用队列实现栈

有了上面的经验，我们可以再想想怎样用两个队列实现栈呢？其实，思路或者说是原理，都是一样，就是利用两个容器，实现数据的翻转，假设现有队列DequeA和DequeB;刚开始两个队列都为空，现有输入序列"ABCDE"，有元素A要入队，那么这个时候，可以随机一个队列使用，假设我们选队列DequeB,元素A进入队列DequeB,接着元素B,C,D进入队列DequeB,这个时候，如果要求有元素输出，如果直接从队列DequeB头部输出元素，那么就不符合栈后进先出的原则，此时，需要输出的元素是D,而他此时在队列DequeB的尾部，因此为了输出他，必须把他前面的ABC拿走，拿走的元素放在哪里呢？队列DequeA恰好是空的，放进去就好了。此时，队列DequeB中只有一个B,让他出队列就好了，最后队列DequeB空了。接着E要入队，此时他应该放在哪里呢？应该放入队列DequeA中。同样，此时需要输出了，再次按照刚才的思路，把队列DequeA 中除了E之外的所有元素放入队列DequeB中，这样以此类推，就实现了栈的输出。总结一下：

• 当两个队列都为空时，有元素需要插入时，任选一个插入即可。
• 当需要元素出栈时，从非空队列中，除了最后一个处于队尾的元素之外，其余元素都压入到另一个空队列中，并从队列中弹出最后一个元素
• 每次入栈、出栈操作完成后，总有一个队列是完全空的

按照上面的思路：

/**
 * Created by engineer on 2017/10/22.
 * <p>
 * 队列实现栈
 */

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

---

好了，这就是栈和队列的相互实现。