栈(最全的概念)-----最通俗易懂的文章_斑马森林m的博客-程序员宝宝

技术标签:   数据结构  

简要

栈和队列都是线性表的一种,所以类型差不多,之前说数据结构其实单位都为结构体,磊成抽象的一种结构,就像搭房子一样,原材料一样,只不过搭出来的样式不同。

首先栈也是一种线性表,因此也有顺序和链式结构,比较常用的为顺序栈,栈的抽象 结构图为
在这里插入图片描述
栈的抽象结构和一个容器相同,比如水杯,底部为密封上方为开口,因此栈的存储数据都是从上方增删该除。放数据为进栈,拿数据则叫出栈。拿出其实就是相当于从栈中删除数据,比如你想拿底部的数据,必须将其上面的数据取出,才可以获取底部的数据。

因此栈的特点就是只能从上面来改动数据,但是它也是线性表的一种,和顺序链式表的结构相似,因此顺序栈其实也只有一个结构体,然后在里面开辟一段空间存储数据。下面为顺序栈结构体的定义

#define maxnumber 20         //定义该栈最大的储存个数,当超过了需要扩大最大值
typedef struct
{
    
   ElemType *base;       //定义基底,相当于顺序表中的数组指针,来存放数据
   ElemType *top;        //定义栈顶指针,主要用来监控,比如栈是否满了,还有最主要的出栈,拿数据,因为你不能从栈底拿吧,所以要定义一个栈顶指针
   int StackLength;     //来确定初始化的最大长度,每当满了需要再重新夸大长度,只起到一个监控长度的作用
}Stack;

typedef的作用就不说了,在线性表文章中有解释,俩个指针的定义和作用如下图在这里插入图片描述
在刚刚定义时候, top和base指针同时指向一个地方,表示该栈为空,因此就得出,每当指针top和base的地址相同时候,该栈为空,第二个图为插入了一个数据,每当插入时候,top指针的地址+1,每当删除栈顶的时候,top指针地址-1,top指针总是指向一个空的地址如图所示,用top地址减去base的地址就可以得出栈里存放数据的个数,例如第二个图,base地址为1,top则为2,2-1=1,因此得出栈里数据的个数为1;

一.栈的初始化

和顺序线性表一样,顺序栈只有一个结构体所以 ,先定义一个结构体

Stack stack1;            //定义了一个栈
int InitStack(Stack &S)         //定义初始化栈函数
{
    
  S.base=(ElemType*)malloc(number*sizeof(ElemType))//这里顺序栈因为只有一个结构体,而不是结构体指针,这里的和顺序线性表相同,这里其实就是一个数组指针,用来存放数据
  if(!S.base) return 0;      //开辟完内存空间后一般都要判断是否开辟成功
  S.top=S.base;            //命令该栈为空才可以进行操作
  S.StackLength=maxnumber;   //确定最大长度,只是一个监控的作用,并没有什么实际作用
}
进栈(压栈)

往你创建好的栈里放数据称为进栈,也称为压栈,之前说过,只能从栈顶的方向放数据,也就是你杯子只能从上面的口倒水,不能从杯底吧。进栈在前面说过每当插入的时候,top指针就会+1,初始化时候top与base指针指向相同,所以我们可以得出进栈的算法:

int Push(Stack &S,ELemType e)            //参数为绑定的栈和你要插入的数据
{
    
  if(S.top-S.base>=S.StackLength)        //顺序结构首先都要判断是否已经满了,俩地址相减为栈中元素的个数
  {
    
     S.base=(Elemtype*)realloc(S.base,(S.StackLength+10)*sizeof(ElemType))      //这里假设扩大10个位置
     if(!S.base)  return 0;         //美当创建好空间和重现扩张空间后都要进行是否分配成功的判断
     S.top=S.base+S.StackLength;       //重新分配内存后,top指针可能缺失重新定义
     S.StackLength+=10//S.StackLength实现监控栈长度的功能,因此当增加长度时候,需要改变
  }
  *S.top++=e;        //top总是指向空的,因此先向top指针指向的区域填入值,然后实现++使top指针上移一位,可以看上面的解释图
}

从上面代码可以看出,top指针在进栈的时候起到作用,相当于游标的作用,先往top指针指向的区域存值,然后top指针上移

有了进栈肯定就有出栈

出栈(弹栈)

出栈就是从栈顶拿出数据并消除数据

int Pop(Stack &s,ElemType e)        //参数为绑定的栈和你要返回的数据
{
    
   if(S.base==S.top) return 0;    //首先判断是否为空栈
   e=*--S.top;         //先实现top指针地址--再取值,因为如图top指向的位置
                       //可以设置返回值取决于函数功能
}

以上就是出栈的算法,通过上面的进出,得出想往顺序表中插入数据首先检查是否已经满了,取数据时候看1是否为空,栈也是线性表的一种,因此也实用。

栈常用实例

一.进制转换,由十进制转化为八进制或二进制

首先熟悉进制转换的步骤,可以网上查询。比如十进制转换为八进制(1087)10

