力扣 - 232. 用栈实现队列.md
2024-09-07 07:29:31
题目
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作(push、pop、peek、empty):
实现 MyQueue 类:
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空,返回 true ;否则,返回 false
说明:
- 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
进阶:
- 你能否实现每个操作均摊时间复杂度为 O(1) 的队列?换句话说,执行 n 个操作的总时间复杂度为 O(n) ,即使其中一个操作可能花费较长时间。
示例:
输入:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 1, 1, false]
解释:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示:
- 1 <= x <= 9
- 最多调用 100 次 push、pop、peek 和 empty
- 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)
思路
- 即然是使用两个栈,那么一个栈就用来做辅助栈,一个栈用来存元素
- 我们将栈顶作为队头,将栈底作为队尾,所以如果要push数据的话,先将stack1栈的数据暂时存到stack2辅助栈中,然后将要插入的数据push进入stack1,最后再将stack2的暂存的数据填回到stack1中(注意,回填元素时顺序不能乱)
- pop时,就是将栈的元素最后一个pop出去,由于我们将队头做为栈顶,所以stack1的pop其实就是出队操作
- empty:要判断队列是否为空,直接判断stack1是否为空即可
- 由于栈是基于LinkedList实现的,peek时即查看的是栈顶的元素,所以直接peek就是查看队头的元素
代码实现
import java.util.LinkedList;
class MyQueue {
LinkedList<Integer> stack1;
LinkedList<Integer> stack2;
public MyQueue() {
stack1 = new LinkedList<>();
stack2 = new LinkedList<>();
}
public void push(int x) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
stack1.push(x);
while (!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
}
public int pop() {
return stack1.pop();
}
public int peek() {
return stack1.peek();
}
public boolean empty() {
return stack1.isEmpty();
}
}
复杂度分析
- 时间复杂度:
- push: \(O(N)\)
- pop: \(O(1)\)
- peek: \(O(1)\)
- empty: \(O(1)\)
- 空间复杂度:\(O(N)\)
最新文章
- tomcat 的优化配置
- scala数组
- HTML5 常用的结构化标签整理
- ASP.NTE 5 Target framework dnx451 and dnxcore50(转)原文:http://www.cnblogs.com/xishuai/p/aspnet5-target-framework-dnx451-and-dnxcore50.html
- mongo语句优化分析
- 字符编码的过滤器Filter(即输入的汉字,能在页面上正常显示,不会出现乱码)
- All_从PO - INV - AP - SLA - GL重要数据表和接口程式(概念)
- 用Servlet实现聊天室设计
- 通过配置Tomcat,让Android真机通过局域网访问PC的文件
- 芝麻HTTP:在阿里云上测试Gerapy教程
- 进阶!基于CentOS7系统使用cobbler实现单台服务器批量自动化安装不同版本系统(week3_day5_part2)-技术流ken
- python打包--pyinstaller打包报错
- Java读取文件-BufferedReader/FileReader/InputStreamReader/FileInputStream的关系和区别
- flex布局下, 内容改变 不重新渲染问题
- jsp的9大内置对象和4大作用域
- AWK用法整理
- android上进行c/C++开发测试(转)
- 一款纯css3实现的颜色渐变按钮
- C#生成Excel
- MWeb Lite以及Eclipse的使用感想
热门文章
- 排序算法:冒泡排序(Bubble Sort)
- 074 01 Android 零基础入门 01 Java基础语法 09 综合案例-数组移位 06 综合案例-数组移位-主方法功能3的实现
- 023 01 Android 零基础入门 01 Java基础语法 03 Java运算符 03 算术运算符之——自增自减运算符
- 跟我一起学Redis之五种基本类型及其应用场景举例(干了6个小时)
- MonkeyRunner+Python自动化测试一
- S3C6410中断系统
- linunx常用命令综合
- Hybrid App中原生页面 VS H5页面
- 【C语言学习笔记】C语言函数执行成功时,返回1和返回0,究竟哪个好?
- 第一期chrome浏览器的小技巧------《提高搜索效率》