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