草庐IT

数据结构(严蔚敏版)——栈和队列(一)【栈和队列的定义和特点】

java小豪 2023-03-28 原文

第三章__栈和队列

3.1、栈和队列的定义和特点

3.1.1、栈的定义和特点

定义:

栈是是一种特殊的线性表,是限定在表尾进行插入或删除操作的线性表。又称为后进先出的线性表,简称LIFO

相关概念:

  • 表尾(即an端)称为栈顶Top;表头(即a1端)称为栈底Base
  • 插入元素到栈顶(即表尾)称为入栈
  • 栈顶(即表尾)删除最后一个元素的操作,称为出栈

入栈的操作示意图

出栈示意图

思考:a、b、c3个元素,入栈顺序是a、b、c,则他们的出栈顺序有几种可能:

栈的相关概念:

  1. 定义:限定只能在表的一端进行插入和删除运算的线性表(只能在栈顶操作)
  2. 逻辑结构: 与同线性表相同,仍为一对一关系
  3. 存储结构:用顺序栈或链栈存储均可,但以顺序栈更常见
  4. 运算规则:只能在栈顶运算,且访问结点时依照后进先出(LIFO)的原则
  5. 实现方式:关键是编写入栈和出栈函数,具体实现依顺序或链栈的不同而不同。

栈与一般线性表的不同:

栈与一般线性表的区别:仅在于运算规则不同

3.1.2、队列的定义和特点

  • 队列是一种先进先出(FIFO)的线性表。在表的一端插入(表尾),在另一端(表头)删除

队列相关概念:

  1. 定义:只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表
  2. 逻辑结构:与同线性表相同,仍为一对一关系
  3. 存储结构:顺序队链队,以循环顺序队列更常见
  4. 运算规则:只能在队首和队尾运算,且访问结点时依照先进先出的原则。
  5. 实现方式:关键时掌握入队出队操作,具体实现依顺序队或链队的不同而不同

3.2、案例引入

3.2.1、案例一:进制转换

十进制整数N向其它进制数d(二、八、十六)的转换是计算机实现计算的基本问题

  • 转换法则:除以d倒取余
  • 原理为:n = (n div d) * d + n mod d ,其中div为整除运算,mod为求余运算

例:把十进制数1348= 转换成八进制数为2504。

N N div 8 N mod 8
1348 168 4
168 21 0
21 2 5
2 0 2

3.2.2、案例二:括号匹配的检验

  • 假设表达式中允许包含两种括号:圆括号和方括号
  • 其嵌套的顺序随意,即:
    • ([] ()) 或 [ ( [] [] ) ]为正确格式
    • [ ( ] ) 或 ( [ () ) 或 ( ( ) ])为错误格式

3.2.3、案例三:表达式求值

表达式求值是程序设计语言编译中的一个基本问题,在实现时也需要运用栈。

