个人学习笔记——栈的存储结构及基本操作

//栈的表示还有操作（个人笔记）

//顺序栈


//顺序栈的存储结构
#define MAXSIZE 100  /顺序栈存储空间的初始分配量
typedef struct
{
      SElemType *base;  //栈底指针
      SElemType *top;   //栈顶指针
      int stacksize;  //栈可用的最大容量
}SqStack;
  
//栈的初始化
Status Initstack(SqStack &S)
{
        S.base=new SElemType[MAXSIZE];  //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
        if(!S.base)
                return 0;  //存储分配失败
        S.base=S.top;      //初始化为空栈
        S.stacksize=MAXSIZE;
        return OK;
}

//入栈操作

Status Push(SqStack &S,SElemType e)
{
        if(S.top-S.base==S.stacksize)   //判断栈是否已满
                return ERROR;
        *S.top++=e;
        //S.top=S.top+1;
        //S.top=e;
        return OK;
}

//出栈

Status Pop(SqStack &S,SElemType &e)
{
        if(S.top==S.base)   //判断栈是否为空
        {
                return ERROR;
        }
        e=*--S.top;
        //S.top=S.top-1;
        //e=*S.top;
        return OK;
}

//取栈顶元素

SElemType GetTop(SqStack S)
{
        if(S.top!=S.base)
        return *(S.top-1);
}



//链栈的表示和实现

//链栈的存储结构
typedef struct StackNode
{
        ElemType data;
        struct StackNode *next;
}StackNode,*linkStack;



//链栈初始化

Status InitStack(linkStack &S)
{
        S=NULL;
        return OK;
}

//链栈入栈操作


Status Push(linkStack &S,SElemType e)
{
       p=new StackNode;  //生成新节点
       p->data=e;        //将新节点数据域置为e
       p->next=S;        //将新节点插入栈顶
       S=p;              //修改栈顶指针为p
       return OK; 
}

//链栈出栈操作

Status Pop(linkStack &S,SElemType &e)
{
        if(S==NULL)    //判断是否为空栈
                return ERROR;
        e=S->data;     //将栈顶元素赋给e
        p=S;           //用p临时保存栈顶元素空间，以便释放。这一步更为关键
        S=S->next;     //修改栈顶指针
        delete p;      //释放原栈顶指针元素的空间
        return OK;
}

//取栈顶元素

SElemType GetTop(linkStack S)
{
        is(S!=NULL)        //判断是否为空栈
        return S->data;    //返回栈顶元素的值
}

资料参考：《数据结构》人民邮电出版社（十二五国家级规划教材）