java-57-用两个栈实现队列&&用两个队列实现一个栈
import java.util.ArrayList;import java.util.List;import java.util.Stack;/* * Q 57 用两个栈实现队列 */public class QueueImplementByTwoStacks {private Stack<Integer> stack1;private Stack<Integer> stack2;QueueImplementByTwoStacks(){stack1=new Stack<Integer>();stack2=new Stack<Integer>();}public Integer poll(){Integer re=null;if(!stack2.empty()){re=stack2.pop();}else{while(!stack1.empty()){//move to stack2 to make stack1 have only one element.Then pop this element.re=stack1.pop();stack2.push(re);}if(!stack2.empty()){re=stack2.pop();}}return re;}public Integer offer(int o){stack1.push(o);return o;}public static void main(String[] args) {QueueImplementByTwoStacks queue=new QueueImplementByTwoStacks();List<Integer> re=new ArrayList<Integer>();queue.offer(1);queue.offer(2);queue.offer(3);re.add(queue.poll());queue.offer(4);re.add(queue.poll());queue.offer(5);re.add(queue.poll());re.add(queue.poll());re.add(queue.poll());System.out.println(re.toString());}}import java.util.LinkedList;/* * Q 57 用两个队列实现一个栈 */public class StackImplementByTwoQueues {//use 'queue1' and 'queue2' as a queue.That means only use the method 'addLast' and 'removeFirst'.private LinkedList<Integer> queue1;private LinkedList<Integer> queue2;StackImplementByTwoQueues(){queue1=new LinkedList<Integer>();queue2=new LinkedList<Integer>();}public Integer pop(){Integer re=null;if(queue1.size()==0&&queue2.size()==0){return null;}if(queue2.size()==0){while(queue1.size()>0){re=queue1.removeFirst();if(queue1.size()!=0){//do not add the last element of queue1 to queue2queue2.addLast(re);}}}else if (queue1.size()==0){while(queue2.size()>0){re=queue2.removeFirst();if(queue2.size()!=0){//do not add the last element of queue2 to queue1queue1.addLast(re);}}}return re;}public Integer push(Integer o){if(queue1.size()==0&&queue2.size()==0){queue1.addLast(o);//queue2.addLast(o); is also ok}if(queue1.size()!=0){queue1.addLast(o);}else if(queue2.size()!=0){queue2.addLast(o);}return o;}public static void main(String[] args) {StackImplementByTwoQueues stack=new StackImplementByTwoQueues();int tmp=0;stack.push(1);stack.push(2);stack.push(3);tmp=stack.pop();System.out.println(tmp);//3stack.push(4);tmp=stack.pop();System.out.println(tmp);//4tmp=stack.pop();System.out.println(tmp);//2stack.push(5);stack.push(6);tmp=stack.pop();System.out.println(tmp);//6tmp=stack.pop();System.out.println(tmp);//5tmp=stack.pop();System.out.println(tmp);//1}}