分析
栈的特性后入先出，队列的特性是先入先出，要用栈去实现一个队列，就要思考如果将一个栈转换成队列的特性。
举个例子：
依次将 1、2、3、4、5入栈，出栈的话，顺序应该是：5、4、3、2、1。
依次将 1、2、3、4、5入队，出队的话，顺序应该是：1、2、3、4、5。
思路：其实这个问题非常简单了，因为已经限定了条件，只能使用栈这个数据结构来实现队列，一个栈的话不能满足条件，又没有别的数据结构来辅助，那么唯一能尝试的办法就是再加一个栈试试咯～
那么现在我们有两个栈，分别为 inStack 和 outStack，首先inStack依次入栈1、2，然后inStack依次出栈2、1，再按照出栈顺序将2、1入栈outStack：2、1，有没有发现，outStack正好将inStack反过来，outStack的出栈顺序是1、2，刚好满足了队列的性质。
现在再来考虑出栈后再次入栈的情况：
1、2入队，先取出队头1，然后入队3，再依次全部出队：2、3。
// 将1、2入栈inStack
inStack：top>>2>>1
outStack: top>>
// 要去修1，需要将inStack全部依次入栈outStack
inStack:top>>
outStack: top>>1>>2
// 然后从outStack栈顶出栈1
inStack:top>>
outStack: top>>2
// 现在需要入栈3
inStack:top>>3
outStack: top>>2
// 现在取出2
inStack:top>>3
outStack: top>>
//取出3需要先将inStack入栈outStack
inStack:top>>
outStack: top>>3
//outStack栈顶出栈3
inStack:top>>
outStack: top>>3
由此可见栈实现队列的流程就是，入队只需要将向inStack栈顶加入元素，出队时，如果outStack为空，就将inStack依次出栈并入栈outStack。然后从outStack栈顶取出元素，如果outStack不为空，直接取出元素。
Java实现
// 用栈实现一个队列
package test;
public class QueueWithStack<E> {
// 使用两个栈来实现一个队列
// 入队时，向inStack入栈一个元素
private Stack<E> inStack = new Stack<E>();
// 出队时，从outStack出栈一个元素
private Stack<E> outStack = new Stack<E>();
// 关键逻辑，当需要出队或者查看队头元素时，先查看outStack是否有值，第一次肯定是空的
// 这时将inStack的元素全部依次出栈并入栈到outStack后，outStack就是反向放置了inStack的元素
// 此时outStack出栈的元素顺序刚好就是之前inStack的入栈顺序
// 当需要出队时，如果outStack不为空，那么直接从outStack出栈
private void checkStack() {
if (outStack.isEmpty()) {
while(inStack.isEmpty() == false) {
outStack.push(inStack.pop());
}
}
}
// 两个栈的数据数量相加是队列的数据数量
public int sise() {
return inStack.size() + outStack.size();
}
// 两个栈都为空队列为空
public boolean isEmpty() {
return inStack.isEmpty() && outStack.isEmpty();
}
// 入队就是在链表尾部添加元素
public void enQueue(E element) {
inStack.push(element);
}
// 出队就是删除链表头部元素
public E deQueue() {
checkStack();
return outStack.pop();
}
// 获取队头就是获取链表头部元素
public E front() {
checkStack();
return outStack.peek();
}
}
其他语言
很多语言不像Java直接有Stack这种包装好的对象来实现一个栈或者队列的数据结构的功能，不过这也不妨碍在其他语言来实现这个功能。
栈和队列本质上就是一个弱化了功能的可以动态添加和删除元素的数组，对外隐藏了可以通过下标向任意位置插入和取出元素的接口，只能操作头尾。
入栈是向队列尾部添加一个元素，出栈是移除队列尾部的元素。
入队是向队列尾部添加一个元素，出队是移除队列头部的元素。
Objective-C模拟一个栈：
// 初始化一个栈
NSMutableArray *stack = [NSMutableArray array];
// 入栈
[stack addObject:root];
// 获取栈顶元素
id top = [stack lastObject];
// 出栈
[stack removeLastObject];
Objective-C模拟一个队列：
// 初始化一个队列
NSMutableArray *queue = [NSMutableArray array];
// 入队
[queue addObject:root];
// 获取队头元素
id top = [queue firstObject];
// 出队
[queue removeObjectAtIndex:0];
通过上面这些代码，Objective-C也可以模拟完成上面的算法。
网友评论