用两个栈实现一个队列思想和java编程实现

写在前面的声明:
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;
    }
}