当前位置:首页 > 开发 > 编程语言 > Java > 正文

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

发表于: 2012-03-11   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.ArrayList; import java.util.List; import java.util.Stack; /* * Q 57 用两个栈实现队列 */ public class QueueImplementByTwoStacks { private Stack<Integer> stack1; pr
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
	}
}

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目描述: 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 输入:
不必解释了吧,这里代码应该就能说明问题了 #include <iostream> #include <stack> #in
开始 再开始开始实现之前,首先将定读者已经理解了栈和队列的区别。 如果不理解的话,可以先看看这
1.题目:用两个栈实现一个队列的功能 template <typename T> class CQueue { public: CQueue(
惯例。看题: 题目:用两个栈实现一个队列。队列的声明如下。请实现它的两个函数appendTail和delete
原文:http://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html 两年前从网上看到
两年前从网上看到一道面试题:用两个栈(Stack)实现一个队列(Queue)。觉得不错,就经常拿来面试
两年前从网上看到一道面试题:用两个栈(Stack)实现一个队列(Queue)。觉得不错,就经常拿来面试
两年前从网上看到一道面试题:用两个栈(Stack)实现一个队列(Queue)。觉得不错,就经常拿来面试
(PS:可在《算法(第四版)》的1.3.49看到此题) 两年前从网上看到一道面试题:用两个栈(Stack)
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号