栈和队列的相互实现

浅浅的花香味﹌ 2022-06-07 13:23 199阅读 0赞

## 前言 ##

栈和队列作为两种典型的线性表，有着非常鲜明甚至可以说是相互对立的特点；栈先进后出（后进先出），队列先进先出（后进后出）。因此，对相同的输入，两者会产生恰好截然相反的输出。例如，对于给定的序列”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

--------------------

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