[数据结构与算法]数据结构 顺序栈

一、栈的定义

? ? ? ? 栈时限定仅在表尾进行插入或删除操作的线性表。所以称表尾为栈顶，表头称为栈底。不含元素的栈称为空栈。栈是一种后进先出的线性表。

????????????????????????????????????? ? ? ??

?

二、顺序栈

????????是指利用顺序存储结构实现的栈，即用一组连续的存储单元依次存放自栈底到栈顶的数据元素。定义如下

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

????????其中，base为栈底指针，初始化完成后，栈底指针始终指向栈底的位置，若base为NULL时，表示栈不存在。top为栈顶指针，初值指向栈底，每增加一个新元素时，top+1，删除栈顶元素时，top-1。?所以，栈空时，base和top都指向栈底，非空时，top始终指向栈顶元素的上一个位置。

1.初始化

? ? ? ?

Status InitStack(Sqstack &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;
}

2.入栈

Status Push(SqStack &S, SElemType e)
{
    if(S.top-S.base==S.stacksize) return ERROR;    //判断是否栈满
        *S.top++=e;          //将元素e压入栈底，top指针加1
        //此处也可以写成
        //*S.top=e;
        //S.top++;
        return OK;
}

? ? ? ? 注意判断栈是否为满，并且先将e赋值给top指针指向的地方，再将top+1。

3.出栈

Status Pop(SqStack &S, SElemType &e)
{
    if(S.top==S.base) return ERROR;    //判断是否栈空
        e=*--S.top;          //将top指针减1，赋值给e返回
        //此处也可以写成
        //--S.top;
        //e=*S.top;
        return OK;
}

? ? ? ? 注意判断栈是否为空，并且先将top指针减1，再将top指向的值赋值给e返回

? ? ? ?

????????我自己刚学习的时候有一个误区，就是误以为出栈必须得将top指向的值给删除或者赋空值才算删除，实际上是可以忽略值的，只由base和top两个指针判断是否为空栈或满栈就行了，并且入栈新元素时，top指向的旧值会被新入栈的值覆盖掉，所以不用删除旧值。

4.取栈顶元素

Status GetTop(SqStack &S)
{
    if(S.top!=S.base)          //判断是否为空
        return *(S.top-1);     //返回栈顶元素
}