数据结构之栈（C语言）基础

墨蓝 2022-04-08 15:42 163阅读 0赞

栈，写的比较基础的函数，太复杂的没写，而且栈的应用（括号匹配啥的）也没写。。

栈：(Stack)  
后进先出的线性表（LIFO）  
把允许插入和删除的一段称为栈顶，另一端称为栈底  
/\*

小问题：  
最先进栈的元素是不是就是最后出栈的呢？  
答案是不一定

\*/

/*
        数据结构之栈
        实现基础函数：
        初始化，入栈，出栈，判断是否为空，
        获得栈顶元素，
    */
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #define MaxSize 100
    #define StackIncreate 10
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    typedef int ElemType;
    typedef int Status;
    typedef struct SNode{
        ElemType *base;
        ElemType *top;
        int stacksize;
    }Stack;
    
    Status InitStack(Stack &S){
        S.base = (ElemType *)malloc(sizeof(ElemType)*MaxSize);
        if(!S.base){
            exit(OVERFLOW);
        }
        S.top = S.base;
        S.stacksize = MaxSize;
        return OK;
    }
    
    Status Push(Stack &S,ElemType e){
        //如果栈满了的话
        if(S.top - S.base >= S.stacksize){
            S.base = (ElemType *)malloc(sizeof(ElemType)*(S.stacksize + StackIncreate));
            if(!S.base){
                exit(OVERFLOW);
            }
            S.top = S.base + S.stacksize;
            S.stacksize += StackIncreate;
        }
        *S.top++ = e;
        return OK;
    }
    Status Pop(Stack &S){
        if(S.base == S.top)
            return ERROR;
        S.top--;
        return OK;
    }
    Status GetTop(Stack &S){
        if(S.base == S.top)
            return ERROR;
        return *(S.top-1);
    }
    void isEmpty(Stack &S){
        if(S.base == S.top)
            printf("Stack is empty!\n");
        else
            printf("Stack is not empty!\n");
    }
    void StackPut(Stack &S){
        if(S.base == S.top)
            printf("Stack is empty!\n");
        else{
            ElemType *s = S.top-1;
            for(s;s >= S.base;s--){
                printf("%d ",*s);
            }
            printf("\n");
        }
    }
    int main(){
        Stack S;
        InitStack(S);
        int num;
        printf("请输入要插入的个数：\n");
        scanf("%d",&num);
        int i,tmp;
        for(i = 0; i < num; i++){
            scanf("%d",&tmp);
            Push(S,tmp);
        }
        //Pop(S);
        StackPut(S);
        return 0;
    }