数据结构与算法--链式堆栈

迷南。 2022-08-31 00:50 180阅读 0赞

## 前言 ##

在计算机领域，堆栈是一个不容忽视的概念，堆栈是一种数据结构。堆栈都是一种数据项按序排列的数据结构，只能在一端(称为栈顶(top))对数据项进行插入和删除。在单片机应用中，堆栈是个特殊的存储区，主要功能是暂时存放数据和地址，通常用来保护断点和现场。

堆栈（stack）的显著特点是后进先出（Last-In First-Out, LIFO），其实现的方法有三种可选方案：**静态数组**、**动态分配的数组**、**动态分配的链式结构**。

链式结构的优点：是动态存储，无长度上限，需要的时候再申请分配内存空间，可最大程度上实现灵活性。  
缺点：链式结构的链接字段需要消耗一定的内存，在链式结构中访问一个特定元素的效率不如数组。

## C程序内存布局 ##

![在这里插入图片描述][1a79fef32cd96e3b62c39c9f3bbb85df.png]  
一个由C/C++编译的程序占用的内存分为以下几个部分  
1、栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。  
2、堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表，呵呵。  
3、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放  
4、文字常量区—常量字符串就是放在这里的。 程序结束后由系统释放  
5、程序代码区—存放函数体的二进制代码。

## 压栈 ##

定义好结构体后，先创建一个未定义的结构体指针，这时head指向为空（NULL），存储在.bss段。

而对于内存空间释放问题：  
创建的new\_node指针是局部变量，存放于栈区，函数调用完后会自动消亡，无需担心该指针会变成野指针，所以在使用完new\_node指针后无需将其指向NULL  
malloc分配的结构体地址空间，存在于堆区的，需要使用free()函数将其释放。

/* * 1.首先创建一个new_node指针 * 2.使用(StackNode *)malloc(sizeof(StackNode))动态分配地址，然后将new_node指针指向它 * 3.判断是否为空 * 4.赋值给new_node的data域 * 5.new_node指针指向head指向的地址，初始值为NULL * 6.head指向new_node指针新节点的首地址 */
    void push(STACK_TYPE value) { 
      StackNode *new_node;
      new_node = (StackNode *)malloc(sizeof(StackNode));
      if (new_node == NULL)
        perror("malloc fail");
      new_node->data = value;
      new_node->next = head;
      head = new_node;
    }

## 出栈 ##

/* * 1.判断该栈是否为空 * 2.创建一个结构体指针top_node * 3.top_node指向head指向的栈顶的首地址，指向栈顶 * 4.head指向next域下一节点 * 5.释放掉top_node指向的地址空间” */ 
    void pop(void) { 
      assert(!is_empty());
      StackNode *top_node;
      top_node = head;
      head = top_node->next;
      free(top_node);
    }

## 静态数组 ##

#include <stdio.h>
    #include <assert.h>
    #include <malloc.h>
    
    
    #define stack_size 50
    
    /******定义一个stack的数组，未初始化，在.bss段********/
    static int stack[stack_size];
    
    /******定义一个top_num来作为数组下标，在.data段********/
    static int top_num = -1;
    
    /******定义一个判断栈为空的函数，在文本段********/
    int empty()
    { 
     return top_num == -1;//如果top_num为-1，其就是(数组/栈)里面没有任何元素
    }
    
    /*******定义一个判断栈为满的函数，在文本段********/
    int full()
    { 
     return top_num == stack_size-1;//如果top_num为stack_size-1，其就是(数组/栈)里面已经装满元素
    }
    
    /********定义一个入栈函数，在文本段******************/
    void push(int value)
    { 
     assert(!full());              //先判断栈是否为满，如果未满就允许程序继续执行，如果已满，则停止执行下一步程序
     top_num+=1;                   //top_num+1,将入栈一个元素
     stack[top_num] = value;       //stack[top_num]数组会将value（用户所定的值）一个一个存入数组里面，即入栈。
    }
    
    /********定义一个出栈函数，在文本段*******************/
    void pop()
    { 
     assert(!empty());              //先判断栈是否为满，如果不为空就允许程序继续执行，如果未空，则停止执行下一步程序
     top_num-=1;                    //top_num减1，这个时候stack_print(打印函数)在打印的时候，将不会再打印这个tom_num已经减一的下标数组
    }
    
    /********定义一个打印函数，在文本段*******************/
    void stack_print()
    { 
     int num;                           //定义一个num，局部变量，在栈区
     num = top_num;                     //top_num是一个全局变量，每入栈一个元素或者出栈一个元素，top_num都会发生变化
     printf("打印静态数组里面的值：");   
     if(num == -1)                      //num为-1，即top_num为-1，这个时候栈为空
     { 
      printf("栈为空");
     }
     while(num!=-1)                     //num不等于-1，说明有元素入栈，push入栈，等全部入栈后，再通过num--，从数组的下标大到小进行打印 
     { 
     printf("%d\n",stack[num--]);              
     }
     printf("\n");
    }
    
    /********定义一个main函数，作为其他函数的一个入口，其位置在文本段*******************/
    int main()
    { 
     stack_print();
     push(5);
     push(4);
     push(3);
     push(2);
     push(1);
     printf("入栈后的数据为：");
     stack_print();
     printf("\n");
     pop();
     pop();
     printf("出栈后的数据为：");
     stack_print();
     printf("\n");
     return 1;
    
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAyMDc4OA_size_16_color_FFFFFF_t_70]

