( 栈和队列) 225. 用队列实现栈 ——【Leetcode每日一题】

news/2024/2/21 3:52:09

❓225. 用队列实现栈

难度:简单

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false

注意:

  • 你只能使用队列的基本操作 —— 也就是 push to backpeek/pop from frontsizeis empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

示例:

输入:
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 2, 2, false]

解释:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示:

  • 1 <= x <= 9
  • 最多调用100 次 pushpoptopempty
  • 每次调用 poptop 都保证栈不为空

进阶:你能否仅用一个队列来实现栈。

💡思路:

在将一个元素 x 插入队列时,为了维护原来的后进先出顺序,需要让 x 插入队列首部。

而队列的默认插入顺序是队列尾部,因此在将 x 插入队列尾部之后,需要让除了 x 之外的所有元素出队列,再入队列。

🍁代码:(Java、C++)

Java

class MyStack {private Queue<Integer> que;public MyStack() {que = new LinkedList<>();}public void push(int x) {int len = que.size();que.add(x);for(int i = 0; i < len; i++){que.add(que.poll());}}public int pop() {return que.remove();}public int top() {return que.peek();}public boolean empty() {return que.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/

C++

class MyStack {
private:queue<int> que;
public:MyStack() {}void push(int x) {int len  = que.size();que.push(x);for(int i = 0; i < len; i++){que.push(que.front());que.pop();}}int pop() {int x = que.front();que.pop();return x;}int top() {return que.front();}bool empty() {return que.empty();}
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n 2 ) O(n^2) O(n2),入栈操作 O ( n ) O(n) O(n),其余操作都是 O ( 1 ) O(1) O(1),其中 n 是栈内的元素个数。每次入栈操作需要将队列中的 n 个元素出队,并入队 n + 1 个元素到队列,共有 2n+1次操作,每次出队和入队操作的时间复杂度都是 O ( 1 ) O(1) O(1),且最多要入栈n次因此入栈操作的时间复杂度是 O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度 O ( n ) O(n) O(n),其中 n 是栈内的元素个数。需要使用一个队列存储栈内的元素。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/53271.html

相关文章

python算法中的深度学习算法之长短时记忆网络(详解)

目录 学习目标: 学习内容: 算法之长短时记忆网络 Ⅰ. LSTM 网络单元 ①、输入门

(4)Mapping(映射)

映射是定义文档及其包含的字段的存储和索引方式的过程。 两种映射方式 dynamic mapping&#xff08;动态映射或自动映射&#xff09; expllcit mapping&#xff08;静态映射或手工映射或显示映射&#xff09; Mapping数据类型 Mapping参数 https://www.elastic.co/guide/…

智加科技+舍弗勒,首发量产正向开发的智能重卡冗余转向

对于自动驾驶赛道来说&#xff0c;感知、规划和控制&#xff0c;除了计算平台、算法等核心上层软硬件支持&#xff0c;底盘控制系统同样是关键一环。事实上&#xff0c;从Demo到规模化量产&#xff0c;更好的车身控制能力以及冗余备份&#xff0c;也是自动驾驶公司迈入2.0阶段的…

一次典型的ORA-04031问题的处理

梳理客户问题&#xff0c;发现之前一个典型的ORA-04031报错&#xff0c;相关处理步骤思路如下&#xff1a; 1.接到应用软件使用人员反馈&#xff0c;程序报错ORA-04031 2.检查数据库alert日志&#xff0c;发现后台日志不停报错ORA-04031: 无法分配 ORA-04031: 无法分配 4160 …

【文心一言】广告文案、演讲稿与请假条自动生成

前言 作为一名大学生而言&#xff0c;平时参加或者举办一些学校组织的活动的时候&#xff0c;总是避免不了需要准备一些演讲稿、广告宣传文案等内容&#xff0c;甚至于在疫情十分严重的这几年内&#xff0c;如何跟老师“委婉的”请假&#xff0c;也成为了我日常头疼的事情。但在…

远程控制电脑的软件哪个比较好用

有多种软件选项可用于远程控制计算机&#xff0c;最适合您的软件选项取决于您的具体需要和要求。 以下是一些最流行的远程控制软件选项及其功能和优势&#xff1a; TeamViewer TeamViewer 是使用最广泛的远程控制软件选项之一。 它具有用户友好的界面&#xff0c;并提供文件传…

【JavaEE】SpringBoot配置文件的设置及其读取

目录 配置文件作用 配置文件注意事项 properties 用法 修改字符集 优缺点 yml 用法 优缺点 读取配置文件 使用 Value注解 读properties配置文件 读yml配置文件 使用 ConfigurationProperties 注解 读properties配置文件 读yml配置文件 配置文件作用 SpringBoot的…

MATLAB算法实战应用案例精讲-【人工智能】机器视觉(概念篇)(补充篇)(附python和matlab代码实现)

目录 前言 知识储备 机器视觉成像 2. 镜头 3. 为机器视觉项目选择镜头和相机的简化流程

Flask搭建api服务-生成API文档

前面讲到了Flask实现api&#xff0c;但api是给别人用的&#xff0c;就要告诉别人如何发现api&#xff0c;以及api的用途、名称、出参、入参&#xff0c;生成api文档的做法有好多种&#xff0c;本文选了一种最简单的方式。 核心就是通过app.view_functions 这个字典找到每个API…

libgo 流程分析(1)

libgo 基础模块 libgo逻辑结构 libgo主要的功能模块主要包括&#xff1a;调度器( Scheduler )、处理器( Processer )、协程( Task )和一个FastSteadyClock。 其中 Scheduler -> Processer -> Task 三层逻辑结构实现了对协程( Task )的生命周期管理和调度和运行。 sch…

Qt鼠标事件全面解析:从基础到实战

Qt鼠标事件全面解析&#xff1a;从基础到实战 一、前言1.1. QT 鼠标事件简介1.2. 鼠标事件在开发中的作用及价值1.3. 本文内容概览&#xff08;Outline of the Article&#xff09; 二、基础知识&#xff1a;Qt中鼠标事件类简介&#xff08;Basic Knowledge: Introduction to M…

C++中引用的基本内容

个人主页&#xff1a;平行线也会相交 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 平行线也会相交 原创 收录于专栏【C之路】 引用&#xff0c;其实没啥特别的&#xff0c;就是起外号&#xff0c;或者说起小名。就比如说孙悟空就有很多外号&#xff0c;如…

C常规型人格的特点和职业选择(霍兰德职业兴趣测试)

常规型人格来源霍兰德职业兴趣理论&#xff0c;在霍兰德职业兴趣测试中&#xff0c;常规型人格也叫C型人格&#xff0c;他们是传统的代表&#xff0c;为人踏实勤奋&#xff0c;做事兢兢业业&#xff0c;不求创新创造&#xff0c;但是毅力过人&#xff0c;细致耐心。不论哪个行业…

搞懂 API ,地图 API 制作方法分享

地图 API 是一种基于 Web 开发的应用程序编程接口&#xff0c;可以用于创建和展示地图及地理信息。以下是一些地图 API 制作的方法&#xff1a; 选择地图 API 平台&#xff1a;目前市场上有很多地图 API 平台供选择&#xff0c;比如 Google Maps API、百度地图 API、高德地图 A…

到底什么是JS的promise?

一、promise的作用 promise用于异步调用&#xff0c;当你需要使用异步嵌套的时候&#xff0c;可以使用promise去简化代码&#xff0c;而不是在ajax或者fetch请求中&#xff0c;再重复写多个请求甚至更多的嵌套异步请求。 二、promise的使用 在promise中可以传入一个函数&…

[Unity] No.1 Single单例模式

单例模式 1. 基础 定义&#xff1a;单例模式是指在内存中只会创建且仅创建一次对象的设计模式。在程序中多次使用同一个对象且作用相同时&#xff0c;为了防止频繁地创建对象使得内存飙升&#xff0c;单例模式可以让程序仅在内存中创建一个对象&#xff0c;让所有需要调用的地…

K-Means和轮廓系数

K-Means和轮廓系数 K-means&#xff08;K均值&#xff09;是机器学习中一种常见的无监督算法&#xff0c;它能够将未知标签的数据&#xff0c;根据它们的特征分成不同组&#xff0c;每一组数据又称为“簇”&#xff0c;每一簇的中心点称为“质心”。其基本原理过程如下&#x…

MySQL 8.0.28中的sql_mode常见参数及其意

MySQL 8.0.28中的sql_mode参数如下&#xff1a; 1. ALLOW_INVALID_DATES - 允许插入无效日期&#xff08;如0000-00-00&#xff09;。 2. ANSI_QUOTES - 激活ANSI_QUOTES模式&#xff0c;使双引号成为标识符引用的有效字符。 默认情况下&#xff0c;mysql使用单引号将字符串引起…

局域网 - CSMA/CD(载波侦听多路访问 / 冲突检测)

文章目录 1 概述1.1 局域网的拓扑结构 2 CSMA/CD2.1 三种监听算法2.2 冲突检测原理2.3 二进制指数后退算法 3 扩展3.1 网工软考真题 1 概述 1.1 局域网的拓扑结构 2 CSMA/CD CSMA/CD&#xff1a;Carrier Sense Multiple Access/ Collision Detection&#xff0c;载波侦听多路…

TCP 协议的低效实现

包括 Linux kernel 在内的各种 TCP 实现均使用类似 skb 的对象管理一个个 packet&#xff0c;使 TCP 失去了 “流” 特征。应用通过 syscall 每写入一批数据&#xff0c;协议栈都可能生成一个 skb&#xff1a; ​ 仅管理这些 skb 就是一笔大开销。除了 skb 数据结构本身的 cru…
最新文章