顺序栈

栈的顺序存储类型

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

顺序栈的初始化

void InitStack(SqStack &S)
{
    S.top=-1;       //初始化栈顶指针,这里规定top指向当前元素
                    //有的教材中将S.top定义为0,规定top指向栈顶的下一个元素
}

栈判空

bool StackEmpty(SqStack S)
{
    if(S.top == -1)
        return TRUE;
    else
        return FALSE;
}

进栈

Status Push(SqStack &S,ElemType x)
{
    if(S.top == MaxSize-1) //栈满 从0开始 最多S.data[MaxSize-1]
        return FALSE;
    S.top+=1;
    S.data[S.top] = x;
    //若S.top = 0 即栈顶指针指向栈顶元素的上一个位置
    //S.data[S.top]=x;
    //S.top++;  栈满为S.top == MaxSize
    return TRUE;
}

出栈

Status Pop(SqStack &S, ElemType &x)
{
    if(S.top == -1)
        return FALSE;
    x = S.data[S.top];
    S.top--;
    //若定义初始S.top=0
    //判空条件为S.top == 0;
    //S.top--;
    //x = S.data[S.top];
    return TRUE;
}

读取栈顶元素

Status GetTop(SqStack S, ElemType &x)
{
    if(S.top == -1)
        return FALSE;
    x = S.data[S.top];
    return TRUE;
}

假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的序列均由 I 和 O 组成，可以操作的序列称为合法序列，否则称为非法序列。写出一个算法，判断所给的操作序列是否合法。

bool judge(char A[],int Length)
{
    int i = 0;
    int flag = 0;
    while(i < Length)
    {
        if(A[i] == 'I')
        {
            flag++;
        }
        else
        {
            flag--;
        }

        if(flag < 0)
        {
            return FALSE;
        }

        i++;
    }

    if(flag != 0)
        return FALSE;

    return TRUE;
}