栈的基本操作

定义

栈是只允许在一端（栈顶）进行插入和删除的线性表。

• LIFO：后进先出（Last In First Out）
• 栈顶（Top）：允许操作的一端
• 栈底（Bottom）：不允许操作的一端

栈的操作

• Push：入栈，在栈顶插入
• Pop：出栈，删除栈顶
• GetTop：取栈顶（不出栈）

一、顺序栈

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int top;  // 栈顶指针（下标）
} SqStack;

初始化 / 判空

void InitStack(SqStack *S) { S->top = -1; }
bool StackEmpty(SqStack S) { return (S.top == -1); }

入栈

bool Push(SqStack *S, ElemType x) {
    if (S->top == MaxSize - 1) return false;  // 栈满
    S->data[++S->top] = x;                    // 先加后存
    return true;
}

出栈

bool Pop(SqStack *S, ElemType *x) {
    if (S->top == -1) return false;  // 栈空
    *x = S->data[S->top--];          // 先取后减
    return true;
}

读栈顶

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

二、共享栈（两栈共享空间）

#define MaxSize 50
typedef struct { ElemType data[MaxSize]; int top1, top2; } ShStack;
void InitShStack(ShStack *S) { S->top1 = -1; S->top2 = MaxSize; }

• 栈 1 从前往后增长，栈 2 从后往前增长
• 栈满：$ top1 + 1 == top2 $
• 栈 1 空：$ top1 == -1 $，栈 2 空：$ top2 == MaxSize $

三、链栈

typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode, *LiStack;

初始化 / 入栈（头插）/ 出栈

void InitLiStack(LiStack *S) { *S = NULL; }   // 不带头结点
void Push(LiStack *S, ElemType x) {            // 头插法
    LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
    p->data = x; p->next = *S; *S = p;
}
bool Pop(LiStack *S, ElemType *x) {
    if (*S == NULL) return false;
    LinkNode *p = *S; *x = p->data; *S = p->next; free(p); return true;
}