草庐IT

详解数据结构中栈的定义和操作

华为云开发者社区 2023-09-13 原文
摘要：本文为大家详解数据结构中栈的定义和操作。

本文分享自华为云社区《数据结构：详细讲解栈的定义、栈的操作》，作者： 高彬滔 。

1.栈的定义

栈（stack）：是只允许在一端进行插入或者删除操作的线性表（即后进先出，大概可以理解为吃饱了吐出来）

  • 空栈：不含元素的空标配
  • 栈顶：表尾端
  • 栈底：表头端
  • 进栈顺序：a1->a2->a3->a4->a5
  • 出栈顺序：a5->a4-a3->a2->a1

2.对比线性表和栈基本操作

2.1 线性表的基本操作

  • InitList(&L):初始化表。构造一个空的线性表L，分配内存空间
  • DestoryList(&L):销毁操作。销毁线性表，并且释放线性表L所占用的空间
  • ListInsert(&L,i,e):插入操作，在表L中的第i个位置上插入指定元素e
  • ListDelete(&L,i,e):删除操作，删除表L中的第i个位置的元素，并且用e返回删除元素的值
  • LocateElem(L,e):按值查找操作，在表L中查找具有给定关键字值的元素
  • GetElem(L,i):按位查找操作，获取表L中第i个位置的元素的值

2.2 栈的基本操作

  • InitStack(&S):初始化栈，构造一个空栈S，分配内存空间
  • DestoryStack(&S):销毁栈，销毁并释放栈S所占用的内存空间
  • Push(&S,x):进栈，若栈S未满，则将x加入使之成为新的栈顶
  • Pop(&S,&x):出栈，若栈S非空，则弹出栈顶元素，并用x返回
  • GetTop(S,&x):读栈顶元素，若栈S非空，则用x返回栈顶元素

其他常见操作： StackEmpty(S):判断一个栈S是否为空，若S为空，则返回true，否则返回false

3.顺序栈

3.1顺序栈的定义

#define MaxSize 10           //定义栈中元素的最大个数 
typedef struct{
 ElemType data[MaxSize];   //静态数组存放栈中的元素
    int top;      //栈顶指针
}SqStack;         //结构体重命名

声明一个顺序栈后就会在内存中分配一整片连续的空间,其中内存大小为:MaxSize*sizeof(ELemType)

void testStack(){
 SqStack S; //声明一个顺序栈
}

3.2栈的初始化操作

由于栈顶指针top需要指向此时栈顶元素，所以让top指向0是不合理的，可以初始化让top指向-1;判断一个栈是否为空，即判断S.top是否等于-1

初始化栈：

void Inittack(SqStack){
 SqStack S;   //声明一个顺序栈
 S.top=-1;
}

判断栈空：

bool StackEmpty(SqStack S){
    if(S.top==-1)      //栈空
        return true;
    else 
        return false;  //非空
}

3.3进栈操作

分析：

  1. 判断栈是否为空
  2. 栈顶指针+1
  3. 新元素入栈
bool Push(SqStack &S,ElemType x){
 if(S.top==NaxSize-1)
        return false;
 S.top+=1;
 S.data[S.top]=x;
        return true;
}

3.4出栈操作

bool Push(SqStack &S,ElemType &x){
 if(S.top==-1)
        return false;
    x=S.data[S.top--];
        return true;
}

3.5读栈顶元素操作

bool GetTop(SqStack &S,ElemType &x){
 if(S.top==-1)
        return false;
    x=S.data[S.top];
        return true;
}

4.共享栈

两个栈共享同一片空间

#define MaxSize 10           //定义栈中元素的最大个数 
typedef struct{
 ElemType data[MaxSize];   //静态数组存放栈中的元素
    int top0;     //0号栈栈顶指针
    int top1;     //1号栈栈顶指针
}SqStack;         //结构体重命名
初始化栈：
void InitStack(ShStack &S){
 S.top0=-1;
 S.top1=MaxSize;
}

5.链栈的定义

  • 进栈/出栈都只能在栈顶一段进行
  • 链头作为栈顶
typedef struct Linknode{
 ElemType data;           //数据域
    struct Linknode *next;   //指针域
}*LiStack                    //栈类型定义

 

点击关注，第一时间了解华为云新鲜技术~

详解数据结构spancolorstyle代码与软件发布

有关详解数据结构中栈的定义和操作的更多相关文章

  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标准库是否已经带有这样一个类？ 最佳

随机推荐