栈理论基础
## 栈的定义
栈就是**操作受限的线性表**，先进后出 **FILO（First In Last Out）**
一般设立栈顶指针初值为 `top = -1`（栈空）
⭐ 从栈顶出队，从栈顶进队
**进栈**：`top ++;`
**出栈**：`top --;`
## 共享栈
一般设初值为 `top1 = -1` (栈空)，`top2 = n` (栈空)，用 `S[0:n-1]` 表示
当且仅当 `top2-top1 = 1` 时共享栈满（即两个栈顶指针相邻）
## 出栈序列
若元素的进栈序列为 ABCDE, 运用栈操作，能否得到出栈序列 BCAED 和 DBACE？
- BCAED 正确
- DBACE 不可能：若 D 为首先出栈元素，已知 ABC 先于 D 入栈， C 不可能后于 AB 出栈
## 实际应用举例
设计算法判断单链表（字符型data域)的全部n个字符是否中心对称。
ex: xyx, xyyx
思路：利用栈的先进后出的特点，将链表前一半元素依次进栈，然后将栈中元素出栈，与链表的后半元素依次进行比较。
```c
int dc(LinkList L, int n){
char s[n/2]; //字符栈，同数组实现栈的功能
p = L->next;
for(int i = 0; i < n/2; i++){ //链表前一半元素进栈
s[i] = p->data;
i++;
}
i--; //恢复最后的i值
if(n%2!=0) //若n为奇数，后移过中心结点
p = p->next;
while(p!=NULL && s[i]=p->data){ //检测是否中心对称
i --; //i充当栈顶指针
p = p->next;
}
if(i = -1) //空栈
return 1;
else
return 0;
}
```
## 将中缀表达式转化为后缀表达式
**核心思想** ：栈外字符加入栈内时，要保证栈外字符的优先级比栈内所有字符的优先级都要低，否则，弹出栈内优先级较高的字符，并加入后缀表达式。
**步骤** ：
- 遇到字母或数字直接入栈；
- 遇到运算符时：
- - 若为'(', 直接入栈；
- 若为')', 依次把栈中运算符加入后缀表达式，直到出现‘(’, 并从栈中将‘(’删除；
- 若为其他运算符，**根据优先级表依次弹出比当前处理的运算符优先级高的运算符**，并将其加入后缀表达式，直到遇到一个比它优先级低的或遇到了一个'('为止。
**运算符优先级表**
| 操作符 | # | （ | *，/ | +，- | ） |
| ---------- | ---- | ---- | ---- | ---- | ---- |
| 栈内优先级 | 0 | 1 | 5 | 3 | 6 |
| 栈外优先级 | 0 | 6 | 4 | 2 | 1 |
## 栈在递归中的应用
ex：斐波拉契数列 0 1 1 2 3 5 ...
```c
int Fib(int n){
if(n == 0)
return 0;
else if(n == 1)
return 1;
else c
return Fib(n-1) + Fib(n-2);
}
```
递归必要的两个条件：
- 递归表达式（递归体）
- **递归出口**（边界条件）
> 采用非递归方式重写递归程序时必须使用栈。该说法是错误的！
>
> ex: 计算斐波拉契数列可用循环实现
函数调用时，系统要用栈保存必要的信息；递归次数过多容易造成栈溢出