当前位置: 首页 > 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&…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...