/* run this program using the console pauser or add your own getch, system("pause") or input loop */
// 用到的库文件
#include <stdio.h> // printf();scanf()
#include <stdlib.h> // exit()
#include <malloc.h> // malloc()
#include <time.h> // srand((unsigned)time(NULL));
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
// Status是函数的类型，其值是函数结果状态代码
typedef int Status;
// #define ElemType int // 也可以用宏定义确定ElemType类型
typedef char SElemType;
// -----栈的顺序存储表示-----
#define STACK_INIT_SIZE 100 // 存储空间初始分配量
#define STACKINCREMENT 10 // 存储空间分配增量
typedef struct {
SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
} SqStack;
// 操作结果：构造一个空栈S。
Status InitStack(SqStack &S) {
S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S.base) // 存储分配失败
exit(OVERFLOW); // exit(-2)程序异常退出
S.top = S.base; // 栈顶、栈底指针均指向栈底
S.stacksize = STACK_INIT_SIZE;
return OK;
}// InitStack
// 操作结果：销毁栈S，S不再存在。
Status DestroyStack(SqStack &S) {
free(S.base);
S.base = NULL;
S.top = NULL;
S.stacksize = 0;
return OK;
}// DestroyStack
// 操作结果：把S置为空栈。
Status ClearStack(SqStack &S) {
S.top = S.base;
return OK;
}// ClearStack
// 操作结果：若S为空栈，返回TRUE，否则返回FALSE
Status StackEmpty(SqStack S) {
if(S.top == S.base)
return TRUE; // 返回1
else
return FALSE; // 返回0
}// StackEmpty
// 操作结果：返回S的元素个数，即栈的长度。
int StackLength(SqStack S) {
return S.top-S.base;
}// StackLengthS.top
// 操作结果：若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR。
Status GetTop(SqStack S, SElemType &e) {
if(S.top == S.base)
return ERROR;
e = *(S.top - 1);
return OK;
}// GetTop
// 操作结果：插入元素e为新的栈顶元素。
Status 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;
}// Push
// 操作结果：若栈不空，则删除S的栈顶元素，并用e返回其值；否则返回ERROR。
Status Pop(SqStack &S, SElemType &e) {
if(S.top == S.base)
return ERROR;
e = *--S.top;
return OK;
}// Pop
// 操作结果：从栈底到栈顶依次对栈中每个数据元素调用函数visit()。一旦vistit()失败，刚操作失败。
Status visit(SElemType e) {
printf("%c - ", e);
return OK;
}
Status StackTraverse(SqStack S, Status (*pfn_visit)(SElemType)) {
while(S.top > S.base)
visit(*S.base++);
printf("\n");
return OK;
}// StackTraverse
int main() {
SqStack S;
// 构造空栈
if(InitStack(S)) {
// 插入元素
Push(S, 'A');
Push(S, 'B');
Push(S, 'C');
Push(S, 'D');
Push(S, 'E');
}
// 求栈长
printf("%d\n", StackLength(S));
// 返回S的栈顶元素
SElemType e;
if(GetTop(S, e))
printf("%c\n", e);
StackTraverse(S, visit);
// 删除S的栈顶元素
if(Pop(S, e))
printf("%c\n", e);
StackTraverse(S, visit);
// 判空
if(StackEmpty(S))
printf("栈空\n");
else
printf("栈非空\n");
// 置空
ClearStack(S);
StackTraverse(S, visit);
// 判空
if(StackEmpty(S))
printf("栈空\n");
else
printf("栈非空\n");
// 销毁
DestroyStack(S);
return 0;
}
