数据结构与算法之栈的顺序存储表示(自动扩容)

//栈的顺序存储表示(自动扩容)
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

#define STACK_INIT_SIZE 10
#define STACK_INCREMENT 2

struct SqStack{

    int *base;
    int *top;
    int stacksize;

};

//构造一个空栈
void InitStack(struct SqStack *s){
    
    s->base = (int *)malloc(STACK_INIT_SIZE*sizeof(int));

    if(s->base==NULL)
    {
        printf("内存分配失败!\n");
        exit(1);
    }

    s->top = s->base;
    s->stacksize = STACK_INIT_SIZE;

}

//销毁栈
void DestoryStack(struct SqStack *s){

    free(s->base);//分配的内存是连续的

    s->stacksize = 0;
    s->base = NULL;
    s->top = NULL;
    
}

//清空栈
void ClearStack(struct SqStack *s){

    s->top = s->base;
    s->stacksize = 0;
}

//判断栈是否为空
bool EmptyStack(struct SqStack *s){
    
    if(s->base==s->top)
        return true;
    else
        return false;
}

//返回栈中的元素个数
int StackLength(struct SqStack s){
    
    if(s.base==s.top)
        return 0;
    else
        return s.top - s.base;
}

//获取栈顶元素
int GetTop(struct SqStack s){
    
    if(s.base==s.top)
        return -1;
    else
        return *--s.top;
}

//入栈
void Push(struct SqStack *s,int value){
    
    if(s->top-s->base>=s->stacksize){
        
        s->base = (int *)realloc(s->base,(STACK_INCREMENT+s->stacksize)*sizeof(int));
        if(s->base==NULL)
        {
            printf("内存分配失败!\n");
            exit(1);
        }
        else{
            
            s->top = s->base + s->stacksize;
            s->stacksize += STACK_INCREMENT;
            *(s->top) = value;
        }
    }

    *(s->top) = value;
    s->top++;
}

//出栈
bool Pop(struct SqStack *s,int *e){
    
    if(s->base==s->top)
    {
        return false;
    }

    (*e) = *(--s->top);
        return true;
}

//遍历栈
void StackTraverse(struct SqStack s){
    
    //从栈顶开始
    while(s.top>s.base){

        s.top--;
        printf("%d ",*(s.top));
    }

    //从栈底开始
    //while(s.base<s.top){
    //  printf("%d ",*s.base++);
    //}

    printf("\n");
}

int main()
{
    struct SqStack s;
    int i=1;
    int e;

    InitStack(&s);//构造一个空栈  

    for(i=1;i<=13;i++){
        Push(&s,i);//进行入栈
    }
    printf("遍历栈元素如下：\n");
    StackTraverse(s);//遍历栈(不要传递s的地址，否者会影响top指针)

    printf("出栈操作元素如下：\n");
    for(i=1;i<=13;i++){

        if(Pop(&s,&e))
        {
            printf("%d ",e);
        }else{
            printf("出栈失败\n");
        }
    }
    printf("\n");
    
    //再次进行入栈，不然会影响后续测试
    for(i=1;i<=13;i++){
        Push(&s,i);
    }

    //获取栈顶元素
    printf("栈顶元素：%d\n",GetTop(s));

    //获取栈含有元素个数
    printf("栈含有的元素个数为：%d\n",StackLength(s));

    return 0;
}