Crackingcodinginterview(3.5)使用2个堆栈实现一个队列

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Crackingcodinginterview(3.5)使用2个堆栈实现一个队列，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2365字，纯文字阅读大概需要4分钟。

内容图文

3.5 Implement a MyQueue class which implements a queue using two stacks. explanation: 1.MyQueue实现原理：当MyQueue需要offer(add)一个元素时，直接添加到堆栈s1中即可，若要poll(remove)一个元素时，则需要借助堆栈s2，将s1中元素pop并且push到s2中，

3.5 Implement a MyQueue class which implements a queue using two stacks.

explanation:

1.MyQueue实现原理：当MyQueue需要offer(add)一个元素时，直接添加到堆栈s1中即可，若要poll(remove)一个元素时，则需要借助堆栈s2，将s1中元素pop并且push到s2中，此时s2栈顶元素即是对头元素。之后再将s2中元素pop并且push回s1中。

2.MyQueue2针对MyQueue的优化。堆栈s2中的元素不再回到s1.堆栈s1用于存放最新的push的元素，堆栈s2用于将堆栈s1中的现有元素反序，这样最先入队的几个元素都会在s2中。当MyQueue队列要弹出一个元素时，只需要从s2中弹出元素即可，若s2为空，则将s1中的最新的元素再次pop->push到s2。如此往复。

import java.util.Stack;

class MyQueue{
	private Stack s1 = new Stack();
	private Stack s2 = new Stack();
	//time complexity:O(1), space complexity:O(1)
	public boolean offer(int val){
		s1.push(val);
		return true;
	}
	//time complexity:O(n) space complexity:O(n)
	public int poll(){
		if(empty())
			return Integer.MIN_VALUE;
		else{
			while(!s1.empty())
				s2.push(s1.pop());
			int val = s2.pop().intValue();
			while(!s2.empty())
				s1.push(s2.pop());
			return val;
		}
	}
	public boolean empty(){		
		return s1.empty();
	}
}

//improvement for MyQueue
class MyQueue2{
	Stack s1 = new Stack();
	Stack s2 = new Stack();
	public boolean offer(int val){
		s1.push(val);
		return true;
	}
	//time complexity gradually reduced, most cases is O(1)
	public int poll(){
		if(s2.empty())
			while(!s1.empty())
				s2.push(s1.pop());
		if(s2.empty())
			return Integer.MIN_VALUE;
		else
			return s2.pop().intValue();	
	}
	public boolean empty(){
		if(s1.empty() && s2.empty())
			return true;
		else
			return false;
	
	}
}

public class Solution{
	public static void main(String[] args){
		//test for MyQueue
		MyQueue mq = new MyQueue();
		int i=0;
		for(;i < 20;i++)
			mq.offer(i);
		
		while(--i > 10 && !mq.empty())
			System.out.print(mq.poll()+" ");
		System.out.println();
		
		for(i=40;i < 50;i++)
			mq.offer(i);
			
		while(!mq.empty())
			System.out.print(mq.poll()+" ");
		System.out.println();	
		
		//test for MyQueue2
		MyQueue2 mq2 = new MyQueue2();
		for(i=100;i < 102;i++)
			mq2.offer(i);
			
		while(i-- != 101 &&!mq2.empty())
			System.out.print(mq2.poll()+" ");
		for(i=102;i < 120;i++)
			mq2.offer(i);
		
		while(!mq2.empty())	
			System.out.print(mq2.poll()+" ");
		System.out.println();
			
	}
}

内容总结

以上是互联网集市为您收集整理的Crackingcodinginterview(3.5)使用2个堆栈实现一个队列全部内容，希望文章能够帮你解决Crackingcodinginterview(3.5)使用2个堆栈实现一个队列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端