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 queue2
					queue2.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 queue1
					queue1.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);//3
		stack.push(4);
		tmp=stack.pop();
		System.out.println(tmp);//4
		tmp=stack.pop();
		System.out.println(tmp);//2
		stack.push(5);
		stack.push(6);
		tmp=stack.pop();
		System.out.println(tmp);//6
		tmp=stack.pop();
		System.out.println(tmp);//5
		tmp=stack.pop();
		System.out.println(tmp);//1
	}
}

评论

2 楼 bylijinnan 2015-07-03  

sand_clock 写道

楼主代码有误：

两个队列实现一个栈
第一次push时你的代码会让第一个元素进栈2遍。
错误代码：
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 Integer push(Integer o){ 
        if(queue1.size()!=0){ 
            queue1.addLast(o); 
        }else if(queue2.size()!=0){ 
            queue2.addLast(o); 
        } 
        if(queue1.size()==0&&queue2.size()==0){ 
            queue1.addLast(o);//queue2.addLast(o); is also ok 
        } 
        return o; 
} 

不会啊，不会存在两个queue都不为空的情况

1 楼 sand_clock 2015-07-02  

楼主代码有误：

两个队列实现一个栈
第一次push时你的代码会让第一个元素进栈2遍。
错误代码：
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 Integer push(Integer o){ 
        if(queue1.size()!=0){ 
            queue1.addLast(o); 
        }else if(queue2.size()!=0){ 
            queue2.addLast(o); 
        } 
        if(queue1.size()==0&&queue2.size()==0){ 
            queue1.addLast(o);//queue2.addLast(o); is also ok 
        } 
        return o; 
}