1.1087除以8得135余7
2.135除以8得16余7
3.16除以8得2余0
4.2除以8得0余2

因此转化为八进制为(2077)8以上得出来的是从后到前的结果,可以实例到栈类型中,利用栈的抽象模型,将先算出来的余数放入栈中,算完后,再从栈顶中取出,结果正好是计算的结果,满足先进后出的原则,可以画图理解一下,

可以得出算法:
首先定义一个栈,计算得出的余数入栈,然后再出栈,得出来的数就是结果
首先定义一个栈

void InitStack(Stack &S)     //定义实例化函数
{
    
  S.base=(int*)malloc(number*sizeof(int));     //这里假设存储的为int类型,因为余数都为int类型  
  S.top=S.base;
  S.StackLength=number;        ///完成实例化    
}

然后定义一个入栈的实例化函数,上面有介绍,下面来实例化

void Push(Stack &S,int e)
 {
    
  if(S.top-S.base>=S.StackLength)
  {
    
   S.base=(int*)realloc(S.base,(number+5)*sizeof(int));
   S.top=S.base+S.StackLength;
   S.StackLength+=5;
  }
  *S.top++=e; 
 }

然后定义一个出栈的函数

int Pop(Stack &S)            //设置弹栈返回栈顶的一个数
 {
    
  if(S.top==S.base)  return 0;
  return *--S.top;         
 }

定义了三个函数,就可以方便使用栈了,首先定义好一个栈,然后放数据,最后再取数据
下面为main()函数的操作

#include <stdio.h>        //c语言必不可少的库函数
#include <stdlib.h>       //malloc,realloc,free的函数库
#define number20         //首先定义栈的初始化最大长度

                         //把上面三个函数写进来,这里省略了过程
int main()
{
    
  Stack S;                //创建栈
  InitStack(S);           //初始化栈
  int x;                
  printf("请输入一个数:"); 
  scanf("%d",&x);
  while(x!=0)             //将每次计算得到的余数放入栈中,不理解的同学可以画图
  {
    
   Push(S,x%8);
   x=x/8;                 //因为你int类型除法得到小数时候,也会取整,所以使用这个,利用进制转换规则开始循环,可以假设一个数自己试试
  }
 while(S.top!=S.base)
 {
    
  printf("%d",Pop(S));   //你已经计算完了,所以该出栈了,取数据了循环到top指针余base指针指向相同的地址退出
 }
 free(S.base);           //栈使用完了,释放base的空间  
}

c要求严谨,这里的free只是释放你分配的内存,但是不会使你的指针地址为NULL,为了防止野指针的出现也可以在最后设置 S.base=S.top=NULL;
以上就是进制转换的算法 。

括号是否匹配问题

括号是否匹配值得是你输入一段字符,看左右括号是否匹配,例如 ( [ ] )
,[ () () ]等为括号匹配,而 [ ( ] } 为括号不匹配,显而易见因此当我们输入一串字符时候,如何去判断括号是否匹配,先将( [ { 放入栈中,然后后面 出现了) } ]则弹栈,他们符合就近原则匹配,即你后面输入为’ ) '则弹栈出来的必须为 ’ ( ’ 否则则错误

简单来说,栈内放的全是( [ {,每当遇到 ) ] }就会判断弹栈出来的是否匹配

首先还是上面三个栈的函数定义,初始化,入栈和出栈,这里省略了直接写main函数:

 void main()
{
    
 Stack S;
 InitStack(S);          //首先进行实例化栈的操作 
 char a[4000];
 scanf("%s",&a);        //你要进行判断的字符串先放到数组里
 int i=0;
 while(a[i]!='\0')      //对数组进行循环,如果为({[先放入栈中,如果为)}]则弹栈,进行判断是否符合要求
 {
    
  switch(a[i])
  {
    
   case '(':
   case '[':
   case '{':
    Push(S,a[i]);          //循环一段你输入字符串数组,如果为为前括号,则入栈
    break; 
   case ')':
   if(Pop(S)!='(')
   {
    
    printf("括号匹配错误");      //当字符串中出现后面的括号时候进行判断,看弹栈出来的前括号是否匹配,如果匹配则什么事情也没有,继续执行下面的,并且用Pop函数会使栈顶指针下移,进行下一次判断使用,只要不匹配,直接停止运行,下面道理也如此
    return 0;
   }
   break;
  case ']':
   if(Pop(S)!='[')
   {
    
    printf("括号匹配错误");
    return 0;
   }
   break;
  case '}':
   if(Pop(S)!='{')
   {
    
    printf("括号匹配错误");
    return 0;
   }
   break;
  }
  i++;
 }
 printf("括号匹配成功");      //因为只要有一次不匹配就会退出程序,所以当前面一路无阻的话,退出while循环,说明括号匹配成功
 }

当深刻了解上面俩个实例后,迷宫问题自然有了解决思路。

最近发现了一个国外挺牛的网站,将所有数据结构都实现了可视化。你可以调节演示速度,有各种算法演示,比如什么查找之类,红黑树,什么都有。可能就是全英文,看不懂的可以用浏览器的翻译软件。地址如下:

