数据结构-栈

  • 2020-10-04
  • 0
  • 0

一、栈的定义

1.栈(stack)是后进先出、限定仅在表尾进行插入和删除操作的线性表。

2.栈的插入和删除

pop //出栈

push //压栈

二、栈的顺序存储结构

*因为栈的本质是一个线性表,线性表有两种存储形式,那么栈也分为栈的顺序存储结构和栈的链式存储结构。

*最开始栈中不包含任何数据,叫做空栈,此时栈顶就是栈底。然后数据栈顶进入,栈顶底分离,整个栈的当前容量变大。数据从出栈时从栈顶弹出,栈顶下移,整个栈的当前容量变小。

栈中元素和栈指针之间的关系。

栈中元素和栈指针之间的关系

1.顺序栈的定义

如下:

#define MAXSIZE 100 //顺序栈存储空间的初始分配量
typedef struct
{
    SElemType *base; //栈底指针
    SElemType *top; //栈顶指针
    int stacksize; //栈可用的最大容量
}SqStack;

2.顺序栈的初始化

顺序栈的初始化操作就是为顺序栈动态分配一个预定义的大小的数组空间
Status InitStack (SqStack &S)
{//构造一个空栈S
    S.base=new SElemType[MAXSIZE];  //为顺序栈分配一个最大容量为MAXSIZE的数组空间
    if(!S.base) exit(OVERFLOW);     //存储分配失败
    S.top=S.base;                   //top初始化为base,空栈
    S.stacksize=MAXSIZE;            //stacksize置为栈的最大容量MAXSIZE
    return OK  ;
}

3.顺序栈入栈操作

入栈操作又叫压栈操作,就是向栈中存放数据。
入栈操作要在栈顶进行,每次向栈中压入一个数据,top指针就要+1,直到栈满为止。
Status Push (SqStack &S,SElemType &e)
{//插入元素e为新的栈顶元素
    if(S.tpo-S.base==S.stacksize) return ERROR;     //栈满
    *S.top++=e;                                     //元素e压入栈顶,栈顶指针加一
    return OK;
}

4.顺序栈的出栈操作

出栈操作是将栈顶元素取出,栈顶指针随之下移的操作。
每当从栈内弹出一个数据,栈的当前容量就-1.
Status Pop (SqStack &S,SElemType &e)
{//删除S的栈顶元素,用e返回其值
    if(S.tpo==S.base) return ERROR;     //栈空
    e=*--S.top;                       //栈顶指针减1,将栈顶元素赋给e
    S.stacksize=MAXSIZE;            //stacksize置为栈的最大容量MAXSIZE
    return OK;
}

评论

还没有任何评论,你来说两句吧