栈的基本结构和操作(C语言实现)

include EOF Z 或 F6 NULL include atoi include include malloc 等 include eof include exit 函数结果状态代码 define TRUE 1 define FALSE 0 define OK 1 define ERROR 0 define INFEASIBLE 1 define OVERFLOW 2 typedef int Status Status 是函数的类型 其值是函数结果状态代码 如 OK 等 typedef int Boolean Boolean 是布尔类型 其值是 TRUE 或 FALSE typedef int SElemType 定义栈元素类型 栈的顺序存储表示 define STACK INIT SIZE 12 存储空间初始分配量 define STACKINCREMENT 2 存储空间分配增量 typedef struct SElemType base 栈底指针 在构造之前和销毁之后 base 为 NULL SElemType top 栈顶指针 int stacksize 当前已分配的栈空间 以元素为单位 SqStack 栈的基本操作 Status InitStack SqStack S 构造一个新的栈 Status DestoryStack SqStack S 销毁栈 S Status ClearStack SqStack S 把栈 S 置为空 Status StackEmpty SqStack S 判断 S 是否为空 若为空 返回 TRUE 否则返回 FALSE int StackLength SqStack S 返回 S 的元素个数 及栈的长度 Status GetTop SqStack S SElemType e 若栈不为空 用 e 返回 S 的栈顶元素 并返回 TRUE 否则返回 FALSE Status Push SqStack S SElemType e 插入元素 e 为新的栈顶元素 Status Pop SqStack S SElemType e 若栈不为空 则删除栈顶元素 并用 e 返回其值 返 回 OK 否则返回 ERROR Status StackTraverse SqStack S Status visit 从栈顶到栈底依次对栈中每个元素调用函数 visit 一旦调用 visit 失败 则操作失败 Status visit SElemType c 基本操作的算法描述 构造一个新的栈 Status 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 销毁栈 S S 不再存在 Status DestroyStack SqStack S free S base S base NULL S top NULL S stacksize 0 return OK 把 S 置为空栈 Status ClearStack SqStack S S top S base return OK 若栈 S 为空栈 则返回 TRUE 否则返回 FALSE Status StackEmpty SqStack S if S top S base return TRUE else return FALSE 返回 S 的元素个数 即栈的长度 int StackLength SqStack S return S top S base 若栈不为空 用 e 返回 S 的栈顶元素 并返回 TRUE 否则返回 FALSE Status GetTop SqStack S SElemType e if S top S base return ERROR e S top 1 return OK 插入元素 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 若栈不为空 则删除栈顶元素 并用 e 返回其值 返回 OK 否则返回 ERROR Status Pop SqStack S SElemType e if S top S base return ERROR e S top return OK 从栈底到栈顶依次对栈中每个元素调用函数 visit Status StackTraverse SqStack S Status visit SElemType 一旦 visit 失败 则操作失败 while S top S base visit S base printf n return OK 栈中每个元素的访问函数 Status visit SElemType c printf d c return OK int main void int j SqStack s SElemType e if InitStack j 12 j Push 如栈 printf 栈中元素依次为 StackTraverse s visit Pop printf 弹出的栈顶元素 e d n e printf 栈空否 d 1 空 0 否 n StackEmpty s GetTop s printf 栈顶元素 e d 栈的长度为 d n e StackLength s ClearStack