栈的抽象数据类型的定义


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指针,指示栈底元素在顺序栈中的位置。

Snipaste_2023-08-19_10-03-08

但是,为了方便操作,通常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;

}

顺序栈的入栈

  1. 判断是否栈满,若满则出错(上溢)

  2. 元素e压入栈顶

  3. 栈顶指针加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;

}

顺序栈的出栈

  1. 判断是否栈空,若空则出错(下溢)

  2. 获取栈顶元素e

  3. 栈顶指针减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; 

}