用两个栈来实现队列

题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

具体实现

解法一

解题思路：入队的时候先把所有的数据都压栈在stack1中，调用出队的方法时，循环出栈把stack1中的数据依次压栈到stack2中，此时的stack2的栈顶就是要出队的数据，用t来保存等下返回，最后再把stack2的数据又压回stack1即可。

Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { stack1.push(node);//入队就全入栈到stack1 } public int pop() { //把stack1出栈，然后入栈到stack2中 while(!stack1.empty()) { stack2.push(stack1.pop()); } int t = stack2.pop();//t要出队的结果 while(!stack2.empty()) {//将stack2中剩下的数据压回stack1 stack1.push(stack2.pop()); } return t; }

解法二

解题思路：和一差不多，主要就是关键点那里的if判断解决的解法一出队后还需压栈回去的问题

Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { stack1.push(node); } public int pop() { if(stack1.empty()&&stack2.empty()){ throw new RuntimeException("Queue is empty!"); } //关键点：这个if判断解决了之前需要把数据再压回栈1的问题。 //当栈2空了才需要从栈1出栈数据压到栈2 if(stack2.empty()){ while(!stack1.empty()){ stack2.push(stack1.pop()); } } return stack2.pop(); }