精华内容
下载资源
问答
  • 栈可以分为两种:静态栈和动态栈 两种栈的实现都可以复用单链表的代码,其中静态栈可以复用顺序表的代码;动态栈可以复用单链表的代码。其实可以从头到尾实现一个栈数据结构,但是那样做是没有意义的。代码复用的...

    栈的本质是线性表,可以说他是一种特殊的线性表,因为只能在线性表的一端进行操作(栈顶),不能操作的那一端交栈底。

    栈的性质:后进先出(LIFO)

    栈可以分为两种:静态栈和动态栈

    两种栈的实现都可以复用单链表的代码,其中静态栈可以复用顺序表的代码;动态栈可以复用单链表的代码。其实可以从头到尾实现一个栈数据结构,但是那样做是没有意义的。代码复用的思想是工程中常见的,而且基于已经测试过的代码就减少了中间会遇到的其它问题。

    而且由于栈的操作仅仅能在线性表的一端进行,所以无论是入栈还是出栈的操作,时间复杂度都是O(1)

    首先是静态栈的实现,项目中需要添加之前实现的顺序表代码。需要注意的是栈顶的选择可以有两种方式,在顺序表的头部或者尾部,这里选择线性表的尾部作为栈顶,也就是说只能允许在这一端进行操作;相应的在进行出栈操作时也是从线性表的尾部开始。

    SeqStack* SeqStack_Greate(int capacity)
    {
    	return SeqList_Create(capacity);
    }
    
    void SeqStack_Destroy(SeqStack* stack)
    {
    	SeqList_Destroy(stack); 
    }
    
    void SeqStack_Clear(SeqStack* stack)
    {
    	SeqList_Clear(stack);
    }
    
    int SeqStack_Push(SeqStack* stack, void* item)
    {
    	return SeqList_Insert(stack, item, SeqList_Length(stack));	// 选择线性表的尾部作为栈顶,在这一端操作栈
    }
    
    void* SeqStack_Pop(SeqStack* stack)
    {
    	return SeqList_Delete(stack, SeqList_Length(stack) - 1); 
    }
    
    // 返回栈顶元素
    void* SeqStack_Top(SeqStack* stack)
    {
    	return SeqList_Get(stack, SeqList_Length(stack) - 1);
    }
    
    int SeqStack_Size(SeqStack* stack)
    {
    	return SeqList_Length(stack);
    }
    
    int SeqStack_Capacity(SeqStack* stack)
    {
    	return SeqList_Capacity(stack);
    }

    动态栈的实现比顺序栈要复杂,首先需要定义结点的结构体,用来表示每次进栈或者出栈的元素,然后进栈和出栈的操作也要malloc和free相应的内存空间。

    // 定义栈的每一个结构体组成
    typedef struct _tag_LinkStackNode
    {
        LinkListNode header;
        void* item;		// 保存地址
    } TLinkStackNode;
    
    // 创建一个只含头结点的栈
    LinkStack* LinkStack_Create()
    {
        return LinkList_Create();
    }
    
    void LinkStack_Destroy(LinkStack* stack)
    {
        LinkStack_Clear(stack);
    
        LinkList_Destroy(stack);
    }
    
    // 链表中的每一个元素都是malloc出来的,单纯clear会产生内存泄漏
    void LinkStack_Clear(LinkStack* stack)
    {
        while( LinkStack_Size(stack) > 0 )
        {
            LinkStack_Pop(stack);
        }
    }
    
    int LinkStack_Push(LinkStack* stack, void* item)
    {
        TLinkStackNode* node = (TLinkStackNode*)malloc(sizeof(TLinkStackNode));
        int ret = (node != NULL) && (item != NULL);
        
        if( ret )
        {
            node->item = item;	// 保存传进来的参数地址
            
            ret  = LinkList_Insert(stack, (LinkListNode*)node, 0); // 使用队头作为栈顶
        }
        
        if(!ret)
        {
            free(node);
        }
        
        return ret;
    }
    
    void* LinkStack_Pop(LinkStack* stack)
    {
        TLinkStackNode* node = (TLinkStackNode*)LinkList_Delete(stack, 0);	// 首元素为栈顶
        void* ret = NULL;
        
        if( node != NULL )
        {
            ret = node->item;	// 返回删除的元素
            
            free(node);		// 释放掉结点空间 
        }
        
        return ret;
    }
    
    void* LinkStack_Top(LinkStack* stack)
    {
        TLinkStackNode* node = (TLinkStackNode*)LinkList_Get(stack, 0);
        void* ret = NULL;
        
        if( node != NULL )
        {
            ret = node->item;	// 返回栈顶元素结点
        }
        
        return ret;
    }
    
    int LinkStack_Size(LinkStack* stack)
    {
        return LinkList_Length(stack);
    }

     

    展开全文
  • C语言-数据结构-栈(静态栈动态栈)

    千次阅读 2019-09-08 23:39:55
    一.简介 在哔哩哔哩看视频学的,赫斌老师数据结构入门的内容-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.迷宫

    展开全文
  • 静态实现

    2016-04-12 10:57:04
    静态实现代码
  • 主要介绍了JAVA中堆、静态方法静态方法的速度问题,堆和栈得速度性能分析多角度给大家分析,非常不错,具有一定的参考借鉴价值,需要的朋友可以参考下
  • 主要介绍了C/C++ 中堆和栈静态数据区详解的相关资料,需要的朋友可以参考下
  • 动态变量和静态变量的区别: 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-04-25 17:02:58
    #pragma once #include<stdio.h> #include<stdlib.h> typedef int DataType; #define MAX_SIZE 100 ...//的元素最大个数 int _top;//栈顶 int _bottom;//低 i...
    #pragma once
    #include<stdio.h>
    #include<stdlib.h>
    typedef int DataType;
    #define MAX_SIZE 100
    
    typedef struct Stack
    {
    	DataType _arr[MAX_SIZE];//栈的元素最大个数
    	int _top;//栈顶
    	int _bottom;//栈低
    	int len;//栈大小
    }Stack,*Pstack;
    
    // 栈的初始化 
    void StackInit(Stack* s); 
    
    // 入栈 
    void StackPush(Stack* s, DataType data); 
    
    // 出栈 
    void StackPop(Stack* s); 
    
    // 获取栈顶元素 
    DataType StackTop(Stack* s); 
    
    // 获取栈中元素个数 
    int StackSize(Stack* s); 
    
    // 检测栈是否为空 
    int StackEmpty(Stack* s);

     test

    #include"Stack.h"
    void StackInit(Stack* S)
    {
    	S->_bottom = S->_top = 0;
    	S->len = 0;
    }
    
    void StackPush(Stack* S, DataType data)
    {
    	if(S->len == MAX_SIZE)
    	{
    	printf("栈满溢出,添加失败!\n");
    	return;
    	}
    	S->_top++;
    	S->_arr[S->_top] = data;
    	S->len++;
    	printf(" %d 入栈成功!\n",data);
    }
    
    void StackPop(Stack* S)
    {
    	if(S->len == 0)
    	{
    	printf("栈为空!\n");
    	return;
    	}
    	printf(" %d 出栈\n",S->_arr[S->_top]);
    	S->_top--;
    	S->len--;
    	printf("此时栈顶元素为:%d\n",S->_arr[S->_top]);
    }
    
    DataType StackTop(Stack* S)
    {
       if(S->len == 0)
    	{
    	printf("栈为空!\n");
    	return;
    	}
        printf("此时栈顶为: %d \n",S->_arr[S->_top]);
    }
    
    int StackSize(Stack* S)
    {
    	int ret = 0;
    	ret = printf("栈中元素个数为:%d\n",S->len);
    	return ret;
    }
    
    int StackEmpty(Stack* S)
    {
       if(S->len == 0 )
    	{
    	printf("栈为空!\n");
    	return 1;
    	}
       else
       {
       printf("栈不为空!\n");
       return 0;
       }
    }
    
    main

    #include"Stack.h"
    test()
    {
      Stack S;
      StackInit(&S);
      StackPush(&S, 1);
      StackPush(&S, 2);
      StackPush(&S, 3);
      StackPush(&S, 4);
      StackPush(&S, 5);
      StackSize(&S);
      StackTop(&S);
      StackPop(&S);
      StackPop(&S);
      StackEmpty(&S);
    
    
    
    }
    int main()
    {
    	test();
    	system("pause");
    }

    动态栈

    Stack.c

    #include "stack.h"  
    #include "Maze.h"  
      
    void StackInit(Stack *S,int capacity)//栈初始化  
    {  
        S->arr = (DataType*)malloc(capacity*sizeof(DataType));  
        if(NULL == S->arr)  
        {  
           printf("申请空间失败!\n");  
           return;  
        }  
        S->capacity = capacity;  
        S->size = 0;  
    }  
      
      
    void AddCapacity(Stack *S)//扩容  
    {  
       if(NULL == S->arr)  
        {  
           printf("扩容失败\n");  
           return;  
        }  
       S->capacity = (DataType*)realloc(S->arr,sizeof(DataType)*(S->capacity)*2);//扩容为原来的二倍  
       if (NULL == S->arr)  
        {  
            printf("空间扩增失败!!!\n");  
            return;  
        }  
       S->capacity =2 * (S->capacity);  
    }  
      
    void PrintfStack(Stack *S)//打印栈  
    {  
       int i = 0;  
       if(NULL == S->arr)  
        {  
           printf("打印失败\n");  
           return;  
        }  
       for(;i<S->size;i++)  
       {  
           printf("%d\n",S->arr[i]);  
       }  
       printf("\n");  
    }  
      
    void StackPush(Stack *S,DataType data)//入栈  
    {  
        if(NULL == S->arr)  
        {  
           printf("入栈失败\n");  
           return;  
        }  
        if(S->capacity == S->size)//空间已满  
        {  
           AddCapacity(S);  
        }  
        S->arr[S->size] = data;  
        S->size++;  
    }  
      
    void StackPop(Stack *S)//出栈  
    {  
       if(NULL == S->arr)  
        {  
           printf("出栈失败\n");  
           return;  
        }  
       S->size--;  
    }  
      
    DataType StackTop(PStack P)//获取栈顶元素  
    {  
        return P->arr[P->size - 1];  
      /* int ret = 0; 
       if(NULL == S->arr) 
        { 
           printf("获取栈失败\n"); 
           return; 
        } 
       if(0 == S->size) 
       { 
       printf("栈为空!\n"); 
       return; 
       } 
       
       printf("栈顶元素为:%d \n", S->arr[S->size - 1]);*/  
    }  
      
    void StackSize(Stack *S)//获取元素个数  
    {  
       if(NULL == S->arr)  
        {  
           printf("获取栈失败\n");  
           return;  
        }  
       printf("元素个数为:%d\n",S->size);  
    }  
      
    int StackEmpty(Stack *S)//检测栈是否为空  
    {  
        if(NULL == S->arr)  
        {  
           printf("获取栈失败\n");  
           return 0;  
        }  
        if(S->size == 0)  
        {  
        printf("栈为空\n");  
        return 1;  
        }  
        return 0;  
    }  

    Stack.h

    #pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    typedef struct int DataType
    typedef struct Stack
    {
       DataType *_arr;
       int  capacity;
       int  size;
    }Stack;
    // 栈的初始化   
    void StackInit(Stack *S, int capacity);  
      
    // 入栈   
    void StackPush(Stack *S, DataType data);  
      
    // 出栈   
    void StackPop(Stack *S);  
      
    // 获取栈顶元素   
    DataType StackTop(Stack *S);  
      
    // 获取栈中元素个数   
    void StackSize(Stack *S);  
      
    // 检测栈是否为空   
    int StackEmpty(Stack *S);  
    



    展开全文
  • cpp代码-静态实现

    2021-07-16 15:35:08
    cpp代码-静态实现
  • 数据结构 - 静态顺序存储

    千次阅读 2015-04-29 09:04:23
    (Stack):是限制在表的一端进行插入删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。 栈顶(Top):允许进行插入、删除操作的一端,又称为表尾。用栈顶...
  • 采用静态一维数组来存储底固定不变的,而栈顶则随着进栈退操作变化的, ◆ 底固定不变的;栈顶则随着进栈退操作而变化,用一个整型变量top(称为栈顶指针)来指示当前栈顶位置。 ◆ 用top=0表示...
  • 堆、静态数据区详解

    千次阅读 2015-01-03 14:28:47
    在C++中,内存分成5个区,他们分别是堆、、自由存储区、全局/静态存储区常量存储区。 ,就是那些由编译器在需要的时候分配,在不需要的时候自动清除的变量的存储区。里面的变量通常是局部变量、函数参数等...
  • 有2种分配方式:静态分配和动态分配。静态分配是编译器完成的,比如局部变量的分配。动态分配由函数malloc进行分配。不过动态分配堆不同,他的动态分配是由编译器进行释放,无需我们手工实现。 ...
  • CC++堆、静态数据区详解,详细解释CC++里的堆、静态数据区
  • 动态分配和静态分配

    2016-09-25 14:43:19
    内存分配方式主要分为两种:动态分配和静态分配。他们的区别主要是两个:1...动态数据区分为栈和堆,动态分配(释放由编译器执行)和静态分配(局部变量),堆只有动态分配(malloc等函数,程序员操作)。 静态
  • 保存对象:保存函数调用相关信息(局部非静态对象、函数参数、、、)。 生存期:调用函数开始时在区分配内存,函数结束时释放内存。 2、动态内存 保存动态对象:通过new在内存池中申请的,没有足够空间会...
  • 主要是进栈退以及遍历的相关简单代码 代码实现如下 #include <stdio.h> #include <stdlib.h> #define MAXSIZE 10 typedef struct { int data[MAXSIZE]; int top;//栈顶指针 }Sqstack; void Init_...
  • 数据结构 C++ 程序加详细注释 静态全局变量 静态数据成员 静态顺序静态有关.rar
  • 和栈静态数据区

    2005-07-07 20:30:00
    在C++中,内存分成5个区,他们分别是堆、、自由存储区、全局/静态存储区常量存储区,下面我们就真对这五个存储区分别进行简单介绍。 五大内存分区------------------------ 在C++中,内存分成5个区,他们分别是...
  • 动态存储区、静态存储区、堆和栈的区别

    千次阅读 多人点赞 2018-09-11 12:43:46
    动态存储区、静态存储区、堆和栈的区别 内存中用户存储空间的分配情况(三种) 程序区:存放程序语句 静态存储区 动态存储区  ...
  • 全局变量和静态全局变量都是静态存储的;在存储上无区别。区别在于他们的作用域;全局变量的作用域是整个源程序,当源程序有多个源文件组成时,全局变量在各个源程序文件都是有效的;而静态全局变量怎被限制了作用域...
  • java中的堆,静态域,常量池

    千次阅读 2017-08-17 10:24:54
    :存放基本类型的数据对象的引用,但对象本身不存放在中,而是存放在堆中 堆:存放用new产生的数据 静态域:存放在对象中用static定义的静态成员 常量池:存放常量 非RAM(随机存取存储器)存储:硬盘等永久存储...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 318,331
精华内容 127,332
关键字:

动态栈和静态栈