栈/队列 互相模拟实现
【摘要】 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路：大概这么想：用一个辅助栈把进第一个栈的元素倒一下就好了。
比如进栈1，2，3，4，5
第一个栈：
5
4
3
2
1
然后倒到第二个栈里
1
2
3
4
5
再倒出来，顺序为1，2，3，4，5
实现队列
然后要注意的事情：
1）栈2非空不能往里面倒数...
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路：大概这么想：用一个辅助栈把进第一个栈的元素倒一下就好了。
比如进栈1，2，3，4，5
第一个栈：
5
4
3
2
1
然后倒到第二个栈里
1
2
3
4
5
再倒出来，顺序为1，2，3，4，5
实现队列
然后要注意的事情：
1）栈2非空不能往里面倒数，顺序就错了。栈2没数再从栈1倒。
2）栈1要倒就一次倒完，不倒完的话，进新数也会循序不对。
-
import java.util.Stack;
-
-
public class Solution {
-
Stack<Integer> stack1 = new Stack<Integer>();
-
Stack<Integer> stack2 = new Stack<Integer>();
-
-
public void push(int node) {
-
stack1.push(node);
-
}
-
-
public int pop() {
-
if(stack1.empty()&&stack2.empty()){
-
throw new RuntimeException("Queue is empty!");
-
}
-
if(stack2.empty()){
-
while(!stack1.empty()){
-
stack2.push(stack1.pop());
-
}
-
}
-
return stack2.pop();
-
}
-
}
用两个队列实现栈，要求同上：
这其实意义不是很大，有些数据结构书上甚至说两个队列不能实现栈。
其实是可以的，只是时间复杂度较高，一个弹出操作时间为O(N)。
思路：两个队列，编号为1和2.
进栈操作：进1号队列
出栈操作：把1号队列全弄到2号队列里，剩最后一个别压入，而是返回。
最后还得把1和2号换一下，因为现在是2号有数，1号空。
仅仅有思考价值，不实用。
比如压入1，2，3
队列1：1，2，3
队列2：空
依次弹出1，2，3：
队列1里的23进入2号，3弹出
队列1：空
队列2：2，3
队列2中3压入1号，2弹出
队列1：3
队列2：空
队列1中只有一个元素，弹出。
上代码：
-
public class TwoQueueImplStack {
-
Queue<Integer> queue1 = new ArrayDeque<Integer>();
-
Queue<Integer> queue2 = new ArrayDeque<Integer>();
-
//压入
-
public void push(Integer element){
-
//都为空，优先1
-
if(queue1.isEmpty() && queue2.isEmpty()){
-
queue1.add(element);
-
return;
-
}
-
//1为空，2有数据，放入2
-
if(queue1.isEmpty()){
-
queue2.add(element);
-
return;
-
}
-
//2为空，1有数据，放入1
-
if(queue2.isEmpty()){
-
queue1.add(element);
-
return;
-
}
-
}
-
//弹出
-
public Integer pop(){
-
//两个都空，异常
-
if(queue1.isEmpty() && queue2.isEmpty()){
-
try{
-
throw new Exception("satck is empty!");
-
}catch(Exception e){
-
e.printStackTrace();
-
}
-
}
-
//1空，2有数据，将2中的数据依次放入1，最后一个元素弹出
-
if(queue1.isEmpty()){
-
while(queue2.size() > 1){
-
queue1.add(queue2.poll());
-
}
-
return queue2.poll();
-
}
-
-
//2空，1有数据，将1中的数据依次放入2，最后一个元素弹出
-
if(queue2.isEmpty()){
-
while(queue1.size() > 1){
-
queue2.add(queue1.poll());
-
}
-
return queue1.poll();
-
}
-
-
return (Integer)null;
-
}
-
//测试
-
public static void main(String[] args) {
-
TwoQueueImplStack qs = new TwoQueueImplStack();
-
qs.push(2);
-
qs.push(4);
-
qs.push(7);
-
qs.push(5);
-
System.out.println(qs.pop());
-
System.out.println(qs.pop());
-
-
qs.push(1);
-
System.out.println(qs.pop());
-
}
-
}
文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。
原文链接：fantianzuo.blog.csdn.net/article/details/82740895
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）