## 动态数组 ##

#include <stdio.h>
    #include <assert.h>
    #include <malloc.h>
    
    /******定义一个strack指针，在.bss段*********/
    static int *stack;
    
    /******定义栈的栈的长度，在.bss段*********/
    static int stack_size;
    
    /******定义top_，在.data段*********/
    static int top_num = -1;
    
    /******定义一个创建栈的函数，在文本段********/
    void create_stack(size_t size)
    { 
      assert(stack_size == 0);                           //如果栈长度为0，则运行下一步程序
      stack_size = size;                                 //将自定义的size长度作为栈的总长度
      
      /* 指针变量stack为int *，所以malloc需要加上(int *)进行强制转换，(stack_size * sizeof(int))意思是 栈长度（元素个数，类型为int）与 int的长度进行相乘得到总长度，并且用malloc进行内存分配，最后将stack 将指向其首地址 */
      stack = (int *)malloc(stack_size * sizeof(int));   
      if (stack == NULL)
      { 
        printf("malloc分配失败");
      }
    }
    
    /******定义一个销毁栈的函数，在文本段********/
    void destroy_stack(void)
    { 
      assert(stack_size  > 0);//如果栈长度不为0，则运行下一步程序
      free(stack);            //释放stack指针变量里面的值（malloc已经分配好给stack_size的首地址），但其实这个时候stack还是指向stack_size的首地址
      stack_size = 0;         //释放后，人工操作将栈长度赋值为0
      stack = NULL;           //指针变量stack变为空指针
    }
    
    /*******定义一个判断栈为满的函数，在文本段********/
    int full()
    { 
      assert(stack_size > 0);//如果栈长度不为0，则运行下一步程序，这步其实有没有对程度运行没太大影响，只是为了方便用户调试
      return top_num == stack_size - 1;//如果top_num为stack_size-1，其是指针指向的stack_size这段存储空间装满了元素，也可以理解为(数组/栈)里面已经装满元素
    }
    
    /******定义一个判断栈为空的函数，在文本段********/
    int empty()
    { 
      assert(stack_size > 0);//如果栈长度不为0，则运行下一步程序，这步其实有没有对程度运行没太大影响，只是为了方便用户调试
      return top_num == -1;  //如果top_num为-1，其是指针指向的stack_size这段存储空间，没有元素，也可以理解为(数组/栈)里面没有元素
    }
    
    /********定义一个入栈函数，在文本段******************/
    void push(int num)
    { 
      assert(!full());     //先判断栈是否为满，如果未满就允许程序继续执行，如果已满，则停止执行下一步程序
      top_num += 1;        //top_num+1,将入栈一个元素
      stack[top_num] = num;//stack[top_num]数组会将num（用户所定的值）一个一个存入指针所指向的内存空间（数组）里面，即入栈
    }
    
    /********定义一个出栈函数，在文本段*******************/
    void pop()
    { 
      assert(!empty());    //先判断栈是否为满，如果不为空就允许程序继续执行，如果未空，则停止执行下一步程序
      top_num -= 1;        //top_num减1，这个时候stack_print(打印函数)在打印的时候，将不会再打印这个tom_num已经减一的（指针所指向的内存空间）或者理解为下标数组
    }
    
    /********定义一个打印函数，在文本段*******************/
    void stack_print()
    { 
      int num;                        //定义一个num，局部变量，在栈区
      num = top_num;                  //top_num是一个全局变量，每入栈一个元素或者出栈一个元素，top_num都会发生变化
      printf("打印动态数组里面的值");
      if (num == -1)                  //num为-1，即top_num为-1，这个时候栈为空
      { 
        printf("这是个空堆栈");
      }
      while (num != -1)               //num不等于-1，说明有元素入栈，push入栈，等全部入栈后，再通过num--，从指针指向的内存空间（数组的下标）大到小进行打印
      { 
        printf("%d\n", stack[num--]);
      }
      printf("\n");
    }
    
    
    /********定义一个main函数，作为其他函数的一个入口，其位置在文本段*******************/
    int main()
    { 
      create_stack(50);
      stack_print();
      push(7);
      push(6);
      push(5);
      push(4);
      push(3);
      push(2);
      push(1);
      printf("入栈后的数值：");
      stack_print();
      printf("\n");
      pop();
      pop();
      pop();
      printf("出栈后的数值：");
      stack_print();
      printf("\n");
      destroy_stack();
      return 1;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAyMDc4OA_size_16_color_FFFFFF_t_70 1]

