LeetCode 232:用栈实现队列 Implement Queue using Stacks
题目:
使用栈实现队列的下列操作:
- push(x) -- 将一个元素放入队列的尾部。
- pop() -- 从队列首部移除元素。
- peek() -- 返回队列首部的元素。
- empty() -- 返回队列是否为空。
Implement the following operations of a queue using stacks.
- push(x) -- Push element x to the back of queue.
- pop() -- Removes the element from in front of queue.
- peek() -- Get the front element.
- empty() -- Return whether the queue is empty.
示例:
MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false
说明:
- 你只能使用标准的栈操作 -- 也就是只有
push to top
,peek/pop from top
,size
, 和is empty
操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
- 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。
Notes:
- You must use only standard operations of a stack -- which means only
push to top
,peek/pop from top
,size
, andis empty
operations are valid. - Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
- You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
解题思路:
队列先进后出,栈后进先出。用栈实现队列,可以用两个栈完成题解。入队列时用 stack1 存入节点,出队列时 stack1 内节点顺序出栈压入 stack2 中。
例如 1, 2, 3 元素顺序入队列 即存入栈stack1:[1, 2, 3] 出队列时顺序应为:1->2->3 但是栈先进先出,出栈顺序为:3->2->1 与出队列顺序不相符 借助另一个栈stack2 stack1内的元素顺序出栈并压入stack2 stack1:[1, 2, 3] ---> stack2:[3, 2, 1] 此时stack2出栈顺序:1->2->3 与出队列顺序相符
注意:在出队列时无需着急将 stack1 中的节点顺序压入 stack2。因为要实现的队列是先进后出,可以将 stack2 中的节点全部弹出之后 再将 stack1 内节点顺序压入stack2,这样可以将出栈的时间复杂度摊还到 O(1)。
Java:
class MyQueue { private Stack<Integer> stack1; private Stack<Integer> stack2; public MyQueue() { stack1 = new Stack<>(); stack2 = new Stack<>(); } public void push(int x) { stack1.push(x); } public int pop() { if (stack2.isEmpty()) { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } } return stack2.pop(); } public int peek() { //stack1节点顺序弹出并压入stack2 if (stack2.isEmpty()) {//条件是: stack2为空,而不是stack1非空, 这样摊还复杂度O(1) while (!stack1.isEmpty()) { stack2.push(stack1.pop());//stack1弹出节点并压入stack2 } } return stack2.peek(); } public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); } }
Python:
Python语言没有栈和队列数据结构,只能用数组 List 或双端队列 deque 实现。
这类编程语言就压根不需要 用队列实现栈或用栈实现队列这种问题,因为栈和队列本身就必须借助List、deque实现。
所以这道题在这种语言中这就非常简单了,可以说是作弊。
class MyQueue: def __init__(self): self.queue = [] def push(self, x: int) -> None: self.queue.append(x) def pop(self) -> int: #弹出第一个元素 return self.queue.pop(0) def peek(self) -> int: #返回第一个元素 return self.queue[0] def empty(self) -> bool: return not self.queue
欢迎关注微.信公.众号:爱写Bug
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Java多线程之Executor框架:Callable、Future、Executor和ExecutorService
引言 Executor框架是指JDK 1.5中引入的一系列并发库中与Executor相关的功能类,包括Executor、Executors、ExecutorService、Future、Callable等。 一、为什么要引入Executor框架? 1、如果使用new Thread(...).start()的方法处理多线程,有如下缺点: 开销大。对于JVM来说,每次新建线程和销毁线程都会有很大的开销。 线程缺乏管理。没有一个池来限制线程的数量,如果并发量很高,会创建很多线程,而且线程之间可能会有相互竞争,这将会过多占用系统资源,增加系统资源的消耗量。而且线程数量超过系统负荷,容易导致系统不稳定。 2、使用线程池的方法,有如下优点: 线程复用。通过复用创建了的线程,减少了线程的创建、消亡的开销。 有效控制并发线程数。 提供了更简单灵活的线程管理。可以提
- 下一篇
LeetCode 739:每日温度 Daily Temperatures
题目: 根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。 例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。 Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead. For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output s...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS7,CentOS8安装Elasticsearch6.8.6
- SpringBoot2初体验,简单认识spring boot2并且搭建基础工程
- CentOS6,CentOS7官方镜像安装Oracle11G
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- 设置Eclipse缩进为4个空格,增强代码规范
- Mario游戏-低调大师作品
- MySQL8.0.19开启GTID主从同步CentOS8