写在前面的声明:
1,栈是先入后出的数据结构(就像将书装入箱子，压箱底的书总是要最后才能取出来)
2,队列是先入先出的数据结构(就像排队买票，先排队的先买票，后来的后买)
小白版
- 初始化两个栈S1和S2。
- S1作为元素的存储空间，S2作为数据的临时缓冲区
-
入队的时候，将数据压入栈S1中 -
出队的时候，将S1中的元素依次出栈，并且压入栈S2中，然后将S2中的栈顶元素出栈。 -
出队之后，将S2中的数据元素倒回到栈S1中
Paste_Image.png
升级版
入队时，先判断S1是否为空，如不为空，说明所有元素都在S1，此时将入队元素直接压入S1；如为空，要将S2的元素逐个“倒回”S1，再压入入队元素。出队时，先判断S2是否为空，如不为空，直接弹出S2的顶元素并出队；如为空，将S1的元素逐个“倒入”S2，把最后一个元素弹出并出队。
这种升级版可以在每次出队之后不用将栈S2中的元素倒回到栈S1中，对于频繁的出队操作效率更高。
大师版
-
入队时，将元素压入s1。 -
出队时，判断s2是否为空，如不为空，则直接弹出顶元素；如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。
这个大师版，避免了反复“倒”栈，仅在需要时才“倒”一次
java实现如下
import java.util.Stack;
public class StackToQueue {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
//入对的时候将数据元素压入栈S1中
stack1.push(node);
}
public int pop() {
//如果S1不为空，将S1出栈的元素一次入栈到S2中
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
//将S2的栈顶元素出栈，即出队。
int first=stack2.pop();
//如果S2不为空，将S2中的元素出栈，然后入栈到S1中
while(!stack2.isEmpty()){
stack1.push(stack2.pop());
}
return first;
}
}