数据结构可视化

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43767511/article/details/104901987

智能推荐

力扣||1.两数之和--Golang_Guolvy的博客-程序员宝宝_golang 两数之和

力扣||1.两数之和–Golang知识点:数组难度:简单题目:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。示例给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] =...

我最近的C++学习之路_奔跑的龙少的博客-程序员宝宝

学习编程的路径千千万,我感觉可以这样学:1.有点C语言基础2.找一本C++的入门书籍,熟悉所有语法3.能够写简单的程序4.能够自己写类5.能够做多线程,多进程6.能够完成类与类之间的通信,以及进程间/线程间通信。7.熟练使用库:类似STL8.能够解决大部分编程问题。9.成为更高水平的程序员。

禁用表单请求验证_kklvgl的博客-程序员宝宝

请求验证过程检测到有潜在危险的客户端输入值,对请求的处理将中止。该值可能指示危及应用程序安全的尝试,如跨站点的脚本攻击。可通过在Page指令或web.config中设置validateRequest=false禁用请求验证。但是,在这种情况下,强烈建议应用程序显式检查所有输入。 解决方法:方法1:在.aspx页面中添加:    方法2:修改Web.Config文件:        

哪些软件可以写PHP,用来写php的软件_联想拯救者的博客-程序员宝宝

用哪种软件做PHP开发首先你得先了解一下编程序的基本思想,和一些流程,学一下怎么画流程图。然后找个明白人给你配置以下服务器(一般是用Apecha),安装php的编译器(注意是编译器 不是编辑器),再弄一个好一点编辑器(比如EditPlus)。编译器用来“运行”(其实是编译不是运行,但是我害怕我说编译你不太明白)程序,编辑器用来写程序。接下来弄一个php的手册,就是chm格式的,学习php的基本语法...

textarea placeholder 不显示_灬宣的博客-程序员宝宝

&lt;textarea&gt;&lt;/textarea&gt;标签之间不要有空格!!!例如:&lt;textarea name="textarea" rows="5" cols="20" placeholder="请输入信息"&gt;&lt;/textarea&gt;上面这行代码可以显示placeholder属性的值。 &lt;textarea name="textarea" row...

随便推点

@ManyToOne注解 与 @OneToMany_ATwill...的博客-程序员宝宝

@ManyToOne注解的这端,是多端1.在注释@ManyToOne(cascade=CascadeType.REFRESH,optional=true)中将属性optional设置为true,这可以使得即使外键为空时仍可以向表中添加数据。2.假设Person和Book是一对多的关系,其中Person的成员变量为:private Integer personId;p

UVC支持的摄像头列表_皮熊的博客-程序员宝宝

0c45:62f1Avatec CMA-L688HueHDSonix TechnologyHueHD [11]http://www.ideasonboard.org/uvc/#footnote-11终于找到了一个榜上有名的摄像头.[ 1668.113785] usb 3-1: new high-speed USB device numbe

CV/DL基础知识 之 深入理解Batch Normalization -我觉得很多人用正态分布来解释是错误的_isErik的博客-程序员宝宝

CV/DL基础知识 之 深入理解Batch Normalization前言关于Batch NormalizationBut, why?1,均匀分布前言关于Batch Normalization的作用和流程请参考郭耀华的博客,博主写的非常详尽了,本文主要深入探讨为什么Normalization之后,能够将神经元中激活函数的输入能够很好的集中在[-1,1]之间。一般的解释是:假设输入服从正态分布来解释,然而本人觉得这是相对片面的,本文将从多种分布来进一步研究该问题。关于Batch Normalizatio

Springboot整合tomcat数据库连接池[email protected]的博客-程序员宝宝

1、配置文件spring: datasource: type: com.zaxxer.hikari.HikariDataSource jdbcUrl: jdbc:mysql://127.0.0.1:8080/database?useUnicode=true&amp;characterEncoding=utf-8&amp;useSSL=true username: root password: 12345678 driv

eMTC技术可以应用到哪些行业?_江西天行智慧科技的博客-程序员宝宝_emtc的应用

       eMTC技术是物联网技术的一个重要分支,eMTC技术拥有支持语音、可移动性、传输速率高等特点,eMTC技术可以被广泛应用到很多行业。       eMTC技术应用到车载车辆管理。因为eMTC可移动性以及支持语音,对于车辆管理跟踪定位有很大作用。前几天,120车辆从被呼叫到接走病人花了40多分钟,这个时间对于病人来说太长太长了,面对抢救,时间就是生命。呼叫120的人花了好几分钟和120...

java正则 以多个开头,Java,正则表达式HasNext以空行开头,支持多平台_Elaine要当律师的博客-程序员宝宝

I need to process the following file on Unix and Windows:a;bc;d;e;f;gc;d;e;f;gc;d;e;f;ga;bc;d;e;f;gc;d;e;f;gc;d;e;f;ga;ba;bc;d;e;f;gc;d;e;f;gc;d;e;f;gi need to process a;b that contain a block of data...

推荐文章

热门文章

相关标签