顺序栈

顺序栈用数组实现，栈顶指针 top 指向栈顶元素（或栈顶元素的下一个位置）。

#define MaxSize 100
typedef struct {
    int data[MaxSize];
    int top;  // 栈顶指针，初始为 -1，指向栈顶元素
} SqStack;

入栈

bool Push(SqStack &S, int x) {
    if (S.top == MaxSize - 1) return false;  // 栈满
    S.data[++S.top] = x;  // 先加1再入栈
    return true;
}

出栈

bool Pop(SqStack &S, int &x) {
    if (S.top == -1) return false;  // 栈空
    x = S.data[S.top--];  // 先出栈再减1
    return true;
}

读取栈顶

bool GetTop(SqStack S, int &x) {
    if (S.top == -1) return false;
    x = S.data[S.top];
    return true;
}

时间复杂度：入栈、出栈、取栈顶均为 $O(1)$。

共享栈

两个栈共享同一数组空间，分别从两端向中间生长，可以充分利用空间，减少栈满的可能。

typedef struct {
    int data[MaxSize];
    int top0;  // 栈0栈顶，初始 -1，向右生长
    int top1;  // 栈1栈顶，初始 MaxSize，向左生长
} ShareStack;
// 栈满条件：top0 + 1 == top1