算法日记day 12(栈实现队列|队列实现栈|有效的括号)

队列是先进先出的,就像排队一样,谁在前谁先获得服务

栈是一种先进后出的数据结构

一、用栈实现队列

题目:

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 MyQueue 类:

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空,返回 true ;否则,返回 false

说明:

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to toppeek/pop from topsize, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。

示例 1:

输入:
["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

思路:

如何用栈实现先进先出的操作呢?

由于栈底元素是第一个入栈的,为了让他在栈结构中变成第一个出栈的元素,可以设置两种栈,一种负责入栈,一种负责出栈, 如果要实现先进先出,可以让元素先进入栈(push),当需要返回首元素时(peek)将入栈中的元素传进出栈中,这样出栈中第一个出去的元素就是入栈中的栈底元素了

代码:

class MyQueue {Stack<Integer> stackIn;Stack<Integer> stackOut;public MyQueue() {stackIn = new Stack<>();stackOut = new Stack<>();}public void push(int x) {stackIn.push(x);}public int pop() {dumpstackIn();return stackOut.pop();}public int peek() {dumpstackIn();return stackOut.peek();}public boolean empty() {return stackIn.isEmpty() && stackOut.isEmpty();}private void dumpstackIn() {if (!stackOut.isEmpty())return;while (!stackIn.isEmpty()) {stackOut.push(stackIn.pop());}}
}

解释每个方法的功能:

  1. 构造函数 MyQueue()

    • 初始化两个栈 stackIn 和 stackOutstackIn 用于入队操作,stackOut 用于出队操作。
  2. push(int x) 方法

    • 将元素 x 压入 stackIn 中,实现入队操作。
  3. pop() 方法

    • 调用 dumpstackIn() 方法确保 stackOut 中有元素(如果为空的话),然后弹出 stackOut 的栈顶元素,即实现出队操作。
  4. peek() 方法

    • 同样调用 dumpstackIn() 方法确保 stackOut 中有元素,然后返回 stackOut 的栈顶元素,即查看队首元素但不移除。
  5. empty() 方法

    • 判断两个栈是否都为空,如果都为空则队列为空。
  6. 辅助方法 dumpstackIn()

    • 当需要从 stackOut 取元素时,确保 stackOut 中有元素,如果 stackOut 为空,则将 stackIn 中的所有元素逐个弹出并压入 stackOut,以实现从队列头部取元素。

 以示例进行代码分析:

输入:

["MyQueue", "push", "push", "peek", "pop", "empty"]

[[], [1], [2], [], [], []]

输出:

[null, null, null, 1, 1, false]

 初始化队列,创建一个空队列

MyQueue myQueue = new MyQueue();

 push操作,队列变为[1]

myQueue.push(2);

 再次push操作,队列变为[1,2]

myQueue.push(1);

peek操作,返回队首元素,即为1

myQueue.peek();

pop移除队首元素并返回,此时队列变为:[2]

myQueue.pop();

empty判断队列是否为空,此时队列为:[2],不为空,因此返回false

myQueue.empty();

二、用队列实现栈

题目:

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

实现 MyStack 类:

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

注意:

  • 你只能使用队列的标准操作 —— 也就是 push to backpeek/pop from frontsize 和 is 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

思路:

队列实现栈的方法有很多,可以像栈实现队列一样用两个队列,一个存储一个输出,但是这种方法比较麻烦一些,用一个队列实现一个栈会更加简单,如何实现呢,由于队列是先进先出的,栈顶元素的返回即为队列中刚进队的队头元素, 如何用一个队列实现返回队头元素呢,只需要将队列中其他的元素全部出队,然后再次进队,留下的唯一元素就是所需的对头元素了,即为栈顶的元素

代码:

class MyStack {Queue<Integer> queue;// 辅助方法:重新排列队列中的元素,将队列头部的元素移到尾部public void rePosition() {int size = queue.size();size--; // 将队列最后一个元素移到队首之前的所有元素挪动到末尾while (size-- > 0) {queue.add(queue.poll()); // 将队列的头部元素移到尾部}}// 构造函数:初始化一个空队列public MyStack() {queue = new LinkedList<>();}// 入栈操作:将元素加入队列尾部public void push(int x) {queue.add(x);}// 出栈操作:调用 rePosition() 将队列头部元素移到尾部,然后移除队列的头部元素并返回public int pop() {rePosition();return queue.poll(); // 弹出队列的头部元素}// 获取栈顶元素:调用 rePosition() 将队列头部元素移到尾部,然后获取队列的头部元素并返回,再将该元素重新加入队列尾部public int top() {rePosition();int result = queue.poll(); // 弹出队列的头部元素queue.add(result); // 将该元素重新加入队列尾部,模拟栈的操作return result; // 返回栈顶元素}// 判断栈是否为空:判断队列是否为空public boolean empty() {return queue.isEmpty();}
}

 解释每个方法的功能:

  1. 构造函数 MyStack()

    • 初始化一个空的队列 queue,用来存储栈的元素。
  2. rePosition() 方法

    • 重新排列队列中的元素,将队列的头部元素移到尾部,以实现栈的后进先出特性。它通过将队列中的前面的元素依次移动到队列尾部来完成。
  3. push(int x) 方法

    • 将元素 x 加入队列的尾部,实现栈的入栈操作。
  4. pop() 方法

    • 调用 rePosition() 方法将队列的头部元素移到尾部,然后移除队列的头部元素并返回,模拟栈的出栈操作。
  5. top() 方法

    • 调用 rePosition() 方法将队列的头部元素移到尾部,然后获取队列的头部元素并返回,再将该元素重新加入队列的尾部。这样可以返回栈顶元素但不移除它,模拟栈的获取栈顶元素操作。
  6. empty() 方法

    • 判断队列是否为空,从而判断栈是否为空。

以示例进行代码分析:

输入:

["MyStack", "push", "push", "top", "pop", "empty"]

[[], [1], [2], [], [], []]

输出:

[null, null, null, 2, 2, false]

 创建栈对象,返回值为空

MyStack myStack = new MyStack();

将元素1入栈,此时栈中元素为[1]

myStack.push(1);

将元素2入栈,此时栈中元素为[1,2]

myStack.push(2);

调用top方法,返回栈顶元素,返回值为2

myStack.top();

 调用pop方法移除并返回栈顶元素,移除返回的元素为2,此时栈中元素为[1]

myStack.pop();

调用empty方法判断,此时栈中不为空,因此返回false

myStack.empty();

三、有效的括号

题目:

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1:

输入:s = "()"
输出:true

示例 2:

输入:s = "()[]{}"
输出:true

示例 3:

输入:s = "(]"
输出:false

思路:

可以使用栈结构存储对应左括号的右括号类型,当检索到右括号时与栈顶匹配,分为三种情况

第一种:遍历完所有元素后,栈中仍有元素,说明有相应的左括号没有右括号来匹配(左括号数量多于右括号)

第二种:遍历过程中,栈中没有要匹配的字符

第三种,遍历过程中,发现栈已经为空(右括号多于左括号)

当字符串全部遍历完且栈为空,说明左右括号均匹配

代码:

public boolean isValid(String s) {Stack<Character> stack = new Stack<>();char c;for (int i = 0; i < s.length(); i++) {//使用一个 for 循环遍历字符串 s 的每个字符,从头到尾依次处理每个字符。c = s.charAt(i);//如果当前字符 c 是左括号 '(', '[', '{',则将对应的右括号 ')', ']', '}' 推入栈中//这样,栈中存放的就是遇到的左括号所对应的期望右括号。if (c == '(')stack.push(')');else if (c == '[')stack.push(']');else if (c == '{')stack.push('}');//如果当前字符 c 是右括号 ')', ']', '}',则检查栈顶的字符是否与 c 匹配//如果栈为空(即没有左括号与之对应),或者栈顶字符与 c 不匹配,说明当前的括号序列不合法,直接返回 false。//如果栈顶字符与 c 匹配,则将栈顶元素弹出,表示找到了一个匹配的括号对。else if (stack.isEmpty() || stack.peek() != c) {return false;} else {stack.pop();}}//最后,检查栈是否为空。//如果栈为空,说明所有的左括号都找到了对应的右括号,返回 true,表示输入的字符串 s 是有效的括号序列;否则返回 false,表示存在未匹配的括号return stack.isEmpty();
}

今天的学习就到这里了

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/380324.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

uniapp上传功能用uni-file-picker实现

文章目录 html代码功能实现css样式代码 html代码 <uni-file-pickerselect"onFileSelected"cancel"onFilePickerCancel"limit"1"class"weightPage-upload-but"file-mediatype"image"></uni-file-picker><imag…

飞睿智能UWB Tag蓝牙防丢器标签,宠物安全新升级,5cm精准定位测距不迷路

宠物早已成为许多家庭不可或缺的一员&#xff0c;它们用无条件的爱温暖着我们的心房&#xff0c;陪伴我们度过每一个平凡而温馨的日子。然而&#xff0c;随着宠物活动范围的扩大和外界环境的复杂多变&#xff0c;宠物走失的风险也随之增加。每一次出门遛弯&#xff0c;都像是心…

视频压缩文件太大了怎么缩小?怎么压缩视频大小?视频压缩方法:10个!(宝藏)

视频压缩文件太大了怎么缩小&#xff1f;让我看看是谁下班之后不是一手刷手机短视频&#xff0c;顺便葛优躺在沙发上的&#xff1f;互联网发展到现在&#xff0c;视频已成为我们生活中不可或缺的一部分。不管是视频录制还是视频缓存&#xff0c;视频文件体积越来越庞大&#xf…

微信小程序canvas 使用案例(一)

一、cavans 对象获取、上线文创建 1.wxml <!-- canvas.wxml --><canvas type"2d" id"myCanvas"></canvas> 2.js /*** 生命周期函数--监听页面加载*/onLoad(options) {const query wx.createSelectorQuery()query.select(#myCanvas).f…

DICOM CT\MR片子免费在线查看工具;python pydicom包加载查看;mayavi 3d查看

DICOM CT\MR片子免费在线查看工具 参考&#xff1a; https://zhuanlan.zhihu.com/p/668804209 dicom格式&#xff1a; DICOM&#xff08;Digital Imaging and Communications in Medicine&#xff09;是医学数字成像和通信的标准。它定义了医学图像&#xff08;如CT、MRI、X…

.net6 core Worker Service项目,使用Exchange Web Services (EWS) 分页获取电子邮件收件箱列表,邮件信息字段

Program.cs 安装包&#xff1a;Microsoft.AspNetCore.Hosting.WindowsServices、Microsoft.Extensions.Hosting、Microsoft.Extensions.Hosting.WindowsServices、Microsoft.Extensions.Logging.Log4Net.AspNetCore 新建Configs/log4net.config using Com.Chinahorn.Exchange.W…

【人工智能】机器学习 -- 决策树(乳腺肿瘤数)

目录 一、使用Python开发工具&#xff0c;运行对iris数据进行分类的例子程序dtree.py&#xff0c;熟悉sklearn机器实习开源库。 二、登录https://archive-beta.ics.uci.edu/ 三、使用sklearn机器学习开源库&#xff0c;使用决策树对breast-cancer-wisconsin.data进行分类。 …

docker自建rustdesk-server远程桌面

rustdesk简介 RustDesk 是一款可以平替 TeamViewer 的开源软件&#xff0c;旨在提供安全便捷的自建方案。 RustDesk 是一款功能齐全的远程桌面应用&#xff0c;具有以下特性&#xff1a; 支持 Windows、macOS、Linux、iOS、Android、Web 等多个平台。支持 VP8 / VP9 / AV1 …

JMeter使用手册

安装 下载地址 https://jmeter.apache.org/download_jmeter.cgi 下载后解压到win的文件夹中 打开JMeter的bin文件夹&#xff0c;双击这个jar就启动了JMeter 启动 出现这样的界面 基本使用 添加变量 这个变量在使用的时候可以被引用 创建线程组 所有的请求都得基于…

Harbor系列之1:介绍、架构及工作流程说明

Harbor介绍、架构及工作流程说明 Harbor 是一个用于存储、签名和扫描内容的企业级容器镜像注册表项目。由 VMware 开发并于 2016 年开源。Harbor 提供了一些关键特性&#xff0c;使其成为企业使用的理想选择。 1. Harbor 介绍 1.1 什么是 Harbor Harbor 是一个开源的云原生…

Spring-Boot基础--yaml

目录 Spring-Boot配置文件 注意&#xff1a; YAML简介 YAML基础语法 YAML:数据格式 YAML文件读取配置内容 逐个注入 批量注入 ConfigurationProperties 和value的区别 Spring-Boot配置文件 Spring-Boot中不用编写.xml文件&#xff0c;但是spring-Boot中还是存在.prope…

基于GTX的64B66B编码的自定义接收模块(高速收发器二十二)

点击进入高速收发器系列文章导航界面 1、自定义PHY顶层模块 前文设计了64B66B自定义PHY的发送模块&#xff0c;本文完成自定义PHY剩余的模块的设计&#xff0c;整体设计框图如下所示。 其中phy_tx是自定义PHY的发送数据模块&#xff0c;scrambler是加扰模块&#xff0c;rx_slip…

多口适配器,给您的生活增添便利

随着科技的快速发展&#xff0c;我们的生活已离不开各种各样的电子设备&#xff0c;智能手机、平板电脑、智能手表、无线耳机……它们共同构建了我们丰富多彩的数字生活。然而&#xff0c;面对众多设备的充电需求&#xff0c;传统的单一充电口已难以满足现代人的使用习惯。在这…

使用JWT双令牌机制进行接口请求鉴权

在前后端分离的开发过程中&#xff0c;前端发起请求&#xff0c;调用后端接口&#xff0c;后端在接收请求时&#xff0c;首先需要对收到的请求鉴权&#xff0c;在这种情况先我们可以采用JWT机制来鉴权。 JWT有两种机制&#xff0c;单令牌机制和双令牌机制。 单令牌机制服务端…

IDEA的详细设置

《IDEA破解、配置、使用技巧与实战教程》系列文章目录 第一章 IDEA破解与HelloWorld的实战编写 第二章 IDEA的详细设置 第三章 IDEA的工程与模块管理 第四章 IDEA的常见代码模板的使用 第五章 IDEA中常用的快捷键 第六章 IDEA的断点调试&#xff08;Debug&#xff09; 第七章 …

《绝区零》是一款什么类型的游戏,Mac电脑怎么玩《绝区零》苹果电脑玩游戏怎么样

米哈游的《绝区零》最近在网上爆火呀&#xff0c;不过很多人都想知道mac电脑能不能玩《绝区零》&#xff0c;今天麦麦就给大家介绍一下《绝区零》是一款什么样的游戏&#xff0c;Mac电脑怎么玩《绝区零》。 一、《绝区零》是一款什么样的游戏 《绝区零》是由上海米哈游自主研发…

常见排序算法总结

文章目录 比较排序冒泡排序选择排序插入排序归并排序快速排序堆排序希尔排序 非比较排序&#xff08;桶排序&#xff09;计数排序基数排序 比较排序 冒泡排序 嵌套循环&#xff0c;每次内层循环执行时&#xff0c;数组的每两个元素交换&#xff0c;将一个最大/小的数排到数组…

技术成神之路:设计模式(八)责任链模式

介绍 责任链模式&#xff08;Chain of Responsibility Pattern&#xff09;是一种行为设计模式&#xff0c;它允许多个对象依次处理请求&#xff0c;避免请求的发送者和接收者之间的显式耦合。该模式通过将多个可能处理请求的对象连接成一条链&#xff0c;并沿着这条链传递请求…

达梦数据库 DISQL连接数据库与执行SQL、脚本的方法

DISQL连接数据库与执行SQL、脚本的方法 1.DISQL介绍2.DISQL连接数据库的方法2.1 本地连接2.2 远程连接2.3 CONN连接 3.执行SQL、脚本的方法3.1 通过DISQL登录后在字符界面3.2 启动DISQL时运行脚本3.3 进入DISQL后&#xff0c;通过start命令运行脚本3.4 使用EDIT命令编辑脚本 1.…

ubuntu 24 PXE Server (bios+uefi) 批量部署系统

pxe server 前言 PXE&#xff08;Preboot eXecution Environment&#xff0c;预启动执行环境&#xff09;是一种网络启动协议&#xff0c;允许计算机通过网络启动而不是使用本地硬盘。PXE服务器是实现这一功能的服务器&#xff0c;它提供了启动镜像和引导加载程序&#xff0c;…