栈的顺序存储结构

顺序栈：栈的顺序存储，利用一组地址连续的存储单元存放自栈底到栈顶的所有元素，同时附加一个用来指向当前栈顶位置的指针

指针指向栈顶（top）主要是因为栈在线性表的一端操作，操作的那端就是栈顶，方便操作。

顺序栈的存储类型

// 定义栈中元素的最大个数
# define MaxSize 50

// 结构体定义
typedef struct{
    ElemType data[MaxSize];     // 存放栈中元素
    int top;                    // 栈顶指针
}SqStack;

假设存在顺序栈S，则：

栈顶指针：S.top 初始化时设置S.top=-1
栈顶元素：S.data[S.top]，其中S.top为栈顶指针
进栈操作：栈不满时，栈顶指针+1，再送值到栈顶元素
出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针-1
栈空条件：S.top=-1
栈满条件：S.top=MaxSize-1
栈长：S.top+1

Tips: 进栈先移动指针，避免占满，元素无法添加，出现外溢；出栈先取栈顶元素，保证指针永远指向栈顶。

顺序栈的存储结构体定义可以很明显看出，顺序栈的入栈操作会受到数组上界(MaxSize)的约束。

当对栈的最大使用空间估计不足时，容易出现栈上溢(外溢)，需要主动向用户报告反馈，避免出现错误；

顺序栈的基本运算

InitStack(&S): 初始化一个空栈S,栈顶指针初始化为-1
StackEmpty(S): 判断一个栈是否为空，如果栈空则返回true,否则返回false
Push(&S,x): 进栈，若栈未满，x进栈操作，插入到栈内成为新的栈顶元素。
Pop(&S,&x): 出栈，若栈非空，出栈操作，弹出栈顶元素，用指针x进行返回。
GetTop(S,&x): 读栈顶元素，若栈S非空，用x返回栈顶元素。
ClearStack(&S): 销毁栈，释放栈S占用的存储空间。

初始化

InitStack(&S): 初始化一个空栈S,栈顶指针初始化为-1


void InitStack(&S){
    // 栈顶指针-1
    s.top=-1;
}

栈空判断

StackEmpty(S): 判断一个栈是否为空，即：栈顶指针是否为-1，如果栈空则返回true,否则返回false


bool StackEmpty(S){
    if(S.top==-1){
        // 栈空
        return true;
    }else{
        // 栈非空
        return false;
    }
}

进栈

Push(&S,x): 进栈，若栈未满，x进栈操作，插入到栈内成为新的栈顶元素。


bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize-1){
        // 栈满，返回false，元素无法进行进栈操作
        return false;
    }else{
        // 可进栈，栈顶指针+1，再元素入栈
        S.data[++S.top]=x;

        // 入栈成功
        return true;
    }
}

注意：

进栈先移动栈顶指针+1，再操作入栈元素
++i是简写，先对变量i进行递加操作，再进行使用，即：先加后用

出栈

Pop(&S,&x): 出栈，若栈非空，出栈操作，弹出栈顶元素，用指针x进行返回。


bool Pop(SqStack &S,ElemType &x){
    if(S.top==-1){
        // 栈空，无栈顶元素可出栈，返回false
        return false;
    }else{
        // 栈非空，先元素出栈，再进行指针-1
        x=S.data[S.top--];

        // 出栈成功，返回true
        return true;
    }
}

注意：

出栈操作，先让元素出栈，获取栈顶元素，再移动指针-1
i--是先使用变量i，再对变量做递减操作，即：先用后加（减）

读（获取）栈顶元素

GetTop(S,&x): 读栈顶元素，若栈S非空，用x返回栈顶元素。


bool GetTop(SqStack S,ElemType &x){

    if(S.top==-1){
        // 栈空，无栈顶元素,返回false
        return false;
    }else{

        // 通过栈顶指针，获取栈顶元素，赋值给变量x
        x=S.data[S.top];

        // 读取栈顶元素成功，返回true
        return true;
    }
}