栈的基本概念

栈是只允许在一端进行插入或删除操作的线性表。

栈的逻辑结构和线性表一样。

01 顺序栈

顺序栈由两部分组成，第一部分是静态数组，存放栈中的元素，第二部分是栈顶指针。

初始化栈

void InitStack(SqStack &S) {

    S.top  = -1;

}

判断栈空

bool StackEmpty(SqStack S) {

    return S.top == -1;

}

进栈

bool Push(SqStack &S, ElemType x) {

    // 判断栈是否存满，注意下标是从0开始的。

    if(S.top == MaxSize-1) 

        return false;

    S.top = S.top + 1;

    S.data[S.top] = x;

    return true;

}

出栈

bool Pop(SqStack &S, ElemType &x) {

    if(S.top == -1) 

        return false;    

    x = S.data[S.top];

    S.top = S.top - 1;

    return true;

}

读栈顶元素

bool GetTop(SqStack S, ElemType &x) {

    if(S.top == -1) 

        return false;

    x = S.data[S.top];

    return true;

}

02 共享栈

两个栈共享同一片内存，从两边往中间增长。

初始化的时候，top0 == -1,top1 == MaxSize。

而栈满条件为 top0 + 1 == top1 。

03 链栈

链栈的定义

typedef struct Linknode {

    ElemType data;

    struct Linknode *next;

} *ListStack;