## 链式结构 ##

#include <stdio.h>
    #include <malloc.h>
    #include <assert.h>
    
    typedef struct STACK_VAR
    { 
      int var;                  //定义一个变量var，在栈区
      struct STACK_VAR *next;   //定义一个结构体指针next（即尾端），在栈区
    }stackvar;
    
    static stackvar *stack;     //定义一个结构体指针stack，用来充当桥梁，在栈区
    
    
    int empty()                 
    { 
      return stack == NULL; 
    }
    
    
    void push(int var)
    { 
      stackvar *new_var;                                
      new_var = (stackvar*)malloc(sizeof(stackvar));    
      if(new_var == NULL)                               
     { 
      printf("malloc分配失败！");
     }
     new_var->var=var;
     new_var->next=stack;                               
     stack=new_var;
    }
    
    
    void pop()
    { 
     stackvar *first_var;               //创建一个新的节点first_var（结构体指针）
     assert(!empty());                  //先判断栈是否为空，如果不为空就允许程序继续执行，如果为空，则停止执行下一步程序
     first_var=stack;                   
     stack=first_var->next;
    }
    
    void stack_all_clear()
    { 
     while(!empty()) //先判断栈是否为空
       pop();
     { 
     }
    }
    
    void stack_print()
    { 
     stackvar *p_var;            //定义一个结构体指针变量，局部变量，在栈区
     p_var = stack;              //指针变量stack是一个全局变量，每入栈一个元素或者出栈一个元素，stack都会发生变化
     printf("打印链表里面的值\n");  
     if(p_var == NULL)       
     { 
      printf("栈为空");
     }
     while(p_var != NULL )
     { 
      printf("%d\n",p_var->var);
      p_var = p_var->next;      
       }
     printf("\n");
    }
    
    
    int main()
    { 
     stack_print();
     push(10);push(9);push(8);push(7);push(6);
     push(5);push(4);push(3);push(2);push(1);
     stack_print();printf("\n");
     pop();pop();
     printf("出栈以后的值\n");
     stack_print();printf("\n");
     stack_all_clear();
     printf("全部清除后");
     stack_print();
     printf("\n");
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAyMDc4OA_size_16_color_FFFFFF_t_70 2]

[1a79fef32cd96e3b62c39c9f3bbb85df.png]: /images/20220829/bffb763d3762471bab555a0dfe8f80c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAyMDc4OA_size_16_color_FFFFFF_t_70]: /images/20220829/02d3d7459a5044668c19c51641c87dd3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAyMDc4OA_size_16_color_FFFFFF_t_70 1]: /images/20220829/843c8f617f304412bcbdbe11bda141b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjAyMDc4OA_size_16_color_FFFFFF_t_70 2]: /images/20220829/aeb4ba889a394c91b7d56003f1f74442.png