在学习数据结构的过程当中,我们会学到栈和队列,在本篇文章中,重点讲解的是队列实现栈,在上篇文章中已经简单介绍过栈和队列的使用说明,以及栈实现队列。(2条消息) 数据结构/栈实现队列_Y君的进化史的博客-CSDN博
关于一个队列的简单使用方式:
关于一个栈的简单使用方式:
很显然一个队列无法实现栈,我们使用两个队列:
此时思路依旧很难被想到,我们跌倒一个队列试试:
我们可以发现,使用一个队列入栈,另一个出栈可以实现我们的想法。
例如:
当第一个队列全部往第二个队列中输入时,最后一个元素即为出栈的第一个元素;当需要第二个出栈的元素时,再将不为空的队列往另一个空队列输入元素,末尾元素即为出栈元素;几次往返即可实现栈。
代码:
import java.util.LinkedList;
import java.util.Queue;
class MyStack {
Queue<Integer> stack1;
Queue<Integer> stack2;
public MyStack() {
stack1 = new LinkedList<>();
stack2 = new LinkedList<>();
}
public void push(int x) {
if(!stack1.isEmpty()){
stack1.offer(x);
}else{
stack2.offer(x);
}
}
public int pop() {
int x = 0;
if(!stack1.isEmpty()){
x = stack1.poll();
while(!stack1.isEmpty()){
stack2.offer(x);
x = stack1.poll();
}
}else if(!stack2.isEmpty()){
x = stack2.poll();
while(!stack2.isEmpty()){
stack1.offer(x);
x = stack2.poll();
}
}
return x;
}
public int top() {
int x = 0;
if(!stack1.isEmpty()){
x = stack1.poll();
while(!stack1.isEmpty()){
stack2.offer(x);
x = stack1.poll();
}
stack2.offer(x);
}else if(!stack2.isEmpty()){
x = stack2.poll();
while(!stack2.isEmpty()){
stack1.offer(x);
x = stack2.poll();
}
stack1.offer(x);
}
return x;
}
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}
关于队列实现栈,以上就是今天的内容,本文仅仅简单介绍了一下。
如果有小伙伴要写题测试自己的代码是否正确,可以点击下方力扣链接:
这篇博客如果对你有帮助,给博主一个免费的点赞以示鼓励,欢迎各位🔎点赞👍评论收藏⭐,谢谢!!!
如果有什么疑问或不同的见解,欢迎评论区留言哦。