栈---->动态实现

曾经终败给现在 2022-06-05 23:25 258阅读 0赞

#### 动态栈 ####

*  栈可以使用静态数组来模拟实现，但是使用静态数组时，栈的大小就必须是固定的，为了弥补这种局限性，栈可以使用动态存储空间，因为在使用过程中可移动台的调整大小；

typedef struct{
        int key; //栈所存储的数据类型
    }element;　//进行类型重命名为element；
    element* stack;
    MALLOC(stack,sizeof(stack));//使用malloc来申请堆上面的空间；

*  动态存储空间的扩容问题，一般来说当栈满之后，直接执行的是加倍策略；

void stackfull(){
        RELLOC(stack,2*capacity*sizeof(*stack));　//当申请的堆空间满时，重新申请空间；
        capacity*=2;　//采用２倍加倍策略进行空间申请；
    }

*  模拟实现动态栈的代码:

#include<stdio.h>
    #include<stdlib.h>
    #define MAX_SIZE 100
    
    typedef struct
    {
        int key;
    } elements;
    elements Stack[MAX_SIZE];
    
    int top=-1;
    
    int Isempty(elements *Stack)
    {
        return (top < 0 ? 0 : 1);　//判断堆是否为空；
    }
    
    int Isfull(elements *Stack)
    {
        return (top == MAX_SIZE ? 0 : 1);　//判断栈是否满；
    }
    
    void Push(elements *Stack, int data)
    {
        if (!Isfull(Stack))　//判断汗是否为满
        {
            fprintf(stderr, "Stack Isfull\n");
            exit(EXIT_FAILURE);
        }
        else
        {
            top++;
            Stack[top].key = data;　//添加元素
        }
    
    }
    
    elements Pop(elements *Stack)
    {
        if (!Isempty(Stack))
        {
            fprintf(stderr, "The Stack is empty\n");
            exit(EXIT_FAILURE);
        }
        else
            return Stack[top--];//弹出元素；
    
    }
    void Destory_stack(){
        free(Stack);
    }
    
    
    int main()
    {   
    
        Push(Stack,10);
        Push(Stack,9);
        Push(Stack,8);
        Push(Stack,7);
        Push(Stack,6);
        Push(Stack,5);
        Push(Stack,4);
        Push(Stack,3);
        Push(Stack,2);
        Push(Stack,1);
        Pop(Stack);
        Pop(Stack);
    
        printf("myStack contains:\n");
    
        int i=0;
        for(i=top;i>=0;i--){
       //用于打印栈里面包含的元素；
            printf("[ %d ]\n",Stack[i].key);
        }
        Destory_stack();
        return 0;
    }