题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
while(!stack2.isEmpty()){
stack1.push(stack2.pop());
}
stack1.push(node);
}
public int pop() {
while (!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
首先我们得清楚stack1和stack2,他们两个栈由于两个方法 public void push(int node)和public int pop()的原因只有其中一个栈是有数据的,另外一个栈肯定为空,如果不太理解的话继续往下看:
假设两个栈刚开始都没有数据,刚开始执行 public void push(1),这样的话stack1就有了第一条数据(第一次没有执行while,因为stack2为空),第二继续public void push(2),stack2没有数据继续压栈到stack1中,继续 public void push(3), public void push(4)进行压栈,现在stack1有数据,stack2没有数据,stack1的栈中数据如下图所示:
现在调用public int pop()的方法,由于stack1现在有数据,进入到while语句中,将stack1的数据取出来放入到stack2中,stack2中的数据如下图所示:
然后在执行stack2.pop (),取出来的就是我们第一个进去的1了,实现了队列的先进先出;现在stack2中数据如下图所示:
到现在分析还没有结束,很多人现在会以为push的while形同摆设,在我们先前push的时候没有起到任何作用,但是现在当stack2有数据的时候就很有用了,我们继续往下分析;
现在我们又回到push里面 public void push(5),现在stack2是有数据的,执行while语句,stack1内的数据如图所示:
有没有发现,它现在又变回了一个栈的排列了,O(∩_∩)O哈哈~
stack1.push(5);之后,stack1的数据如图所示:
其实最终的思想就是,stack1这个栈的作用就是以栈方式存储数据,然后stack2的作用就是以队列的方式来取数据.
代码不足的地方:在public int pop()的时候最好对stack2进行非空判断,以免出现stack2取null;该算法思想简单,导致其时间复杂度为(n),暂时没有想到更优的解法.
Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。
它的内容包括：
- 大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
- 原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
- 持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
- 覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
- 不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
- 宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
- 宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
- 宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw
目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：
想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询
同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】 即可免费领取。
