美文网首页
顺序栈的表示和实现

顺序栈的表示和实现

作者: 搬砖的猫 | 来源:发表于2019-10-28 10:47 被阅读0次

    顺序栈是指利用顺序存储结构实现的栈,即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。

    顺序栈的定义

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

    顺序栈的初始化

    (1)为顺序栈动态分配一个最大容量为MAXSIZE的数组空间,使base指向这段空间的基地址,即栈底。
    (2)栈顶指针top初始为base,表示栈为空。
    (3)stacksize置为栈的最大容量MAXSIZE。

    //顺序栈的初始化
    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;
    } 
    

    顺序栈的入栈

    (1)判断栈是否满,若满则返回ERROR。
    (2)将新元素压入栈顶,栈顶指针加1。

    //顺序栈的入栈
    Status Push(SqStack &S, SElemType e){
        //插入元素e为新的栈顶元素 
        if(S.top - S.base == S.stacksize){  //栈满 
            return ERROR;
        }
        *S.top ++ = e;                      //元素e压入栈顶,栈顶指针加1 
        return OK;
    } 
    

    顺序栈的出栈

    (1)判断栈是否空,若空则返回ERROR。
    (2)栈顶指针减1,栈顶元素出栈。

    //顺序栈的出栈
    Status Pop(SqStack &S, SElemType e){
        //删除S的栈顶元素,用e返回其值 
        if(S.top == S.base){               //栈空 
            return ERROR;
        } 
        e == *--S.top;                     //栈顶指针减1,将栈顶元素赋给e 
        return OK;
    } 
    

    取顺序栈的栈顶元素

    //取顺序栈的栈顶元素
    SElemType GetTop(SqStack S){
        //返回S的栈顶元素,不修改栈顶指针 
        if(S.top != S.base){        //栈非空   
            return *(S.top - 1);    //返回栈顶元素的值,栈顶指针不变 
        }
    } 
    

    小结

    由于顺序栈和顺序表一样,受到最大空间容量的限制,虽然可以在“满员”时重新分配空间扩大容量,但工作量较大,应该尽量避免。

    相关文章

      网友评论

          本文标题:顺序栈的表示和实现

          本文链接:https://www.haomeiwen.com/subject/mzbvvctx.html