#define MaxSize 100
#define OK 1
#define ERROR 0
/** 栈
* s=(a1,a2,a3,a4,a5)
* a1 栈底
* a5 栈顶
* 入栈(压栈)push
* 出栈(弹栈)pop
* 案例1 - 进制转换,倒取余
* 案例2 - 括号匹配检测
* 案例3 - 表达式求值(算符优先算法:操作数、运算符、界限符)
* ADT Stack {
* 数据对象:D={ai|ai 属于 ElemSet ,i=1,2,3,4}
* //todo
* }
* InitStack(&S) //创建栈
* DestroyStack(&S) //销毁
* StackEmpty(S) //判断空
* StackLength(S) //获取栈长度
* GetTop(S,&e) //获取栈顶元素
* ClearStack(&S)//清空
* Push(&S,e) //入栈
* Pop(&S,&e) //出栈
*
* 关键词:push-上溢,pop-下溢
*
* 顺序栈
* 指针:top:指向最后一个元素的后一个
* top -> | |
* |===|
* |===|
* base -> |===|
* base:指向第一个元素
* 元素个数: top-base
* 栈的最大容量: stackSize
* 满栈 top-base==stackSize
*
* */
class ShuXuStack {
typedef int SElemType;
typedef struct {
SElemType *base;
SElemType *top;
int stackSize;
} SqStack;
int InitStack(SqStack &S) {
S.base = new SElemType[MaxSize]; //
// S.base=(SElemType *)malloc(MaxSize*sizeof(SElemType));
if (S.base) exit(OVERFLOW);
S.top = S.base;
S.stackSize = MaxSize;
return OK;
}
bool StackEmpty(SqStack S) {
return S.base == S.top;
}
int StackLength(SqStack S) {
return S.top - S.base;
}
int ClearStack(SqStack &S) {
if (S.base) S.top = S.base;
return OK;
}
int DestroyStack(SqStack &S) {
if (S.base) {
delete S.base;
S.stackSize = 0;
S.base = S.top = NULL;
}
return OK;
}
int Push(SqStack &S, SElemType e) {
/**判断是否满
* e 入栈
* 指针+1
* */
if (S.top - S.base == S.stackSize) return ERROR; //栈满
*S.top++ = e;
return OK;
}
int Pop(SqStack S, SElemType &e) {
if (S.top == S.base) return ERROR; //下溢
e = *--S.top; //S.top 先下移,否则取不到元素
return OK;
}
};
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。