[数据结构]栈的学习
一 栈的定义
栈是一种限定的线性表
比喻:装羽毛球的盒子,
二 栈抽象数据类型
三 栈的分类
1 顺序栈 2多栈共享技术 3 链栈 4 多栈运算
3.1,顺序栈的定义:
自己的理解:不是动态的,比较死;
3.1.1进栈
注意点:要判断是否满.
比喻:如果羽毛球盒子满了怎么可能在装?!
3.1.2出栈
注意:要判断是是否为空
比喻:如果羽毛球盒子空了,还怎么拿羽毛球?1!
3.1.3 进栈和出栈示意图:
比喻:进栈如同装羽毛球,出栈如同拿羽毛球.
3.1.4读栈顶元素
思考:说明读栈顶元素和退栈的处理有什么异同? *****
答:读栈顶元素没有指针的移动,而退栈有指针的移动;
比喻:拿一个羽毛球就不需要移动,而你想拿多个当然要移动了;
3.2 多栈共享技术(2栈)
3.3 链栈
理解;联系到链表.
比喻:1 链子 2 糖葫芦(不能从你手拿的那方出) 3 暂时没有想到
3.3.1进栈
注意:同样也要判断是否满*****
3.3.2 出栈
注意:出栈同样也要判断是否为空
3.4 多栈运算
四 栈的应用
4.1 括号匹配问题
算法理解:当遇到左括号时进栈,遇到右括号时比较;如( { [ ]} )
4.1.1 不合法情况:
(1) 右括号找不到栈顶左括号匹配 如 1 ({ ] ) 2 [ ] )
(2) 当读完序列时,还有左括号在栈中.如 1 {[ ] 2 [ [ ( )
4.1.2 合法的情况:读完序列时栈也同时空