栈的抽象数据类型的定义
ADT Stack{
数据对象:
D={ai|ai∈ElemSet,i=1,2,.....,n,n≥0}
数据关系:
R1 ={<ai-1,ai> |ai-1,ai∈D,i=2,...n
约定an端为栈顶,a1端为栈底。
基本操作:初始化、进栈、出栈、取栈顶元素等
}ADT Stack
顺序栈
存储方式:同一般线性表的顺序存储结构完全相同,
利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端。
-
附设top指针,指示栈顶元素在顺序栈中的位置。
-
另设base指针,指示栈底元素在顺序栈中的位置。
但是,为了方便操作,通常top指示真正的栈顶元素之上的下标地址
-
空栈:base == top 是栈空标志
-
栈满 :top - base == stacksize
-
栈满时的处理方法
-
报错,返回操作系统
-
分配更大的空间,作为栈的存储空间,将原栈的内容移入新栈。
-
使用数组作为顺序栈存储方式的特点:
简单、方便、但易产生溢出(数组大小固定)
-
上溢(overflow):栈已经满,又要压入元素
-
下溢(underflow):栈已经空,还要弹出元素
注:上溢是一种错误,使问题的处理无法进行;而下溢一般认为是一种结束条件,即问题处理结束。
顺序栈的表示
#define MAXSIZE 100
typedef struct{
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //栈可用最大容量
}SqStack;
顺序栈的初始化
Status 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;
}
顺序栈判断是否为空
Status StackEmpty(SqStack S){
//若栈为空,返回TRUE;否则返回FALSE
if (S.top == S.base)
return TRUE;
else
return FALSE;
}
求顺序栈长度
int StackLength(SqStack S)
{
return S.top - S.base;
}
清空顺序栈
Status ClearStack(SqStack S){
if(S.base) S.top = S.base;
return OK;
}
销毁顺序栈
Status DestroyStack(SqStack &S ){
if(S.base){
delete S.base;
S.stacksize = 0;
S.base = S.top = NULL;
}
return OK;
}
顺序栈的入栈
-
判断是否栈满,若满则出错(上溢)
-
元素e压入栈顶
-
栈顶指针加1
Status Push(SqStack &S,SElemType e){
if(S.top-S.base == S.stacksize)//栈满
return ERROR;
*S.top++=e; //相当于先进行*S.top = e;再进行S.top++;
return OK;
}
顺序栈的出栈
-
判断是否栈空,若空则出错(下溢)
-
获取栈顶元素e
-
栈顶指针减1
Status Pop(SqStack &S,SElemType &e){ //若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
if(S.top==S.base) //等价于if(StackEmpty(S))
return ERROR;
e = *--S.top; //相当于先进行--S.top;再进行e = *S.top;
return OK;
}