栈（定义，基本操作，顺序存储，链式存储）

链式存储）"/>

栈（定义，基本操作，顺序存储，链式存储）

目录

• 1.栈的定义
• • 1.重要术语
  • 2.特点
• 2.栈的基本操作
• 3.栈的顺序存储
• • 1.顺序栈的定义
  • 2.基本操作
  • • 1.初始化
    • 2.进栈
    • 3.出栈
    • 4.读栈顶
  • 3.共享栈
• 4.栈的链式存储

1.栈的定义

栈( Stack）是只允许在一端进行插入或删除操作的线性表。
一种受限的线性表，只能在栈顶进行插入删除。

1.重要术语

①栈顶：允许插入和删除的一端。
②栈底：不允许插入和删除的一端。
③空栈：对应线性表的空表。
④栈顶元素
⑤栈底元素

2.特点

后进先出：Last In First Out (LIFO)

2.栈的基本操作

1. InitStack(&S)：初始化栈。构造一个空栈S，分配内存空间。
2. DestroyStack(&L)：销毁栈。销毁并释放栈S所占用的内存空间。
3. Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。
4. Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。（删除栈顶元素）
5. GetTop(S,&x)：读栈顶元素。若栈S非空，则用x返回栈顶元素。（不删除栈顶元素）
6. StackEmpty(S)：判断一个栈S是否为空。若S为空，则返回true，否则返回false。

n个不同元素进栈，出栈元素不同排列的个数为 1 n + 1 C 2 n n \frac{1}{n+1}C_{2n}^n n+11​C2nn​。
上述公式称为卡特兰(Catalan）数，可采用数学归纳法证明。

3.栈的顺序存储

顺序存储：给各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType)
用静态数组实现，并需要记录栈顶指针。

1.顺序栈的定义

顺序栈的缺点:栈的大小不可变。

2.基本操作

1.初始化

2.进栈

3.出栈

4.读栈顶

3.共享栈

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

栈满的条件： top0 + 1 == top1

4.栈的链式存储

本质上用链式存储实现栈就是只允许在单链表的一段进行插入和删除操作。
进栈对应插入操作，出栈对应删除操作。

进栈/出栈都只能在栈顶一端进行(链头作为栈顶)。