栈(最全的概念)-----最通俗易懂的文章-程序员宅基地

技术标签:   数据结构  

简要

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

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

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

#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

智能推荐

(转载)java synchronized详解-程序员宅基地

文章浏览阅读422次。java synchronized详解记下来,很重要。Java语言的关键字,当它用来修饰一个方法或者一个代码块的时候,能够保证在同一时刻最多只有一个线程执行该段代码。 一、当两个并发线程访问同一个对象object中的这个synchronized(this)同步代码块时,一个时间内只能有一个线程得到执行。另一个线程必须等待当前线程执行完这个代码块以后才能执行该代码块..._java make synchronized invalid

Android 多种投屏神器(Vysor,Total Control,scrcpy )-程序员宅基地

文章浏览阅读1.9w次,点赞6次,收藏32次。一,Vysor1,Vysor特点及优点特点或者说优点:极强的跨平台性能,Mac、Windows、Linux系统上都可以用;免费;无需Android系统Root 即可玩转电脑控制Android 设备;2,官网https://www.vysor.io/3,使用3.1,Win客户端(建议使用)直接下载windows客户端安装,运行就可以使用,使用也很简单,可以通过局域网和数据线连接Android设备,然后实现投屏;3.2,Chrome浏览器3.2.1,从官网Download进入_total control

Java反射机制_object o3 = m; object o4 = n; system.out.println(o-程序员宅基地

文章浏览阅读144次。概念:在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法;对于任意一个对象,都能够调用它的任意方法和属性;这种动态获取信息以及动态调用对象方法的功能称为 Java 语言的反射机制。简单来说,反射机制指的是程序在运行时能够获取自身的信息。在 Java 中,只要给定类的名字,就可以通过反射机制来获得类的所有信息。类的加载机制:new 对象()1.JVM加载对象.class文件1.1JVM在硬盘找对象.class文件并读取到内存中1.2JVM自动创建..._object o3 = m; object o4 = n; system.out.println(o3 == o4)

NDK各个版本,待后续更新_android-ndk-r10e和ndk 29差别-程序员宅基地

文章浏览阅读414次。ndk_r15c (July 2017)Windows 32-bit :https://dl.google.com/android/repository/android-ndk-r15c-windows-x86.zipWindows 64-bit :https://dl.google.com/android/repository/android-ndk-r15c-windows-x86_64.zipMac OS X :https://dl.google.com/android/repositor_android-ndk-r10e和ndk 29差别

Linux常用命令—grep_linux命令+grep-程序员宅基地

文章浏览阅读4.1k次,点赞3次,收藏16次。简介grep命令(Global Regular Expression Print)是 Linux系统中一种强大的文本搜索工具,它能使用正则表达式搜索文本,并把匹 配的行打印出来 。grep 是linux中最为常用的三大文本(awk,sed,grep)处理工具之一,所以有必要掌握其用法。grep家族总共有三个成员构成:grep、egrep、fgrep。使用格式grep [选项] ..._linux命令+grep

关于the selection cannot be run on any server错误的问题,如何快速的解决。-程序员宅基地

文章浏览阅读3.9w次,点赞29次,收藏121次。最近在导入外来项目时,遇到了一个难题,就是出现了图中的错误。the selection cannot be run on any server(无法在任何服务器上运行所选内容)这个错误的原因在于Dynamic Web Module 的版本与server不匹配。Dynamic Web Module的版本可以通过右键项目名-&gt;properties-&gt;Project Facets可以..._the selection cannot be run on any server

随便推点

Cookie,会话,令牌-程序员宅基地

文章浏览阅读804次。会话cookieAre you new to web-development, feeling confused with different Web Storage elements? 您是Web开发的新手,对不同的Web存储元素感到困惑吗? If yes, then you are at the right place This article will give you a brief e..._会话和令牌

Linux查找文本中指定字符的小技巧_linux查找指定字符后的数据-程序员宅基地

文章浏览阅读3.6k次。在Linux的vi编辑器中,如果要查看指定文件中的某项内容,由于内容过于庞大,可以打开vi编辑器后再打一个【/】,括号中间的字符,然后输入你要查找的字符这样就可以找到你需要的字符了,方便我们查看大容量的日志文件。_linux查找指定字符后的数据

编译chromium 总结_<includepath>$(includepath);$(dxsdk_dir)include</i-程序员宅基地

文章浏览阅读2.5k次。编译chromium 总结http://www.chromium.org/developers/how-tos/build-instructions-windows这是官网的详细地址,但我只用他的说明还不够 可以参考这篇文章http://blog.sina.com.cn/s/blog_41608ead0101578b.htmlwin7+vs2010+vs2010SP1+DIR_$(includepath);$(dxsdk_dir)include

Struts-笔记-2-程序员宅基地

文章浏览阅读61次。2 .搭建Struts开发环境 2.1 搭建环境l 导入jar 包。 Add Library 导入jar包 l 建立一个配置文件:struts-config.xml &lt...

【杭电oj】1872 - 稳定排序(结构体排序)_wygoj-程序员宅基地

文章浏览阅读695次。稳定排序Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4632 Accepted Submission(s): 1802Problem Description大家都知道,快速排序是不稳定的排序方法。_wygoj

Java中 GC是什么_gc钱包是干嘛的?-程序员宅基地

文章浏览阅读2.3w次,点赞9次,收藏17次。Java GC(Garbage Collection,垃圾收集,垃圾回收)机制,是Java与C++/C的主要区别之一,在使用JAVA的时候,一般不需要专门编写内存回收和垃圾清理代 码。这是因为在Java虚拟机中,存在自动内存管理和垃圾清扫机制。电脑的内存大小的不变的,当我们使用对象的时候,如使用New关键字的时候,就会在内存中生产一个对象,但是我们在使用JAVA开发的时候,当一个对象使用完_gc钱包是干嘛的?

推荐文章

热门文章

相关标签