静态数组实现顺序栈

栈 是一种 线性数据结构，它的核心规则是 “后进先出”（Last In, First Out，简称 LIFO）。可以把它想象成日常生活中的：一叠盘子：最后放上去的盘子，最先被拿下来；

栈 只允许在一端（称为 “栈顶”） 进行数据的添加(入栈) 和 删除(出栈)操作，另一端（栈底）是封闭的，无法直接操作。

栈的核心操作

• 入栈（push）：把数据添加到栈顶；
• 出栈（pop）：从栈顶移除并返回数据（栈为空时出栈会报错）；
• 查看栈顶（peek/top）：只看栈顶的数据，不删除；
• 判空（isEmpty）：检查栈是否为空；
• 获取长度（size）：查看栈中有多少个元素；
• 判满：检查栈是否满了。

顺序栈的实现

用静态数组实现栈，数组的大小由MaxSize固定，属于 “静态栈”（容量不可动态扩展,除此还有链栈）

top 的含义：

• 初始化时：top = -1（表示栈为空，栈底的前一个位置）；
• 入栈时：top++，再把元素存入data[top]；
• 出栈时：先取data[top]，再top--；
• 栈满的条件：top == MaxSize - 1（数组下标从 0 开始，最后一个位置是 MaxSize-1）

* top 更准确来说就是 SqStack.data 的下标，涉及到下标时，全部使用 top

栈的结构
#define MaxSize 50
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];
    int top;
}SqStack;

* 初始化栈：S.top=-1 表示 栈为空

初始化栈
void InitStack(SqStack &S){
    S.top=-1;//初始化栈，S.top=-1表示栈为空
}

判空
bool StackEmpty(SqStack S){
    if(S.top==-1){
        return true;
    } else{
        return false;
    }
}

* 入栈：入栈前需要检查栈是否满了

入栈
bool Push(SqStack &S,ElemType x){
    // 判断栈是否满了
    if(S.top==MaxSize-1){
        return false;
    }
    S.data[++S.top]=x;
    // 等价于
    // S.top=S.top+1;
    // S.data[S.top]=x;
    return true;
}

* 查看栈顶:需要检查栈是否为空

获取栈顶元素
bool GetTop(SqStack S,ElemType &m){
    if(StackEmpty(S)){ //判空
        return false;
    }
    m=S.data[S.top]; //拿栈顶元素
    return true;
}

* 出栈：出栈前需要检查栈是否为空

出栈
bool Pop(SqStack &S,ElemType &m){
    if(StackEmpty(S)){ //判空
        return false;
    }
    m=S.data[S.top--]; //出栈
    // 等价于
    // m=S.data[S.top];
    // S.top=S.top-1;
    return true;
}

测试看看

int main() {
    SqStack S;
    InitStack(S);

    bool flag;
    flag=StackEmpty(S);
    if(flag){
        printf("stack is empty\n");
    }

    Push(S,3);
    Push(S,4);
    Push(S,5);

    ElemType m;
    flag=GetTop(S,m);
    if(flag){
        printf("get top:%d\n",m);
    }

    flag=Pop(S,m);
    if(flag){
        printf("Pop element:%d\n",m);
    }
    return 0;
}