题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
解题思路
1，用stack1来充当入队，将stack1所有元素出栈到stack2，然后stack2出栈，实现先进先出。
2，三种算法，一种比一种优化
/** * */ package 栈和队列; import java.util.Stack; /** * <p> * Title:StacktoQueue * </p> * <p> * Description: * </p> * * @author 田茂林 * @data 2017年8月22日 上午10:16:19 */ public class StacktoQueue { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); //==================================================普通方法=============================== public void push(int node) { stack1.push(node); } public int pop() { while(!stack1.isEmpty()){ stack2.push(stack1.pop()); //把stack1的所有元素入栈到2 } int num = stack2.pop(); //返回值为2出栈 while(!stack2.isEmpty()){ stack1.push(stack2.pop()); //把2中所有元素重新放回到1 } return num; //操作数过多 } //==================================================优化=============================== public void push1(int node) { stack1.push(node); } public int pop1() { while(stack1.size()>1){ stack2.push(stack1.pop()); //栈1里只剩一个元素，用于出栈 } int num = stack1.pop(); //栈1出栈 while(!stack2.isEmpty()){ //把剩下的元素重新放回栈1 stack1.push(stack2.pop()); } return num; } //==================================================更加优化=============================== public void push2(int node) { stack1.push(node); } public int pop2() { if(stack1.isEmpty()&&stack2.isEmpty()) throw new RuntimeException("queue is empty"); if(stack2.isEmpty()){ //只有栈2空的时候才把栈1的放进去，这样避免了频繁的操作 while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.pop(); } public static void main(String[] args) { // TODO Auto-dgenerated method stub } }
