精华内容
下载资源
问答
  • 一.简介 在哔哩哔哩看视频学的,赫斌老师数据结构入门的内容-b站搜索:av6159200(P33),通过学习,能独立把赫斌...简介已经说了,栈可以分为静态栈和动态栈. 静态栈是用数组来实现而动态栈是用链表来实现. 栈实现的功能...

    一.简介

    哔哩哔哩看视频学的,赫斌老师数据结构入门的内容-b站搜索:av6159200(P33),通过学习,能独立把赫斌老师教的敲出来,由于动态栈(链表阉割版)的功能很少,我并没有增加什么其它功能,但是我自己实现了静态栈(数组阉割版),还有就是分享一些我对动态栈,以及静态栈的理解.

    二.什么是栈

    简介已经说了,栈可以分为静态栈和动态栈.

    静态栈是用数组来实现动态栈是用链表来实现.

    栈实现的功能就是:先进后出.

    打个比喻就是把一块一块的方块放进一个箱子里,等到你不想放,想要从箱子取出来的时候,第一个出来的,就是你最后一次放的,而最后一个出来的,只能是最后一个出来,这就是所谓的先进后出.

    具体图解在这里插入图片描述

    栈的实现需要确定顶部底部.

    静态栈与动态栈的区别:

          静态栈必须提前确定栈的大小(有限的),并且都是连续的.
    
          动态栈可以无限大小(内存够的情况下),并且是不连续的.
    

    三.动态栈的图解

    在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
    由于图片较多…具体可以链接下载详看:百度网盘

    四.函数功能实现的源码

    理解不了可以看第三部分的图解

    void init(PSTACK);	                                    	//初始化
    

    在这里插入图片描述

    void push_stack(PSTACK , int);	                            //入栈(压栈)
    

    在这里插入图片描述

    void traversal_output(PSTACK );	                             //遍历输出
    

    在这里插入图片描述

    int air(PSTACK );	                              	//判断是否为空
    

    在这里插入图片描述

    int pop(PSTACK , int*);	                                    	//出栈
    

    在这里插入图片描述

    void empty(PSTACK );	                              //清空栈
    

    在这里插入图片描述

    五.源码分享(可复现)

    动态栈链接:百度网盘

    静态栈链接:百度网盘

    六.栈可以应用在那些方面

    1.函数调用

    2.中断

    3.表达式求值(计算器)

    4.内存分配

    5.缓冲处理

    6.迷宫

    展开全文
  • 动态变量和静态变量的区别: 1、存储位置 动态变量:存储在内存出栈数据区 静态变量:存储在全局数据区(静态数据区) 2、生命期 动态变量:根据你定义的位置确定,比如你在一个函数中定义的,那么超出该函数...

    动态变量和静态变量的区别:

    1、存储位置

    动态变量:存储在内存出栈数据区

    静态变量:存储在全局数据区(静态数据区)

    2、生命期

    动态变量:根据你定义的位置确定,比如你在一个函数中定义的,那么超出该函数范围变量将失效

    静态变量:程序结束时才释放

    3、作用域

    动态变量:同样的要根据你定义的位置才能确定,和第二点的一样

    静态变量:当前文件中有效

    堆和栈的区分:

    堆(Heap)栈(Stack)

    1、内存分配方面:

    堆:一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事,分配方式是类似于链表。可能用到的关键字如下:newmallocdeletefree等等。

    栈:由编译器(Compiler)自动分配释放,存放函数的参数值局部变量的值等。其操作方式类似于数据结构中的栈。

    2、申请方式方面:

    堆:需要程序员自己申请,并指明大小。在c中malloc函数如p1 = (char *)malloc(10);在C++中用new运算符,但是注意p1、p2本身是在栈中的。因为他们还是可以认为是局部变量。

    栈:由系统自动分配。 例如,声明在函数中一个局部变量 int b;系统自动在栈中为b开辟空间。

    3、系统响应方面:

    堆:操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序,另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小,这样代码中的delete语句才能正确的释放本内存空间。另外由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。

    栈:只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出。

    4、大小限制方面:

    堆:是向高地址扩展的数据结构,是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见,堆获得的空间比较灵活,也比较大。

    栈:在Windows下, 栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在WINDOWS下,栈的大小是固定的(是一个编译时就确定的常数),如果申请的空间超过栈的剩余空间时,将提示overflow。因此,能从栈获得的空间较小。

    5、效率方面:

    堆:是由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便,另外,在WINDOWS下,最好的方式是用VirtualAlloc分配内存,他不是在堆,也不是在栈是直接在进程的地址空间中保留一快内存,虽然用起来最不方便。但是速度快,也最灵活。

    栈:由系统自动分配,速度较快。但程序员是无法控制的。

    6、存放内容方面:

    堆:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。

    栈:在函数调用时第一个进栈的是主函数中后的下一条指令(函数调用语句的下一条可执行语句)的地址然后是函数的各个参数,在大多数的C编译器中,参数是由右往左入栈,然后是函数中的局部变量。 注意: 静态变量是不入栈的。当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地址,也就是主函数中的下一条指令,程序由该点继续运行

    7、存取效率方面:

    堆:char *s1 = “Hellow Word”;是在编译时就确定的;

    栈:char s1[] = “Hellow Word”; 是在运行时赋值的;用数组比用指针速度要快一些,因为指针在底层汇编中需要用edx寄存器中转一下,而数组在栈上直接读取。

    展开全文
  • 动态存储区、静态存储区、堆和栈区别

    千次阅读 多人点赞 2018-09-11 12:43:46
    动态存储区、静态存储区、堆和栈区别 内存中用户存储空间的分配情况(三种) 程序区:存放程序语句 静态存储区 动态存储区  ...

    动态存储区、静态存储区、堆和栈的区别

    内存中用户存储空间的分配情况(三种)

    程序区:存放程序语句

    静态存储区

    动态存储区

                                                                                                                                                                            

    ***动态存储方式----->动态存储区

    栈:由编译器自动分配释放,存放函数的参数值,局部变量等值。其操作方式类似于数据结构中的栈。

    会存放函数的返回地址、参数和局部变量

    堆:一般由程序员分配释放,   若程序员不释放,程序结束时可能由OS回收。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表,呵呵。

    查看后续更加具体的栈和堆的区别 [1]

    **静态存储方式----->静态存储区---------静态区/全局区

    常量、常变量(const 变量)、静态变量、全局变量

                                                                                                                                                              

    由C/C++编译的程序占用的内存分为以下几个部分:

    1. 栈区(stack
    2. 堆区(heap
    3. 全局区(静态区)(static
    4. 文字常量区-----------常量字符串就是放在这里的。 程序结束后由系统释放
    5. 程序代码区

                                                                                                                                                                

    [1]堆和栈的区别

    (一) 申请方式

    • 栈(satck:由系统自动分配
    1. 程序运行时由编译器自动分配的一块连续的内容,存放函数的参数值,局部变量的值等。 例如,声明在函数中一个局部变量int b;系统自动在栈中为b开辟空间。
    2. 程序结束时由编译器自动释放
    3. 栈由系统自动分配,程序员无法控制
    4. 只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出。
    5. 存取方式,先进后出
    • 堆(heap):
    1. 在内存开辟另一块不连续的存储区域。一般由程序员分配释放
    2. 若程序员不释放,程序结束时由系统回收
    3. 首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序。
    4. 需程序员自己申请(调用malloc,realloc,calloc),并指明大小,并由程序员进行释放。容易产生memory leak.

    (二) 申请大小的限制

    • 栈:在windows下,栈是向底地址扩展的数据结构,是一块连续的内存区域(它的生长方向与内存的生长方向相反)。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在 WINDOWS下,栈的大小是2M(也有的说是1M,总之是一个编译时就确定的常数)。

    栈的大小是固定的。如果申请的空间超过栈的剩余空间时,将提示overflow。因此,能从栈获得的空间较小。

    • 堆:堆是高地址扩展的数据结构(它的生长方向与内存的生长方向相同),是不连续的内存区域。这是由于系统使用链表来存储空闲内存地址的,自然是不连续的,而链表的遍历方向是由底地址向高地址堆的大小受限于计算机系统中有效的虚拟内存。由此可见,堆获得的空间比较灵活,也比较大。

    (三) 系统响应:

    • 栈:只要栈的空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出
    • 堆:首先应该知道操作系统有一个记录空闲内存地址的链表,但系统收到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲链表中删除,并将该结点的空间分配给程序,另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小,这样,代码中的free语句才能正确的释放本内存空间。另外,找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。

    说明:

    (1)对于堆来讲,频繁的new/delete势必会造成内存空间的不连续,从而造成大量的碎片,使程序效率降低。

    (2)对于栈来讲,则不会存在这个问题,

    (四) 申请效率的比较

    (1)栈由系统自动分配,速度快。但程序员是无法控制的

    (2)堆是由malloc分配的内存,一般速度比较慢,而且容易产生碎片,不过用起来最方便。

    另外,在WINDOWS下,最好的方式是用VirtualAlloc分配内存,他不是在堆,也不是在栈,是直接在进程的地址空间中保留一块内存,虽然用起来最不方便。但是速度快,也最灵活。

    (五) 堆和栈中的存储内容

    • 栈:在函数调用时,第一个进栈的主函数中后的下一条语句的地址,然后是函数的各个参数,参数是从右往左入栈的,然后是函数中的局部变量。注:静态变量是不入栈的。当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地址,也就是主函数中的下一条指令,程序由该点继续执行。
    • 堆:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容由程序员安排。

    (六) 存取效率的比较

    (1)堆:char *s1=”hellow tigerjibo”;hellow tigerjibo是在编译时就确定的

    (2)栈:char s1[]=”hellow tigerjibo”;hellow tigerjibo是在运行时赋值的;

    数组比用指针速度更快一些,指针在底层汇编中需要用edx寄存器中转一下。

    数组在栈读取时直接就把字符串中的元素读到寄存器cl中,而堆则要先把指针值读到edx中,再根据edx读取字符,显然慢了。

    补充:

           栈是机器系统提供的数据结构,计算机会在底层对栈提供支持:分配专门的寄存器存放栈的地址,压栈出栈都有专门的指令执行,这就决定了栈的效率比较高。

           堆则是C/C++函数库提供的,它的机制是很复杂的,例如为了分配一块内存,库函数会按照一定的算法(具体的算法可以参考数据结构/操作系统)在堆内存中搜索可用的足够大小的空间,如果没有足够大小的空间(可能是由于内存碎片太多),就有可能调用系统功能去增加程序数据段的内存空间,这样就有机会分到足够大小的内存,然后进行返回。显然,堆的效率比栈要低得多。

    (七) 分配方式:

    (1)堆都是动态分配的,没有静态分配的堆。

    (2)栈有两种分配方式:静态分配和动态分配。静态分配是编译器完成的,比如局部变量的分配。动态分配由alloca函数进行分配,但是栈的动态分配和堆是不同的。它的动态分配是由编译器进行释放,无需手工实现。

    展开全文
  • 数据结构 - 静态顺序存储

    千次阅读 2015-04-29 09:04:23
    (Stack):是限制在表的一端进行插入删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。 栈顶(Top):允许进行插入、删除操作的一端,又称为表尾。用栈顶...

    1 栈的概念
    栈(Stack):是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。
    栈顶(Top):允许进行插入、删除操作的一端,又称为表尾。用栈顶指针(top)来指示栈顶元素。
    栈底(Bottom):是固定端,又称为表头。
    空栈:当表中没有元素时称为空栈。

    设栈S=(a1,a2,…an),则a1称为栈底元素,an为栈顶元素,如图3-1所示。
    栈中元素按a1,a2,…an的次序进栈,退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。
    

    栈的抽象数据类型定义

    ADT Stack{
    数据对象:D ={ ai|ai∈ElemSet, i=1,2,…,n,n≥0 }
    数据关系:R ={(ai-1, ai)| ai -1, ai ∈D, i=2,3,…,n }
    基本操作:初始化、进栈、出栈、取栈顶元素、求栈的长度、判断栈是否为空等
    } ADT Stack

    栈的静态顺序存储表示

    采用静态一维数组来存储栈。
    

    ◆ 栈底固定不变的;栈顶则随着进栈和退栈操作而变化,用一个整型变量top(称为栈顶指针)来指示当前栈顶位置。
    ◆ 用top=0表示栈空的初始状态,每次top指向栈顶在数组中的存储位置。
    ◆ 结点进栈:首先执行top加1,使top指向新的栈顶位置,然后将数据元素保存到栈顶(top所指的当前位置)。
    ◆ 结点出栈:首先把top指向的栈顶元素取出,然后执行top减1,使top指向新的栈顶位置。

    栈的基本操作的实现

      栈的类型定义
    define  MAX_STACK_SIZE  100      /*  栈向量大小  */
    typedef  int  ElemType ;
    typedef struct  sqstack
    {  ElemType   stack_array[MAX_STACK_SIZE] ;
    int  bottom; //栈底,实为数组下标
    int  top;  //栈顶,实为数组下标
    }SqStack ;
    栈的初始化
    SqStack Init_Stack(void)
    {    SqStack  S ;
    S.bottom=S.top=0 ;  
    return(S) ;
    }
    
     压栈(元素进栈)
    Status push(SqStack &S , ElemType  e)
       /*  使数据元素e进栈成为新的栈顶  */
    {  if  (S.top==MAX_STACK_SIZE-1) 
    return  ERROR;      /*  栈满,返回错误标志    */
    S.top++ ;  /* 栈顶指针加1,下标为0的位置不放元素  */
    S.stack_array[S.top]=e  ;   /* e成为新的栈顶  */
    return OK;        /*  压栈成功    */
    }
    思考:若调换S.top++ 和S.stack_array[S.top]=e 的位置,结果如何?
    
    弹栈(元素出栈)
    ElemType  pop( SqStack   &S)
          /*弹出栈顶元素*/
    {  if ( S.top==0 )
    return ERROR ;       /*  栈空,返回错误标志    */
    e=S.stack_array[S.top] ;  
    S.top-- ;  
    return e ;  
    }
    

    当栈满时做进栈运算必定产生空间溢出,简称“上溢”。上溢是一种出错状态,应设法避免。
    当栈空时做退栈运算也将产生溢出,简称“下溢”。下溢则可能是正常现象,因为栈在使用时,其初态或终态都是空栈,所以下溢常用来作为控制转移的条件。

    栈的动态顺序存储表示

    采用动态一维数组来存储栈。所谓动态,指的是栈的大小可以根据需要增加。
    

    ◆ 用bottom表示栈底指针,栈底固定不变;栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位置。
    ◆ 用top=bottom作为栈空的标记,每次top指向栈顶数组中的下一个存储位置(或指向栈顶元素)。
    ◆ 结点进栈:判断栈是否已满,如果栈满,则重新申请更大的内存空间,然后将数据元素保存到栈顶(top所指的当前位置),然后执行top加1,使top指向栈顶的下一个存储位置;
    ◆ 结点出栈:首先执行top减1,使top指向栈顶元素的存储位置,然后将栈顶元素取出。

    基本操作的实现

    1 栈的类型定义
    #define  STACK_SIZE  100    /*  栈初始向量大小  */
    #define STACKINCREMENT 10   /*  存储空间分配增量  */
    typedef  int  ElemType ;
    typedef struct sqstack
    {   ElemType  *bottom;     /*  栈不存在时值为NULL  */
    ElemType  *top;      /*  栈顶指针  */
    int   stacksize ;   /*  当前已分配空间,以元素为单位  */
    }SqStack ;
    2  栈的初始化
    Status Init_Stack(SqStack  *S )
    {
    S ->bottom=(ElemType *)malloc(STACK_SIZE *sizeof(ElemType));
    if (! S -> bottom) //若返回空指针,内存分配失败
        return  ERROR;
    S -> top=S -> bottom ;  /*  栈空时栈顶和栈底指针相同  */
    S -> stacksize=STACK_SIZE; 
    return OK ;
    }
    
    3  压栈(元素进栈)
    Status push(SqStack *S , ElemType  e)
       {  if  (S -> top-S -> bottom>=S -> stacksize-1) 
    {   S -> bottom=(ElemType *) realloc (S -> bottom, (STACKINCREMENT+STACK_SIZE) *sizeof(ElemType));  
     /*  栈满,追加存储空间  */
    if (! S -> bottom)  return  ERROR; 
    S -> top=S -> bottom+S -> stacksize ; //为什么?
    S -> stacksize+=STACKINCREMENT ;
    }  
    *S-> top=e;  
    S -> top++ ; /* 栈顶指针加1,e成为新的栈顶 */
    return OK;
    }
    
    4 弹栈(元素出栈)
    ElemType pop( SqStack   *S)      
    /*弹出栈顶元素*/
    {   if ( S->top== S-> bottom )  
    return ERROR ;       /*  栈空,返回失败标志  */
    S-> top-- ; 
    e=*S -> top ;  
    return  e ; 
    } 
    

    地址传递与值传递的区别

    ElemType pop( SqStack   *S)      /*弹出栈顶元素*/
    {   if ( S ->top== 0 )  
    return ERROR ;       /*  栈空,返回失败标志  */
    S -> top-- ; e =S-> bottom[S ->top];  
    return  e ; 
    } 
    ElemType Get_top( SqStack   *S)      /*弹出栈顶元素*/
    {   if ( S ->top== 0 )  
    return ERROR ;       /*  栈空,返回失败标志  */
    S -> top-- ; e =S-> bottom[S ->top];  
    return  e ; 
    } 
    展开全文
  • 动态分配和静态分配区别

    千次阅读 2012-10-08 22:42:19
    内存的静态分配和动态分配的区别主要是两个:  一是时间不同。静态分配发生在程序编译连接的时候。动态分配则发生在程序调入执行的时候。  二是空间不同。堆都是动态分配的,没有静态分配的堆。有2种...
  • 和栈的主要的区别由以下几点: 1、管理方式不同; 2、空间大小不同; 3、能否产生碎片不同; 4、生长方向不同; 5、分配方式不同; 6、分配效率不同; 管理方式:对于来讲,是由编译器自动管理,无需我们...
  • 内存的静态分配和动态分配的区别主要是两个: 一是时间不同。静态分配发生在程序编译连接的时候。动态分配则发生在程序调入执行的时候。 二是空间不同。堆都是动态分配的,没有静态分配的堆。有2种分配方式...
  • 堆、静态数据区详解

    千次阅读 2015-01-03 14:28:47
    在C++中,内存分成5个区,他们分别是堆、、自由存储区、全局/静态存储区常量存储区。 ,就是那些由编译器在需要的时候分配,在不需要的时候自动清除的变量的存储区。里面的变量通常是局部变量、函数参数等...
  • 和栈区别 一、预备知识—程序的内存分配 一个由c/C++编译的程序占用的内存分为以下几个部分 1、区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的...
  • (1) 从静态存储区域分配。内存在程序编译的时候就已经分配好,这块内存在程序的整个运行期间都存在。例如全局变量,static变量。 (2) 在上创建。在执行函数时,函数内局部变量的存储单元都可以在上创建,...
  • 静态存储区、堆和栈区别
  • 动态分配和静态分配

    2016-09-25 14:43:19
    内存分配方式主要分为两种:动态分配和静态分配。他们的区别主要是两个:1...动态数据区分为栈和堆,动态分配(释放由编译器执行)和静态分配(局部变量),堆只有动态分配(malloc等函数,程序员操作)。 静态
  • 主要是进栈退以及遍历的相关简单代码 代码实现如下 #include <stdio.h> #include <stdlib.h> #define MAXSIZE 10 typedef struct { int data[MAXSIZE]; int top;//栈顶指针 }Sqstack; void Init_...
  • 动态存储和静态存储区域区别

    千次阅读 多人点赞 2017-11-27 19:19:23
    动态存储方式 所谓动态存储方式是指在程序运行期间根据需要进行动态的分配存储空间的方式。动态存储变量是在程序执行过程中,使用它时才分配存储单元, 使用完毕立即释放。 典型的例子是函数的形式参数,在函数...
  • 静态存储区、区、堆区的区别

    万次阅读 多人点赞 2016-11-09 14:28:38
    内存分配有三种:静态存储区、堆区和栈区。他们的功能不同,对他们使用方式也就不同。 静态存储区:内存在程序编译的时候就已经分配好,这块内存在程序的整个运行期间都存在。它主要存放静态数据、全局数据...
  • 全局变量和静态全局变量都是静态存储的;在存储上无区别区别在于他们的作用域;全局变量的作用域是整个源程序,当源程序有多个源文件组成时,全局变量在各个源程序文件都是有效的;而静态全局变量怎被限制了作用域...
  • java中的堆,静态域,常量池

    千次阅读 2017-08-17 10:24:54
    :存放基本类型的数据对象的引用,但对象本身不存放在中,而是存放在堆中 堆:存放用new产生的数据 静态域:存放在对象中用static定义的静态成员 常量池:存放常量 非RAM(随机存取存储器)存储:硬盘等永久存储...
  • 动态的区域,就是堆和栈。这个应该称作 call stack,上面会存放函数的返回地址、参数局部变量。而堆放就是我们通过 new 算符 malloc 函数分配得到的空间,这些都是手动获得的空间,也需要手动的释放。 ht...
  • 和栈区别

    千次阅读 2014-04-27 12:01:05
    c++内存区分为5个部分:常量区;全局/静态区;自由存储区;;堆。 内存申请堆内存申请时,系统所做的工作的区别栈和堆的区别
  • 的顺序存储分为静态顺序存储和动态顺序存储,静态顺序存储的一次性分为配空间,但是不具备可扩重新,即在满后不能追加空间进行入栈操作。 一、程序代码如下: #include&amp;lt;stdio.h&amp;gt; #...
  • 堆与区别

    万次阅读 多人点赞 2018-06-29 15:24:05
    堆(Heap)与(Stack)是开发人员必须面对的两个概念,在理解这两个概念时,需要放到具体的场景下,因为不同场景下,堆与代表不同的含义。一般情况下,有两层含义: (1)程序内存布局场景下,堆与表示的是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 308,532
精华内容 123,412
关键字:

动态栈和静态栈的区别