数据结构——栈与栈排序
栈的特性
栈是一种遵循后进先出(LIFO)原则的数据结构。其基本操作包括:
push
:将元素添加到栈顶。pop
:移除栈顶元素。peek
:查看栈顶元素,但不移除。
栈排序的原理
栈排序的核心是使用两个栈:一个原始栈(用于输入数据)和一个辅助栈(用于排序过程)。通过这两个栈的相互操作,可以实现数据的排序。
排序实现步骤
-
初始化:创建两个栈,
stk
(原始栈)和tmpstk
(辅助栈)。 -
执行排序:
- 当新元素需要加入原始栈
stk
时,先比较它与辅助栈tmpstk
顶部元素的大小。 - 如果辅助栈顶部的元素大于新元素,则将辅助栈的元素移动到原始栈,直至找到合适的位置为新元素腾出空间。
- 将新元素放入辅助栈。
- 最终,辅助栈
tmpstk
中的元素将按排序顺序存放。
- 当新元素需要加入原始栈
-
完成排序:将辅助栈
tmpstk
的元素移回原始栈stk
,此时stk
中的元素依排序顺序排列。
代码实现
1.在将新元素压入栈的时候就进行排序
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
class SortedStack {
private:stack<int>stk;stack<int>tmpstk;
public:SortedStack() {}void push(int val) {// 将stk中小于val的元素移到tmpstkwhile (!stk.empty() && stk.top() < val) {tmpstk.push(stk.top());stk.pop();}// 将新元素val压入stkstk.push(val);// 将tmpstk的元素回填到stk,保持stk的排序while (!tmpstk.empty()) {stk.push(tmpstk.top());tmpstk.pop();}}void pop() {if(!stk.empty())stk.pop();return;}int peek() {if(!stk.empty())return stk.top();return -1;}bool isEmpty() {return stk.empty();}
};
此代码段展示了栈排序的具体实现。push
函数中的逻辑确保了每次插入新元素后,stk
都会按排序顺序重新排列。
2.对一个已经压入所有元素的栈的排序
while (!st.is_empty()) {int tmp = st.get_top(); st.pop();while (!tmpst.is_empty() && tmp <tmpst.get_top()) {st.push(tmpst.get_top());tmpst.pop();}tmpst.push(tmp);}while (!tmpst.is_empty() {st.push(tmpst.get_top());tmpst.pop();}
代码解释
-
第一个 while 循环:该循环负责进行排序。
while (!st.is_empty())
:当主栈st
不为空时,执行循环体。int tmp = st.get_top(); st.pop();
:取出st
栈顶元素并存储在tmp
中,然后将该元素从st
弹出。while (!tmpst.is_empty() && tmp < tmpst.get_top())
:如果辅助栈tmpst
不为空且tmp
小于tmpst
的栈顶元素,则执行内部循环。st.push(tmpst.get_top());
:将tmpst
的栈顶元素移回st
。tmpst.pop();
:从tmpst
弹出栈顶元素。
tmpst.push(tmp);
:将tmp
压入tmpst
。
-
第二个 while 循环:该循环将排序后的元素从
tmpst
移回st
。while (!tmpst.is_empty())
:当辅助栈tmpst
不为空时,执行循环体。st.push(tmpst.get_top());
:将tmpst
的栈顶元素压入st
。tmpst.pop();
:从tmpst
弹出栈顶元素。
- 模拟过程
st: [4, 2, 3, 1] (栈顶是 1)
tmpst: []第一步:处理元素 1
从 st 弹出 1 (tmp = 1)。
tmpst 是空的,所以直接将 1 压入 tmpst。st: [4, 2, 3] (栈顶是 3)
tmpst: [1]第二步:处理元素 3
从 st 弹出 3 (tmp = 3)。
tmpst 的栈顶元素 1 小于 3,所以不需要移动元素,直接将 3 压入 tmpst。st: [4, 2] (栈顶是 2)
tmpst: [3, 1]第三步:处理元素 2
从 st 弹出 2 (tmp = 2)。
tmpst 的栈顶元素 3 大于 2,所以将 3 移回 st。现在 tmpst 的栈顶元素 1 小于 2,直接将 2 压入 tmpst。st: [4, 3] (栈顶是 3)
tmpst: [2, 1]第四步:处理元素 3
从 st 弹出 3 (tmp = 3)。
tmpst 的栈顶元素 2 小于 3,不需要移动元素,直接将 3 压入 tmpst。st: [4] (栈顶是 4)
tmpst: [3, 2, 1]第五步:处理元素 4
从 st 弹出 4 (tmp = 4)。
tmpst 的栈顶元素 3 小于 4,所以直接将 4 压入 tmpst。st: []
tmpst: [4, 3, 2, 1]完成排序
将 tmpst 中的元素按顺序移回 st,得到排序后的栈。
st: [1, 2, 3, 4] (栈顶是 4)
tmpst: []
优势和局限性
- 优势:栈排序提供了一种直观理解排序逻辑的方法,同时也是对栈操作的良好练习。
- 局限性:栈排序的效率相对较低,特别是在处理大量数据时。它的时间复杂度为 O(n²),不适合用于性能敏感的应用。
相关文章:
数据结构——栈与栈排序
栈的特性 栈是一种遵循后进先出(LIFO)原则的数据结构。其基本操作包括: push:将元素添加到栈顶。pop:移除栈顶元素。peek:查看栈顶元素,但不移除。 栈排序的原理 栈排序的核心是使用两个栈&…...

Java Web应用小案例 - 实现用户登录功能
文章目录 一、使用纯JSP方式实现用户登录功能(一)项目概述(二)实现步骤1、创建Web项目2、创建登录页面 二、使用JSPServlet方式实现用户登录功能三、使用JSPServletDB方式实现用户登录功能 一、使用纯JSP方式实现用户登录功能 &a…...

Excel——多列合并成一列的4种方法
Excel怎么将多列内容合并成一列? 怎么将多个单元格的内容连接起来放在一个单元格里? 比如下图,要将B、C、D列的内容,合并成E列那样,该怎么做呢? △图1 本文中,高潜老师将给大家介绍 4种 将多…...
Vue笔记(四)路由
路由(Vue Router) 用Vue Vue Router创建单页面应用非常简单。当加入Vue Router时,需要将组件映射到路由上,让Vue知道在哪里渲染它们。 路由基本例子 <!-- 引入Vue 和 router --><script src"https://unpkg.com/vu…...

Redis部署-哨兵模式
目录 redis sentinel相关名词 redis sentinel架构 故障转移流程 基于docker搭建redis哨兵 准备工作 搭建过程 模拟主节点宕机,观察哨兵节点的工作流程 哨兵重新选取主节点的流程 1.主观下线 2.客观下线 3.哨兵节点推举出一个leader节点 4.leader选举完毕,leader挑选…...

滑动窗口练习(三)— 加油站问题
题目 测试链接 在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。 给定两个整数数组…...

udemy angular decoration 自存
番外 为什么一个ts文件变成了component,因为它使用了components装饰器 components is just a class,you export it so angular know how to use it 举例:组件装饰器 decoration前总是有一个符号 decoration的作用(之一?) NgModu…...

msvcr90.dll丢失的解决方法分享,5个快速修复dll文件丢失教程
在今天的电脑使用过程中,我们可能会遇到各种各样的问题。其中之一就是msvcr90.dll丢失的问题。那么,msvcr90.dll是什么?msvcr90.dll丢失对电脑有什么影响?又该如何解决这个问题呢?接下来,我将为大家详细介绍…...

海外媒体发稿:软文发稿推广技巧解析超级实用-华媒舍
随着互联网时代的发展,软文发稿成为推广产品与服务的重要手段之一。本文将向大家介绍软文发稿推广的技巧,帮助您更好地利用软文推广商业活动。无论是拥有自己的品牌还是个人创业者,都可以从中受益。 1. 什么是软文? 软文是指以文…...

vm net 方式 静态ip配置访问主机IP和外网
1、win 11 安装vm,镜像文件 F:\software\VMwork\CentOS-7-x86_64-Everything-1804.iso 2、配置网络 net 方式 3、右击网络--》属性---》更改适配器设置--》vmnet8 属性、这里不做配置会出现主机ping通访问不通的情况,(访问不通,…...
Vue笔记(二)基本语法
基本语法 <style> table {border-collapse: collapse;margin:0 auto; } strong {color: rgb(235, 51, 100); }td, th {padding-left: 6px; } table tr td:first-child {width:150px } table tr td:nth-child(2) {width:300px } </style> <template><tabl…...
前端面试提问(4)
1、手撕防抖与节流、树与对象的转换、递归调用,链表头插法 1.1、防抖 防抖函数用于延迟执行某个函数,直到过了一定的间隔时间(例如等待用户停止输入)后再执行。 即后一次点击事件发生时间距离一次点击事件至少间隔一定时间。 …...

基于BEV+Transformer的地面要素感知+建模技术在高德的应用
导读 本文将主要介绍BEVTransformer端到端感知与建模技术在高德各项业务中的应用,如高精地图中地面要素(包含线要素和地面标识)自动化上的具体方案及其演化过程。该方案使用BEVTransformer技术来实现采集车上不同传感器(包含激光和…...

了解c++11中的新增
一,统一的初始化列表 在引入c11后,我们得出计划都可以用初始化列表进行初始化。 C11 扩大了用大括号括起的列表 ( 初始化列表 ) 的使用范围,使其可用于所有的内置类型和用户自 定义的类型, 使用初始化列表时,可添加等…...

104. 二叉树的最大深度(Java)
目录 解法: 官方解答: 方法一:深度优先搜索 方法二:广度优先搜索 思路与算法 复杂度分析 时间复杂度: 空间复杂度: 给定一个二叉树 root ,返回其最大深度。 二叉树的 最大深度 是指从根…...

SpringSecurity6 | 自定义认证规则
✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: Java从入门到精通 ✨特色专栏…...

浅析安科瑞电动机保护器在广州某地铁项目的设计与应用-安科瑞 蒋静
1 摘要 随着城市的发展,较多城市的轨道交通选择修建地下式车辆段(或停车场),即车辆段(或停车场)位于地下或设置有上盖(上盖上再做物业开发)。为了给工作人员提供良好的工作环境、给…...
LeetCode 2048. 下一个更大的数值平衡数
【LetMeFly】2048.下一个更大的数值平衡数 力扣题目链接:https://leetcode.cn/problems/next-greater-numerically-balanced-number/ 如果整数 x 满足:对于每个数位 d ,这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。…...

多线程(初阶七:阻塞队列和生产者消费者模型)
目录 一、阻塞队列的简单介绍 二、生产者消费者模型 1、举个栗子: 2、引入生产者消费者模型的意义: (1)解耦合 (2)削峰填谷 三、模拟实现阻塞队列 1、阻塞队列的简单介绍 2、实现阻塞队列 &#…...
区间价值 --- 题解--动态规划
目录 区间价值 题目描述 输入描述: 输出描述: 输入 输出 备注: 思路: 代码: 区间价值 J-区间价值_牛客竞赛动态规划专题班习题课 (nowcoder.com) 时间限制:C/C 2秒,其他语言4秒 空间限制:C/C 262144K&…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...

React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...

R 语言科研绘图第 55 期 --- 网络图-聚类
在发表科研论文的过程中,科研绘图是必不可少的,一张好看的图形会是文章很大的加分项。 为了便于使用,本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中,获取方式: R 语言科研绘图模板 --- sciRplothttps://mp.…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

论文阅读:Matting by Generation
今天介绍一篇关于 matting 抠图的文章,抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法,已经有很多的工作和这个任务相关。这两年 diffusion 模型很火,大家又开始用 diffusion 模型做各种 CV 任务了&am…...