实现:我们会使用算法——算符优先算法(运算符优先级确定运算顺序的表达式求值算法)

  • 表达式组成
    • 操作数:常数、变量
    • 运算符:算术运算符、关系运算符和逻辑运算符
    • 界限符:左右括弧和表达式结束符
  • 任何一个算术表达式都是由操作数(常数、变量)、算术运算符(+、-、*、/)和界限符(括号、表达式结束符 ’#‘、虚设的表达式起始符'#')组成。

3.2.4、案例四:舞伴问题

假设在舞会上,男士和女士各自排成一队,舞会开始时,依次从男队和女队的队头个出一人配成舞伴。如果两队初始人数不同,则较长的那一队未配对者等待下一轮舞曲。

有关数据结构(严蔚敏版)——栈和队列(一)【栈和队列的定义和特点】的更多相关文章

  1. ruby - Facter::Util::Uptime:Module 的未定义方法 get_uptime (NoMethodError) - 2

    我正在尝试设置一个puppet节点,但ruby​​gems似乎不正常。如果我通过它自己的二进制文件(/usr/lib/ruby/gems/1.8/gems/facter-1.5.8/bin/facter)在cli上运行facter,它工作正常,但如果我通过由ruby​​gems(/usr/bin/facter)安装的二进制文件,它抛出:/usr/lib/ruby/1.8/facter/uptime.rb:11:undefinedmethod`get_uptime'forFacter::Util::Uptime:Module(NoMethodError)from/usr/lib/ruby

  2. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过,我不想只删除标签,我想智能地保留尽可能多的格式。为插入换行符标签,检测段落并格式化它们等。输入非常简单,通常是格式良好的html(不是整个文档,只是一堆内容,通常没有anchor或图像)。我可以将几个正则表达式放在一起,让我达到80%,但我认为可能有一些现有的解决方案更智能。 最佳答案 首先,不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案,它会随着HTML的变化而崩溃,或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  3. ruby - 解析 RDFa、微数据等的最佳方式是什么,使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作,但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式,例如使用这个yaml文件,它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  4. ruby-on-rails - Rails 3.2.1 中 ActionMailer 中的未定义方法 'default_content_type=' - 2

    我在我的项目中添加了一个系统来重置用户密码并通过电子邮件将密码发送给他,以防他忘记密码。昨天它运行良好(当我实现它时)。当我今天尝试启动服务器时,出现以下错误。=>BootingWEBrick=>Rails3.2.1applicationstartingindevelopmentonhttp://0.0.0.0:3000=>Callwith-dtodetach=>Ctrl-CtoshutdownserverExiting/Users/vinayshenoy/.rvm/gems/ruby-1.9.3-p0/gems/actionmailer-3.2.1/lib/action_mailer

  5. ruby-on-rails - form_for 中不在模型中的自定义字段 - 2

    我想向我的Controller传递一个参数,它是一个简单的复选框,但我不知道如何在模型的form_for中引入它,这是我的观点:{:id=>'go_finance'}do|f|%>Transferirde:para:Entrada:"input",:placeholder=>"Quantofoiganho?"%>Saída:"output",:placeholder=>"Quantofoigasto?"%>Nota:我想做一个额外的复选框,但我该怎么做,模型中没有一个对象,而是一个要检查的对象,以便在Controller中创建一个ifelse,如果没有检查,请帮助我,非常感谢,谢谢

  6. ruby - 主要 :Object when running build from sublime 的未定义方法 `require_relative' - 2

    我已经从我的命令行中获得了一切,所以我可以运行rubymyfile并且它可以正常工作。但是当我尝试从sublime中运行它时,我得到了undefinedmethod`require_relative'formain:Object有人知道我的sublime设置中缺少什么吗?我正在使用OSX并安装了rvm。 最佳答案 或者,您可以只使用“require”,它应该可以正常工作。我认为“require_relative”仅适用于ruby​​1.9+ 关于ruby-主要:Objectwhenrun

  7. ruby - 在 Ruby 中有条件地定义函数 - 2

    我有一些代码在几个不同的位置之一运行:作为具有调试输出的命令行工具,作为不接受任何输出的更大程序的一部分,以及在Rails环境中。有时我需要根据代码的位置对代码进行细微的更改,我意识到以下样式似乎可行:print"Testingnestedfunctionsdefined\n"CLI=trueifCLIdeftest_printprint"CommandLineVersion\n"endelsedeftest_printprint"ReleaseVersion\n"endendtest_print()这导致:TestingnestedfunctionsdefinedCommandLin

  8. ruby - 定义方法参数的条件 - 2

    我有一个只接受一个参数的方法:defmy_method(number)end如果使用number调用方法,我该如何引发错误??通常,我如何定义方法参数的条件?比如我想在调用的时候报错:my_method(1) 最佳答案 您可以添加guard在函数的开头,如果参数无效则引发异常。例如:defmy_method(number)failArgumentError,"Inputshouldbegreaterthanorequalto2"ifnumbereputse.messageend#=>Inputshouldbegreaterthano

  9. ruby - 如何在 Grape 中定义哈希数组? - 2

    我使用Ember作为我的前端和GrapeAPI来为我的API提供服务。前端发送类似:{"service"=>{"name"=>"Name","duration"=>"30","user"=>nil,"organization"=>"org","category"=>nil,"description"=>"description","disabled"=>true,"color"=>nil,"availabilities"=>[{"day"=>"Saturday","enabled"=>false,"timeSlots"=>[{"startAt"=>"09:00AM","endAt"=>

  10. ruby - Ruby 有 `Pair` 数据类型吗? - 2

    有时我需要处理键/值数据。我不喜欢使用数组,因为它们在大小上没有限制(很容易不小心添加超过2个项目,而且您最终需要稍后验证大小)。此外,0和1的索引变成了魔数(MagicNumber),并且在传达含义方面做得很差(“当我说0时,我的意思是head...”)。散列也不合适,因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题,但我很想知道:Ruby标准库是否已经带有这样一个类? 最佳

随机推荐