栈和队列的相互实现
前言
栈和队列作为两种典型的线性表，有着非常鲜明甚至可以说是相互对立的特点；栈先进后出（后进先出），队列先进先出（后进后出）。因此，对相同的输入，两者会产生恰好截然相反的输出。例如，对于给定的序列”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出队列:b3 个元素出队：BCD
用队列实现栈
有了上面的经验，我们可以再想想怎样用两个队列实现栈呢？其实，思路或者说是原理，都是一样，就是利用两个容器，实现数据的翻转，假设现有队列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 happenthrow 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:D4 个元素出栈：第 1 个出栈元素：E第 2 个出栈元素：C第 3 个出栈元素：B第 4 个出栈元素：A
好了，这就是栈和队列的相互实现。
Dear 丶
╰+哭是因爲堅強的太久メ
深藏阁楼爱情的钟
系统管理员
Bertha 。
还没有评论，来说两句吧...