【数据结构】第3章栈和队列顺序栈

Bertha 。 2022-11-27 10:29 113阅读 0赞

【顺序栈的初始化、判空、取栈顶元素、入栈、出栈】  
栈和队列是操作受限的线性表

--------------------

`S.base`：栈底指针，始终指向栈底  
`S.top`：栈顶指针， 栈空时指向栈底，栈非空时指向栈顶元素的上一个位置  
栈满：`S.top - S.base == S.stacksize`  
栈空：`S.top == S.base` 都指向栈底  
入栈：`*S.top++ = e` 先入栈，再栈顶指针++  
出栈：`e = *--S.top` 先栈顶指针- -，再出栈

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]

#include<bits/stdc++.h>
    using namespace std;
    typedef int Status;
    typedef int SElemType;
    #define OVERFLOW -1
    #define ERROR 0
    #define OK 1
    
    //------顺序栈的存储结构-----
    #define MAXSIZE 100
    typedef struct
    {
        
        SElemType *base;    //栈底指针
        SElemType *top;     //栈顶指针
        int stacksize;      //栈可用的最大容量
    }SqStack;
    
    SqStack S;
    
    //1、顺序栈初始化
    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;
        return OK;
    }
    
    //2、顺序栈销毁
    //3、顺序栈清空
    //4、顺序栈判空
    int StackEmpty(SqStack S)
    {
        
        if(S.top == S.base)
            return OK;
        else
            return ERROR;
    }
    
    //6、顺序栈取栈顶元素
    SElemType GetTop(SqStack S)
    {
        //返回S的栈顶元素， 不修改栈顶指针
        if(S.top != S.base)                 //栈非空
            return *(S.top - 1);            //返回栈顶元素的值，栈顶指针不变
    }
    
    //7、顺序栈入栈
    Status Push(SqStack &S, SElemType e)
    {
        //插入元素e为新的栈顶元素
        if(S.top - S.base == S.stacksize)
            return ERROR;                   //栈满
        *S.top++ = e;                       //先将元素e压入栈顶，再栈顶指针+1
        return OK;
    }
    
    //8、顺序栈出栈
    Status Pop(SqStack &S, SElemType &e)
    {
        //删除S的栈顶元素，用e返回其值
        if(S.top == S.base)
            return ERROR;                   //栈空
        e = *--S.top;                       //先栈顶指针-1，再将栈顶元素赋给e
        return OK;              
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/28fd2dcef4674aae9a583ed185b27219.png