栈 Stack ADT
一、前提条件：栈是一种线性表。

它的特点是：只能在一端插入和删除。

这一端叫：栈顶 top

另一端叫：栈底 bottom

二、核心概念

栈的规则是：后进先出 LIFO

也就是：Last In First Out

例如依次入栈：
1
2
3

栈内逻辑是：
栈顶
 ↓
3
2
1

先进的扔到栈底，后进的在栈顶

出栈顺序是：
3 -> 2 -> 1

三、基本操作

栈 ADT 常见操作：

InitStack     初始化栈
Push          入栈
Pop           出栈
GetTop        取栈顶元素
IsEmpty       判空
IsFull        判满

四、顺序栈
1. 存储结构：用数组实现。

#define MAXSIZE 100

struct Stack {
    int data[MAXSIZE];
    int top;
};

这里：
data 存元素
top 表示栈顶下标

2. top 的定义

常见写法：top = -1 表示空栈

如果压入第一个元素：

top = 0

栈：

data[0]

如果再压入一个：

top = 1

栈：

data[0], data[1]

所以：top 永远指向当前栈顶元素。

五、顺序栈 C 语言模板

1. 初始化
void InitStack(struct Stack* s)
{
    s->top = -1;
}

2. 判空
int IsEmpty(struct Stack* s)
{
    return s->top == -1;
}

3. 判满
int IsFull(struct Stack* s)
{
    return s->top == MAXSIZE - 1;
}

4. 入栈 Push
int Push(struct Stack* s, int x)
{
    if (IsFull(s)) {
        return 0;
    }

    s->top++;
    s->data[s->top] = x;

    return 1;
}

也可以写成：
s->data[++s->top] = x;


5. 出栈 Pop
int Pop(struct Stack* s, int* x)
{
    if (IsEmpty(s)) {
        return 0;
    }

    *x = s->data[s->top];
    s->top--;

    return 1;
}

这里用：int* x

是为了把出栈元素带回去。

6. 读取栈顶 GetTop
int GetTop(struct Stack* s, int* x)
{
    if (IsEmpty(s)) {
        return 0;
    }

    *x = s->data[s->top];

    return 1;
}

注意：

GetTop 只读取，不删除。
Pop 读取并删除。

六、顺序栈完整代码
#define MAXSIZE 100

struct Stack {
    int data[MAXSIZE];
    int top;
};

void InitStack(struct Stack* s)
{
    s->top = -1;
}

int IsEmpty(struct Stack* s)
{
    return s->top == -1;
}

int IsFull(struct Stack* s)
{
    return s->top == MAXSIZE - 1;
}

int Push(struct Stack* s, int x)
{
    if (IsFull(s)) {
        return 0;
    }

    s->top++;
    s->data[s->top] = x;

    return 1;
}

int Pop(struct Stack* s, int* x)
{
    if (IsEmpty(s)) {
        return 0;
    }

    *x = s->data[s->top];
    s->top--;

    return 1;
}

int GetTop(struct Stack* s, int* x)
{
    if (IsEmpty(s)) {
        return 0;
    }

    *x = s->data[s->top];

    return 1;
}
七、顺序栈例子

初始：top = -1
栈为空

执行：Push(&s, 10);

变成：
data[0] = 10
top = 0

执行：Push(&s, 20);

变成：

data[0] = 10
data[1] = 20
top = 1

栈顶是：20

执行：Pop(&s, &x);

得到：

x = 20
top = 0

栈里剩：10

八、链式栈

顺序栈用数组，有最大容量限制。

链式栈用链表，没有固定容量限制。

1. 存储结构

struct Node {
    int data;
    struct Node* next;
};

struct LinkedStack {
    struct Node* top;
};

这里：top 指向链表第一个节点。

也就是：链表头部就是栈顶。

九、链式栈 C 语言模板
1. 初始化
void InitLinkedStack(struct LinkedStack* s)
{
    s->top = NULL;
}
2. 判空
int IsLinkedStackEmpty(struct LinkedStack* s)
{
    return s->top == NULL;
}
3. 入栈 Push

链式栈入栈本质是：

头插法
#include <stdlib.h>

int PushLinkedStack(struct LinkedStack* s, int x)
{
    struct Node* node =
        malloc(sizeof(struct Node));

    if (node == NULL) {
        return 0;
    }

    node->data = x;
    node->next = s->top;
    s->top = node;
//这里相当于是把node的next赋NULL，之后把top指向node，每次头插进之后，top都指向新的node，
    return 1;
}

4. 出栈 Pop

链式栈出栈本质是：

删除头节点
int PopLinkedStack(struct LinkedStack* s, int* x)
{
    if (IsLinkedStackEmpty(s)) {
        return 0;
    }

    struct Node* p = s->top;

    *x = p->data;

    s->top = p->next;
//相当于就是把top对应的值返回给x，然后top去取next的值，这样相当于把原节点跳过
    free(p);

    return 1;
}

5. 读取栈顶
int GetLinkedStackTop(struct LinkedStack* s, int* x)
{
    if (IsLinkedStackEmpty(s)) {
        return 0;
    }

    *x = s->top->data;

    return 1;
}

十、链式栈完整代码
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

struct LinkedStack {
    struct Node* top;
};

void InitLinkedStack(struct LinkedStack* s)
{
    s->top = NULL;
}

int IsLinkedStackEmpty(struct LinkedStack* s)
{
    return s->top == NULL;
}

int PushLinkedStack(struct LinkedStack* s, int x)//入栈
{
    struct Node* node =
        malloc(sizeof(struct Node));

    if (node == NULL) {
        return 0;
    }

    node->data = x;
    node->next = s->top;
    s->top = node;

    return 1;
}

int PopLinkedStack(struct LinkedStack* s, int* x)//出栈
{
    if (IsLinkedStackEmpty(s)) {
        return 0;
    }

    struct Node* p = s->top;

    *x = p->data;

    s->top = p->next;

    free(p);

    return 1;
}

int GetLinkedStackTop(struct LinkedStack* s, int* x)//查看栈顶
{
    if (IsLinkedStackEmpty(s)) {
        return 0;
    }

    *x = s->top->data;

    return 1;
}

十一、链式栈例子

初始：top = NULL

入栈 10：

top
 ↓
10 -> NULL

入栈 20：

top
 ↓
20 -> 10 -> NULL

入栈 30：

top
 ↓
30 -> 20 -> 10 -> NULL

出栈：

弹出 30
top 指向 20

变成：

top
 ↓
20 -> 10 -> NULL

十二、顺序栈和链式栈
类型	存储方式	优点	缺点
顺序栈	数组	简单、访问快	容量固定

链式栈	链表	容量灵活	需要 malloc/free

栈的常见算法题

栈常用于：
1. 括号匹配
2. 表达式求值
3. 单调栈
4. 递归转非递归
5. DFS
6. 函数调用栈
7. 浏览器前进后退
8. 字符串消除


顺序栈优点：
    简单，速度快。

顺序栈缺点：
    容量固定。

链式栈优点：
    容量灵活。

链式栈缺点：
    需要动态申请和释放内存。
    
栈就是只能在一端操作的线性表，规则是后进先出。