当前位置: 首页 > news >正文

5.2用队列实现栈(LC225-E)

算法:

其实这道题不用像上一道题一样,用两个队列实现栈。

由于队列的数据结构特性。用一个队列就可实现栈。

难点还是在出队的时候:

  • 比如队列=[1,2,3],要模拟一个栈
  • 入栈就是直接append(其实就是C++中的push)
  • 出栈时应该先出3,但是队列先出1
  • 此时可以先把1取出来,再加入队列,即[2,3,1]
  • 再把2取出来,再加入队列,即[3,1,2]
  • 这个时候再取出队首3,也就模拟了出栈操作。

总结:

只要将队列首部的元素(除了最后一个元素外) 重新添加到队列尾部,此时再去弹出元素就是栈的顺序了。

为什么用栈实现队列的时候要用两个栈?

因为栈底部是密封的,只有上面敞口;而队列前后都敞口。

所以队列可以实现“先从队首把1取出来,再加入队列”的操作,而栈要取数只能从最上面敞口的地方取。

Top算法:

对于 Python 中的序列类型(如列表、元组、字符串等),可以使用负数索引来访问元素。负数索引表示从序列的末尾开始计数,-1 表示最后一个元素,-2 表示倒数第二个元素,依此类推。

可以使用负数索引来访问队列的最后一个元素,如self.que[-1]。

调试过程:

 Python普通的Queue或SimpleQueue没有类似于peek的功能
        也无法用索引访问,在实现top的时候较为困难。

        用list可以,但是在使用pop(0)的时候时间复杂度为O(n)
        因此这里使用双向队列,我们保证只执行popleft()和append(),因为deque可以用索引访问,可以实现和peek相似的功能

class MyStack:def __init__(self):self.que = deque()def push(self, x: int) -> None:self.que.append(x)def pop(self) -> int:if self.empty():return Noneelse:for i in range(len(self.que)-1):self.que.append(self.que.pop())return self.que.pop()def top(self) -> int:if self.empty():return Noneelse:return self.que[-1]def empty(self) -> bool:return self.que# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

原因:

因为我的 `empty` 方法返回的是一个 `deque` 对象,而预期的返回类型是布尔值。

为了解决这个问题,可以将 `empty` 方法中的返回语句修改为 `return not self.que`。这样,如果队列为空,返回 `True`,否则返回 `False`

正确代码:

class MyStack:def __init__(self):self.que = deque()def push(self, x: int) -> None:self.que.append(x)def pop(self) -> int:if self.empty():return Noneelse:for i in range(len(self.que)-1):self.que.append(self.que.pop())return self.que.pop()def top(self) -> int:if self.empty():return Noneelse:return self.que[-1]def empty(self) -> bool:return not self.que

优化:

Top里面的que[-1]实际上用到了栈,因为直接获取了que的末尾元素。

其实可以类似pop函数,将队列首部的元素(除了最后一个元素外) 重新添加到队列尾部,此时再去弹出的元素就是栈的首了

不过要把这个“栈首”再加回队列里面,因为top不改变栈。

  • 比如队列=[1,2,3],要模拟一个栈
  • 出栈时应该先出3,但是队列先出1
  • 此时可以先把1取出来,再加入队列,即[2,3,1]
  • 再把2取出来,再加入队列,即[3,1,2]
  • 这个时候再取出队首3,也就是top,将其弹出
  • 再把这个3加入队列,即[1,2,3]。其实没有改变栈的内容。
class MyStack:def __init__(self):self.que = deque()def push(self, x: int) -> None:self.que.append(x)def pop(self) -> int:if self.empty():return Noneelse:for i in range(len(self.que)-1):self.que.append(self.que.pop())return self.que.pop()def top(self) -> int:if self.empty():return Noneelse:for i in range(len(self.que)-1):self.que.append(self.que.pop())temp = self.que.pop()self.que.append(temp)return tempdef empty(self) -> bool:return not self.que# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

相关文章:

5.2用队列实现栈(LC225-E)

