栈理论基础
# 栈的定义
栈就是操作受限的线性表,先进后出 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
思路:利用栈的先进后出的特点,将链表前一半元素依次进栈,然后将栈中元素出栈,与链表的后半元素依次进行比较。
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 ...
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: 计算斐波拉契数列可用循环实现
函数调用时,系统要用栈保存必要的信息;递归次数过多容易造成栈溢出
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10