一、栈的定义

线性表是具有相同数据类型的n (n≥0) 个数据元素的有限序列，其中n为表长，当n =0时线性表是一个空表。若用L命名线性表，则其一般表示为$L=\left(a_{1}, a_{2}, ..., a_{i}, a_{i+1}, ..., a_{n}\right)$

栈(Stack) 是只允许在一端进行插入或删除操作的线性表，核心特点为后进先出（Last In First Out，LIFO）。

1. 重要术语
   • 栈顶：允许插入和删除的一端
   • 栈底：不允许插入和删除的一端
   • 空栈：不含任何元素的栈
2. 进栈与出栈顺序
   • 进栈顺序（示例）：$a1→a2→a3→a4→a5$
   • 出栈顺序（示例）：$a5 →a4→a3→a2→a1$

1.栈和线性表的基本操作对比

线性表基本操作

操作	功能描述
InitList(&L)	初始化表，构造空线性表L并分配内存
DestroyList(&L)	销毁线性表，释放占用内存
ListInsert(&L,i,e)	在表L第i个位置插入元素e
ListDelete(&L,i,&e)	删除表L第i个位置元素，并用e返回该元素
LocateElem(L,e)	按值查找表中对应元素
GetElem(L,i)	按位查找表中第i个位置元素
Length(L)	返回线性表长度
PrintList(L)	按顺序输出表中所有元素
Empty(L)	判断表是否为空，为空返回true

栈的基本操作

操作	功能描述
InitStack(&S)	初始化栈，构造空栈S并分配内存
DestroyStack(&S)	销毁栈，释放占用内存
Push(&S,x)	进栈，栈未满时将x加入成为新栈顶
Pop(&S,&x)	出栈，栈非空时弹出栈顶元素，并用x返回
GetTop(S,&x)	读栈顶元素，栈非空时用x返回栈顶元素
StackEmpty(S)	判断栈是否为空，为空返回true

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

栈的基本操作演示

下方模拟了 C 语言中栈的 6 个核心函数执行过程。请按顺序操作体验。

1. InitStack: 必须先初始化分配内存。
2. Push: 元素从上方落下，Top 指针上移。
3. Pop: 元素弹出消失，Top 指针下移。
4. Destroy: 内存清空，之后无法操作。

未分配内存

请先初始化栈

接口定义

操作	功能描述
InitStack(&S)	初始化栈，构造空栈S并分配内存
DestroyStack(&S)	销毁栈，释放占用内存
Push(&S,x)	进栈，栈未满时将x加入成为新栈顶
Pop(&S,&x)	出栈，栈非空时弹出栈顶元素
GetTop(S,&x)	读栈顶元素，不删除
StackEmpty(S)	判断栈是否为空

2.合法出栈顺序的数量

n个不同元素进栈，出栈元素不同排列的个数为卡特兰数，公式为$\frac{1}{n+1}C_{2n}^{n}$。 示例：当n=5时，$\frac{1}{5+1} C_{10}^{5}=\frac{10 * 9 * 8 * 7 * 6}{6 * 5 * 4 * 3 * 2 * 1}=42$，即5个元素合法出栈顺序有42种。