算法: 其实这道题不用像上一道题一样,用两个队列实现栈。 由于队列的数据结构特性。用一个队列就可实现栈。 难点还是在出队的时候: 比如队列[1,2,3],要模拟一个栈入栈就是直接append(其实就是C中的push&#xff0…...

项目上线前发现严重Bug怎么办?

今天分享一个面试问题,现在有一个面试场景: 项目计划明天发布,但是在今天你作为测试人员发现了一个严重的bug,市场相关人员又在催发布的事情,这个时候你应该怎么办? 这是测试工程师不管是在面试&#xff0…...

【WPF系列】- Application详解

【WPF系列】- Application详解 文章目录 【WPF系列】- Application详解一、Application简介Application 类具体有以下功能: 二、初始App.xaml二、自定义Main方法启动WPF应用程序第一种:启动应用程序的代码第二种:启动应用程序的代码第三种:启…...

常见的内置方法:__call__,__getitem__,__iter__,__next__

1.__call__方法 在创建好一个实例后,直接调用一个实例会报错。但使用__call__后,可以让这个实例可以像方法一样被调用(就是一个函数后面加个括号的函数调用形式) class Person:passp1 Person() p1() # 实例这样无法直接被调…...

python用cv2画图(line, rectangle, text等)

Python做图像图形研究的时候,通常需要画很多辅助几何形状(比如bounding box等)。基于opencv的几何图形绘制具有易用性,而且天然能和numpy数组交互。 本文总结了几种常用的cv2画几何图形的方法,当一个简易的手册使用&a…...

解决方案中word中分页符的使用

在投标方案中要善于使用“分页符”,尽可能少使用分节符号,没有分页符前,你每次修改你的标书或者文件,增加或者修改内容后。你的格式字段前后都是会发生变化,如何稳定的保证结构呢,那就是分页符的使用&#…...

ubuntu20.04下apache启用php7.4-fpm

默认的apache不解析php文件: 直接安装提示依赖有问题: libapache2-mod-php7.4 : Depends: php7.4-common ( 7.4.3-4ubuntu2.19) but 1:7.4.33-8ubuntu20.04.1deb.sury.org1 is to be installed rootfv-az1492-145:/tmp# sudo apt install libapache2-…...

在 CentOS 服务器上部署 JAR 文件到 Docker 容器

标题:在 CentOS 服务器上部署 JAR 文件到 Docker 容器的详细步骤 步骤 1: 确保 Docker 已安装 在开始之前,确保在 CentOS 服务器上已经安装了 Docker。如果没有安装,可以使用以下命令进行安装: sudo yum install docker步骤 2:…...

vector类模拟实现(c++)(学习笔记)

vector 构造函数析构函数[]push_backsize()capacity()reserve()push_back() 迭代器实现非const和const版本 pop_back()resize()insert()***重点erase()***重点再谈构造函数!拷贝构造函数****(重点)运算符重载***(重点)…...

Redis Sentinel 哨兵模式

Sentinel 哨兵模式 Redis Sentinel 官网 Redis 的 Sentinel 文档 -- Redis中国用户组(CRUG) Sentinel Redis 命令参考(红色) Sentinel 通过监控的方式获取主机的工作状态是否正常,当主机发生故障时, Senti…...

实用篇-MQ消息队列

一、初识MQ 通讯分为同步通讯和异步通讯,同步通讯就比如我们日常生活中的打电话,看直播,能够得到及时的反馈。而异步通讯则类似于聊天软件聊天,不需要建立实时的连接,并且可以进行建立多个业务一起异步执行 1. 同步通…...

springboot打包时依赖jar和项目jar分开打包;jar包瘦身

概述 最近感觉项目在部署时时jar包传输太慢了; 看了下jar包内容,除了项目代码,其余大部分都是依赖jar; 平时改动较多的只是项目代码,依赖jar改动比较少; 所以就在想能不能分开打包;这样只部署项…...

嵌入式系统的元素

注意:关于嵌入式系统的元素这一块儿内容,定义太多了。例如:吉姆莱丁 著,陈会翔 译,由清华大学出版社出版的《构建高性能嵌入式系统》中提到:嵌入式系统通常由电源、时基、数字处理、内存、软件和固件、专用…...

提升ChatGPT答案质量和准确性的方法Prompt engineering实用的prompt灵感和技巧

文章目录 1. 实用的prompt灵感和技巧小技巧常用prompt保存到输入法中普通promptprompt通用公式保存到输入法快捷指令中尝试用英语去写prompt沉浸式翻译软件3. 补充1. 实用的prompt灵感和技巧 解释***,并且给出暗喻/隐喻/类比(解释术语、专业名称,用一个词或短语指出常见的一…...

[Machine Learning] Learning with Noisy Labels

文章目录 随机分类噪声 (Random Classification Noise, RCN)类别依赖的标签噪声 (Class-Dependent Noise, CCN)二分类多分类 实例和类别依赖的标签噪声 (Instance and Label-Dependent Noise, ILN) 标签噪声是指分类任务中的标签被错误地标记。这可能是由于各种原因&#xff0c…...

集简云slack(自建)无需API开发轻松连接OA、电商、营销、CRM、用户运营、推广、客服等近千款系统

slack是一个工作效率管理平台,让每个人都能够使用无代码自动化和 AI 功能,还可以无缝连接搜索和知识共享,并确保团队保持联系和参与。在世界各地,Slack 不仅受到公司的信任,同时也是人们偏好使用的平台。 官网&#x…...

Idea 对容器中的 Java 程序断点远程调试

第一种:简单粗暴型 直接在java程序中添加log.info(),根据需要打印信息然后打包覆盖,根据日志查看相关信息 第二种:远程调试 在IDEA右上角点击编辑配置设置相关参数在Dockerfile中加入 "-jar", "-agentlib:jdwp…...

vscode设置保存后,自动格式化代码

第一步:打开setting.json文件 第二步:在setting.json中加入以下代码 "editor.formatOnType": true, "editor.formatOnSave": true, "editor.formatOnPaste": true...

datagrip出现 java.net.ConnectException: Connection refused: connect.

出现这样的情况要看一下hadoop有没有启动 start-all.sh nohup /export/server/apache-hive-3.1.2-bin/bin/hive --service hiveserver2 & scp -r /export/server/apache-hive-3.1.2-bin/ node3:/export/server/ /export/server/apache-hive-3.1.2-bin/bin/hive show databa…...

Docker 安装ELK7.7.1

(在安装之前,本方法必须安装jdk1.8以上版本) 一、安装elasticsearch 1、下载elasticsearch7镜像:docker pull elasticsearch:7.7.1 2、创建挂载目录:mkdir -p /data/elk/es/{config,data,logs} 3、赋予权限:chown -R 1000:100…...

接口测试中缓存处理策略

在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...