数据结构-栈操作算法

#include <stdio.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW -2
#define OK 1
#define ERROR 0

typedef int SElemType;

//栈结构体
typedef struct {
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

int InitStack(SqStack *S);//初始化栈
int GetTop(SqStack *S,SElemType *e);//取得栈顶元素
int Push(SqStack *S,SElemType e);//入栈
int Pop(SqStack *S,SElemType *e);//删除栈中的元素
int DestoryStack(SqStack *S);//销毁栈
int StackEmpty(SqStack *S);//判断栈是否为空
int StackLength(SqStack *S);//取得栈的长度
int StackTraverse(SqStack *S);//自顶向下遍历栈

//初始化栈
int InitStack(SqStack *S) {
    S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if(!S->base) {
        exit(OVERFLOW);
    }
    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;

    return OK;
}

//取得栈顶元素
int GetTop(SqStack *S,SElemType *e) {
    if(S->top == S->base) {
        return ERROR;
    }
    *e = *(S->top-1);
    return OK;
}

//入栈
int Push(SqStack *S,SElemType e) {
    if((S->top-S->base)>=S->stacksize) {
        S->base = (SElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));
        if(!S->base) exit(OVERFLOW);
        S->top = S->base + S->stacksize;
        S->stacksize += STACKINCREMENT;
    }
    *S->top++ = e;
    return OK;
}

//删除栈中的元素
int Pop(SqStack *S,SElemType *e) {
    if(S->top  == S->base) return ERROR;
    *e = *--S->top;
    return OK;
}

//销毁栈
int DestoryStack(SqStack *S) {
    S->top = S->base;
    free(S->base);
    S->top = NULL;
    S->base = NULL;
    return OK;
}

//判断栈是否为空
int StackEmpty(SqStack *S) {
    if(S->top == S->base) {
        return OK;
    }
    return ERROR;
}

//取得栈的长度
int StackLength(SqStack *S) {
    return S->top-S->base;
    /*int i=0;
    if(!StackEmpty(S)) {
        while(S->top!=S->base) {
            i++;
            S->top--;
        }
    }
    return i;*/
}

//自顶向下遍历栈
int StackTraverse(SqStack *S) {
    SElemType *p;
    if(S->base!=S->top) {
        printf("栈中自顶向下的元素为：");
        p = S->top;
        while(p!=S->base) {
            p--;
            printf("%d ",*p);
        }
    } else {
        printf("栈为空！\n");
        return ERROR;
    }
    printf("\n");
    return OK;
}

int main()
{
    SqStack *sq;
    int f1,f2,e,f3,i,n,a,f4,f5,len,f6,f7;
    //初始化栈
    f1 = InitStack(sq);
    if(f1) printf("初始化栈成功！\n");
    else printf("初始化栈失败！\n");

    //入栈
    printf("请输入栈中元素的个数：");
    scanf("%d",&n);
    printf("请输入栈中元素：");
    for(i=0; i<n; i++) {
        scanf("%d",&a);
        Push(sq,a);
    }

    //取得栈顶元素
    f2 = GetTop(sq,&e);
    if(f2) printf("栈顶元素为：%d\n",e);
    else printf("栈为空！无栈顶元素！\n");

    //判断栈是否为空
    f5 = StackEmpty(sq);
    if(f5) printf("栈为空！\n");
    else printf("栈不为空！\n");

    //删除栈中的元素
    f6 = Pop(sq,&e);
    if(f6) {
        printf("删除的元素为：%d\n",e);
    }

    //取得栈的长度
    len = StackLength(sq);
    printf("栈的长度为：%d\n",len);

    //自顶向下遍历栈
    StackTraverse(sq);

    //销毁栈
    f4 = DestoryStack(sq);
    if(f4) printf("销毁栈成功！\n");
    else printf("销毁栈失败！\n");


    return 0;
}