/* 栈 */
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef int tElem;
typedef enum Status {
    ok = 1,Error = 0
} Status;
typedef struct Stack {
    tElem data[MAX_SIZE];
    int base;           // 栈尾
    int top;            // 栈头
    int length;         // 栈长
} Stack,*pStack;


/*
 * 初始化
 * 步骤：
 *  当栈为空时，为栈申请空间
 *  初始化栈头、栈尾、栈长
 *  返回栈指针
*/
pStack InitStack(pStack Sta)
{
    if(Sta == NULL)
    {
        Sta = (pStack) malloc(sizeof(Stack));
    }
    Sta->base = 0;
    Sta->top = 0;
    Sta->length = 0;
    return Sta;
}


/*
 * 获取元素在栈中的位置
 * 步骤：
 *  定义变量 i 初始值为 -1
 *  遍历栈，匹配元素 e 找到 e 后，把 e 的下标赋给 i
 *  返回位置 i（当 i = -1 时表示元素 e 不在栈中，若不等于 -1 则反之）
*/
int getPosition(pStack Sta,tElem e)
{
    int i = -1;
    int j = Sta->base;
    while (j < Sta->length)
    {
        if(Sta->data[j] == e) i = j;
        j++;
    }
    return i;
}


/*
 * 入栈
 * 步骤：
 *  若栈长大于最大长度时，表示空间不足，无法插入元素。否则反之
 *  将元素 e 存入原栈头的位置
 *  栈头 + 1，表示后移一位
 *  栈长 + 1
 *  返回栈指针
*/
pStack intoStack(pStack Sta,tElem e)
{
    if(Sta->length >= MAX_SIZE)
    {
        printf("空间不足！\n");
        return Sta;
    }

    Sta->data[Sta->top] = e;
    Sta->top++;
    Sta->length++;
    printf("元素 %d 入栈成功！\n",e);
    return Sta;
}


/*
 * 出栈
 * 步骤：
 *  调用 getPosition() 函数，找到元素 e 的位置，并将位置赋给变量 position。
 *  若 position = -1 表示元素 e 不在栈中。
 *  若 position + 1 不等于栈头，表示元素不是栈头元素，无法出栈，否则反之。
 *  令栈头向栈尾方向移动一位
 *  令栈长 - 1
 *  令移出去的元素位置存入 0
 *  返回栈指针
*/
pStack outStack(pStack Sta,tElem e)
{
    int position = getPosition(Sta,e);
    if(position == -1)
    {
        printf("元素 %d 不在栈中！\n",e);
    }
    else if(++position != Sta->top)
    {
        printf("元素 %d 不是最后一个入栈的元素，无法出栈！\n",e);
    }
    else
    {
        Sta->top--;
        Sta->length--;
        Sta->data[Sta->top] = 0;
        printf("元素 %d 出栈成功！\n",e);
    }
    return Sta;
}


/*
 * 打印栈元素
 * 步骤：
 *  若栈长等于 0 表示空栈。
 *  若非空栈，遍历栈，输出所有元素
*/
void printStack(pStack Sta)
{
    if(Sta->length == 0)
    {
        printf("空栈！\n");
    }
    else
    {
        int i = Sta->base;
        while (i < Sta->length)
        {
            printf("栈的第 %d 个元素是：%d\n",i,Sta->data[i]);
            i++;
        }
    }
}


/*
 * 清空所有元素
 * 步骤：
 *  遍历栈，令每个元素 = 0
 *  栈长和栈头都清零。
 *  返回栈指针
*/
pStack clearStack(pStack Sta)
{
    int i = Sta->base;
    while (i < Sta->top)
    {
        Sta->data[i] = 0;
        i++;
    }
    Sta->length = 0;
    Sta->top = 0;
    return Sta;
}


/*
 * 摧毁栈
 * 步骤：
 *  调用 clearStack() 函数，清空站内所有元素
 *  使用 free() 函数释放栈空间
*/
pStack destroyStack(pStack Sta)
{
    clearStack(Sta);
    printf("\n清空栈后，栈的长度为：%d\n",Sta->length);

    free(Sta);
    printf("\n摧毁成功！\n");
}

int main()
{
    pStack stack = NULL;
    stack = InitStack(stack);

    printf("\n-----开始入栈-----\n");
    stack = intoStack(stack,10);
    stack = intoStack(stack,20);
    stack = intoStack(stack,30);
    stack = intoStack(stack,40);
    stack = intoStack(stack,50);

    printf("\n-----入栈后-----\n");
    printStack(stack);

    printf("\n-----开始出栈-----\n");
    stack = outStack(stack,50);
    stack = outStack(stack,40);
    stack = outStack(stack,30);

    printf("\n-----出栈后-----\n");
    printStack(stack);

    destroyStack(stack);

    return 0;
}