转自：http://bylijinnan.iteye.com/blog/1450125

————————————————————————————————————————————

Java代码  

1. import java.util.ArrayList;   
2. import java.util.List;   
3. import java.util.Stack;   
4.   
5.     /*  
6.      * Q 57 用两个栈实现队列  
7.      */  
8.   
9. public class QueueImplementByTwoStacks {   
10.   
11.     private Stack<Integer> stack1;   
12.     private Stack<Integer> stack2;   
13.        
14.     QueueImplementByTwoStacks(){   
15.         stack1=new Stack<Integer>();   
16.         stack2=new Stack<Integer>();   
17.     }   
18.        
19.     public Integer poll(){   
20.         Integer re=null;   
21.         if(!stack2.empty()){   
22.             re=stack2.pop();   
23.         }else{   
24.             while(!stack1.empty()){//move to stack2 to make stack1 have only one element.Then pop this element.   
25.                 re=stack1.pop();   
26.                 stack2.push(re);   
27.             }   
28.             if(!stack2.empty()){   
29.                 re=stack2.pop();   
30.             }   
31.         }   
32.         return re;   
33.     }   
34.     public Integer offer(int o){   
35.         stack1.push(o);   
36.         return o;   
37.     }   
38.        
39.     public static void main(String[] args) {   
40.         QueueImplementByTwoStacks queue=new QueueImplementByTwoStacks();   
41.         List<Integer> re=new ArrayList<Integer>();   
42.         queue.offer(1);   
43.         queue.offer(2);   
44.         queue.offer(3);   
45.         re.add(queue.poll());   
46.         queue.offer(4);   
47.         re.add(queue.poll());   
48.         queue.offer(5);   
49.         re.add(queue.poll());   
50.         re.add(queue.poll());   
51.         re.add(queue.poll());   
52.         System.out.println(re.toString());   
53.     }   
54.   
55. }  

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());	}}

Java代码  

1. import java.util.LinkedList;   
2.   
3.     /*  
4.      * Q 57 用两个队列实现一个栈  
5.      */  
6. public class StackImplementByTwoQueues {   
7.   
8.     //use ‘queue1‘ and ‘queue2‘ as a queue.That means only use the method ‘addLast‘ and ‘removeFirst‘.   
9.     private LinkedList<Integer> queue1;   
10.     private LinkedList<Integer> queue2;   
11.        
12.     StackImplementByTwoQueues(){   
13.         queue1=new LinkedList<Integer>();   
14.         queue2=new LinkedList<Integer>();   
15.     }   
16.        
17.     public Integer pop(){   
18.         Integer re=null;   
19.         if(queue1.size()==0&&queue2.size()==0){   
20.             return null;   
21.         }   
22.         if(queue2.size()==0){   
23.             while(queue1.size()>0){   
24.                 re=queue1.removeFirst();   
25.                 if(queue1.size()!=0){//do not add the last element of queue1 to queue2   
26.                     queue2.addLast(re);   
27.                 }   
28.             }   
29.         }else if (queue1.size()==0){   
30.             while(queue2.size()>0){   
31.                 re=queue2.removeFirst();   
32.                 if(queue2.size()!=0){//do not add the last element of queue2 to queue1   
33.                     queue1.addLast(re);   
34.                 }   
35.             }   
36.         }   
37.         return re;   
38.     }   
39.     public Integer push(Integer o){   
40.         if(queue1.size()==0&&queue2.size()==0){   
41.             queue1.addLast(o);//queue2.addLast(o); is also ok   
42.         }   
43.         if(queue1.size()!=0){   
44.             queue1.addLast(o);   
45.         }else if(queue2.size()!=0){   
46.             queue2.addLast(o);   
47.         }   
48.         return o;   
49.     }   
50.        
51.     public static void main(String[] args) {   
52.         StackImplementByTwoQueues stack=new StackImplementByTwoQueues();   
53.         int tmp=0;   
54.         stack.push(1);   
55.         stack.push(2);   
56.         stack.push(3);   
57.         tmp=stack.pop();   
58.         System.out.println(tmp);//3   
59.         stack.push(4);   
60.         tmp=stack.pop();   
61.         System.out.println(tmp);//4   
62.         tmp=stack.pop();   
63.         System.out.println(tmp);//2   
64.         stack.push(5);   
65.         stack.push(6);   
66.         tmp=stack.pop();   
67.         System.out.println(tmp);//6   
68.         tmp=stack.pop();   
69.         System.out.println(tmp);//5   
70.         tmp=stack.pop();   
71.         System.out.println(tmp);//1   
72.     }   
73. }  

java-57-用两个栈实现队列&&用两个队列实现一个栈