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

数据结构——栈与栈排序

栈的特性

栈是一种遵循后进先出(LIFO)原则的数据结构。其基本操作包括:

  • push:将元素添加到栈顶。
  • pop:移除栈顶元素。
  • peek:查看栈顶元素,但不移除。
栈排序的原理

栈排序的核心是使用两个栈:一个原始栈(用于输入数据)和一个辅助栈(用于排序过程)。通过这两个栈的相互操作,可以实现数据的排序。

排序实现步骤
  1. 初始化:创建两个栈,stk(原始栈)和 tmpstk(辅助栈)。

  2. 执行排序

    • 当新元素需要加入原始栈 stk 时,先比较它与辅助栈 tmpstk 顶部元素的大小。
    • 如果辅助栈顶部的元素大于新元素,则将辅助栈的元素移动到原始栈,直至找到合适的位置为新元素腾出空间。
    • 将新元素放入辅助栈。
    • 最终,辅助栈 tmpstk 中的元素将按排序顺序存放。
  3. 完成排序:将辅助栈 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();}
代码解释
  1. 第一个 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
  2. 第二个 while 循环:该循环将排序后的元素从 tmpst 移回 st

    • while (!tmpst.is_empty()):当辅助栈 tmpst 不为空时,执行循环体。
    • st.push(tmpst.get_top());:将 tmpst 的栈顶元素压入 st
    • tmpst.pop();:从 tmpst 弹出栈顶元素。
  3. 模拟过程
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²),不适合用于性能敏感的应用。

相关文章:

数据结构——栈与栈排序

栈的特性 栈是一种遵循后进先出&#xff08;LIFO&#xff09;原则的数据结构。其基本操作包括&#xff1a; push&#xff1a;将元素添加到栈顶。pop&#xff1a;移除栈顶元素。peek&#xff1a;查看栈顶元素&#xff0c;但不移除。 栈排序的原理 栈排序的核心是使用两个栈&…...

Java Web应用小案例 - 实现用户登录功能

文章目录 一、使用纯JSP方式实现用户登录功能&#xff08;一&#xff09;项目概述&#xff08;二&#xff09;实现步骤1、创建Web项目2、创建登录页面 二、使用JSPServlet方式实现用户登录功能三、使用JSPServletDB方式实现用户登录功能 一、使用纯JSP方式实现用户登录功能 &a…...

Excel——多列合并成一列的4种方法

Excel怎么将多列内容合并成一列&#xff1f; 怎么将多个单元格的内容连接起来放在一个单元格里&#xff1f; 比如下图&#xff0c;要将B、C、D列的内容&#xff0c;合并成E列那样&#xff0c;该怎么做呢&#xff1f; △图1 本文中&#xff0c;高潜老师将给大家介绍 4种 将多…...

Vue笔记(四)路由

路由&#xff08;Vue Router&#xff09; 用Vue Vue Router创建单页面应用非常简单。当加入Vue Router时&#xff0c;需要将组件映射到路由上&#xff0c;让Vue知道在哪里渲染它们。 路由基本例子 <!-- 引入Vue 和 router --><script src"https://unpkg.com/vu…...

Redis部署-哨兵模式

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

滑动窗口练习(三)— 加油站问题

题目 测试链接 在一条环路上有 n 个加油站&#xff0c;其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车&#xff0c;从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发&#xff0c;开始时油箱为空。 给定两个整数数组…...

udemy angular decoration 自存

番外 为什么一个ts文件变成了component,因为它使用了components装饰器 components is just a class,you export it so angular know how to use it 举例&#xff1a;组件装饰器 decoration前总是有一个符号 decoration的作用&#xff08;之一&#xff1f;&#xff09; NgModu…...

msvcr90.dll丢失的解决方法分享,5个快速修复dll文件丢失教程

在今天的电脑使用过程中&#xff0c;我们可能会遇到各种各样的问题。其中之一就是msvcr90.dll丢失的问题。那么&#xff0c;msvcr90.dll是什么&#xff1f;msvcr90.dll丢失对电脑有什么影响&#xff1f;又该如何解决这个问题呢&#xff1f;接下来&#xff0c;我将为大家详细介绍…...

海外媒体发稿:软文发稿推广技巧解析超级实用-华媒舍

随着互联网时代的发展&#xff0c;软文发稿成为推广产品与服务的重要手段之一。本文将向大家介绍软文发稿推广的技巧&#xff0c;帮助您更好地利用软文推广商业活动。无论是拥有自己的品牌还是个人创业者&#xff0c;都可以从中受益。 1. 什么是软文&#xff1f; 软文是指以文…...

vm net 方式 静态ip配置访问主机IP和外网

1、win 11 安装vm&#xff0c;镜像文件 F:\software\VMwork\CentOS-7-x86_64-Everything-1804.iso 2、配置网络 net 方式 3、右击网络--》属性---》更改适配器设置--》vmnet8 属性、这里不做配置会出现主机ping通访问不通的情况&#xff0c;&#xff08;访问不通&#xff0c;…...

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、手撕防抖与节流、树与对象的转换、递归调用&#xff0c;链表头插法 1.1、防抖 防抖函数用于延迟执行某个函数&#xff0c;直到过了一定的间隔时间&#xff08;例如等待用户停止输入&#xff09;后再执行。 即后一次点击事件发生时间距离一次点击事件至少间隔一定时间。 …...

基于BEV+Transformer的地面要素感知+建模技术在高德的应用

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

了解c++11中的新增

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

104. 二叉树的最大深度(Java)

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

SpringSecurity6 | 自定义认证规则

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; Java从入门到精通 ✨特色专栏&#xf…...

浅析安科瑞电动机保护器在广州某地铁项目的设计与应用-安科瑞 蒋静

1 摘要 随着城市的发展&#xff0c;较多城市的轨道交通选择修建地下式车辆段&#xff08;或停车场&#xff09;&#xff0c;即车辆段&#xff08;或停车场&#xff09;位于地下或设置有上盖&#xff08;上盖上再做物业开发&#xff09;。为了给工作人员提供良好的工作环境、给…...

LeetCode 2048. 下一个更大的数值平衡数

【LetMeFly】2048.下一个更大的数值平衡数 力扣题目链接&#xff1a;https://leetcode.cn/problems/next-greater-numerically-balanced-number/ 如果整数 x 满足&#xff1a;对于每个数位 d &#xff0c;这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。…...

多线程(初阶七:阻塞队列和生产者消费者模型)

目录 一、阻塞队列的简单介绍 二、生产者消费者模型 1、举个栗子&#xff1a; 2、引入生产者消费者模型的意义&#xff1a; &#xff08;1&#xff09;解耦合 &#xff08;2&#xff09;削峰填谷 三、模拟实现阻塞队列 1、阻塞队列的简单介绍 2、实现阻塞队列 &#…...

区间价值 --- 题解--动态规划

目录 区间价值 题目描述 输入描述: 输出描述: 输入 输出 备注: 思路&#xff1a; 代码&#xff1a; 区间价值 J-区间价值_牛客竞赛动态规划专题班习题课 (nowcoder.com) 时间限制&#xff1a;C/C 2秒&#xff0c;其他语言4秒 空间限制&#xff1a;C/C 262144K&…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

React19源码系列之 事件插件系统

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

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

R 语言科研绘图第 55 期 --- 网络图-聚类

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

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

论文阅读:Matting by Generation

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