#include <string.h>
#include <ctype.h>
// #include<malloc.h>      // malloc( )等
#include <limits.h> // INT_MAX等
#include <stdio.h>  // NULL等
#include <stdlib.h> // atoi( ), exit( )
// #include<io.h>          // eof( )
#include <math.h> // floor( ), ceil( ), abs( ), OVERFLOW宏定义，其值为3。

// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW 3

typedef int Status;
typedef int SElemType;

#define STACK_INIT_SIZE 5 // 存储空间初始分配量
#define STACKINCREMENT 2  // 存储空间分配增量
typedef struct
{
    SElemType *base; // 存储空间基址
    SElemType *top;  // 栈顶指针
    int stacksize;   // 当前已分配的存储空间，以元素为单位
} SqStack;

//构造空栈
void InitStack(SqStack &S)
{
    // 构造一个空栈S。
    S.base = (SElemType *)malloc(100 * sizeof(SElemType));
    if (!S.base)
        exit(OVERFLOW);
    S.top = S.base;
    S.stacksize = 0;
}

//销毁栈S
void DestroyStack(SqStack &S)
{ // 销毁栈S，S不再存在
    free(S.base);
    S.base = NULL;
    S.top = NULL;
    S.stacksize = 0;
}

//清空栈
void ClearStack(SqStack &S)
{   // 把S置为空栈
    S.top = S.base;
    S.stacksize = 0;
}

//判断栈是否为空
Status StackEmpty(SqStack S)
{   // 若栈S为空栈，则返回TRUE；否则返回FALSE
    return S.top == S.base ? TRUE : FALSE;
}

//计算栈元素的个数
int StackLength(SqStack S)
{   // 返回栈S的元素个数，即栈的长度
    return S.stacksize;
}

//获取栈顶元素
Status GetTop(SqStack S, SElemType &e) // 在教科书第47页
{                                      // 若栈S不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
                                
    if (S.top == S.base)
        return ERROR;
    e = *(S.top - 1);
    return OK;
}

//元素进栈
Status Push(SqStack &S, SElemType e)
{   // 插入元素e为栈S新的栈顶元素。
    if (S.stacksize >= 100)
        return ERROR;
    *(S.top++) = e;
    S.stacksize++;
    return OK;
}

//元素出栈
Status Pop(SqStack &S, SElemType &e)
{   // 若栈S不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
    if (S.top == S.base)
        return ERROR;
    e = *(--S.top);
    S.stacksize--;
    return OK;
}
//遍历栈
Status StackTraverse(SqStack S, void (*visit)(SElemType))
{ // 从栈底到栈顶依次对栈中每个元素调用函数visit()
    while (S.top > S.base)
        visit(*S.base++);
    printf("\n");
    return OK;
}