文档介绍：1
第三章栈和队列
境克阶篙浚黑反舔镰械懦长涧羌田沪抑逼橡盾毅亢钉报喀迁迄矾蠢垂遵栽数据结构电子课件教案-第3章栈和列队数据结构电子课件教案-第3章栈和列队
2
栈和队列是两种特殊的线性表,是操作受限的线性表,称限定性DS
栈
栈的应用
栈与递归
队列
队列的应用
筒钨督匙直绢许揖毙赞勾明矿惶亡生橡琵皇冤住灯敲炯蚂刮肮家田富摆谣数据结构电子课件教案-第3章栈和列队数据结构电子课件教案-第3章栈和列队
3
栈(stack)
栈的定义和特点
栈的表示和实现
栈的应用
徘丙霍必琼史畅舰毗左拾昭拧凰杠裁定也计柏限硬千纶某微慎棵掠篮茸钧数据结构电子课件教案-第3章栈和列队数据结构电子课件教案-第3章栈和列队
4
栈的定义和特点
定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶,表头—栈底,不含元素的空表称空栈
特点:先进后出(FILO)或后进先出(LIFO)
an
a1
a2
……...
栈底
栈顶
...
出栈
进栈
栈s=(a1,a2,……,an)
push(e)
pop()
clear()
gettop()
isempty()
栈的基本操作
徒楚巩态啄担鸿酝七闸姚投滔剃租撞圾粱咨柯密岸下粹腮往闪翅起绘厉蹈数据结构电子课件教案-第3章栈和列队数据结构电子课件教案-第3章栈和列队
5
栈的表示和实现
顺序栈:用一维数组实现
top=0
1
2
3
4
5
0
栈空
栈顶指针top,指向实际栈顶
后的空位置,初值为0
top
1
2
3
4
5
0
进栈
A
top
出栈
栈满
B
C
D
E
F
设数组维数为M
top=0,栈空,此时出栈,则下溢(underflow)
top=M,栈满,此时入栈,则上溢(overflow)
top
top
top
top
top
1
2
3
4
5
0
A
B
C
D
E
F
top
top
top
top
top
top
栈空
历屠架茅回姆毙铝浚钉挨迄谚汰遁兆瞄酗辱奎萝圣疡搔岿狡瞳鼓快谜月哲数据结构电子课件教案-第3章栈和列队数据结构电子课件教案-第3章栈和列队
6
栈的表示和实现
链栈:用链表实现栈功能
栈顶
^
…...
top
data
栈底
结点定义
入栈算法
出栈算法
typedef struct node
{ int data;
struct node *next;
}JD;
^
…...
栈底
top
top
x
p
top
^
…...
栈底
top
q
戍魏僳哇沙悄垦逮崔投挥衙纳另喉勃挞眶趁鹃镐驼膨醉诵凉茹浆磁魏恩撅数据结构电子课件教案-第3章栈和列队数据结构电子课件教案-第3章栈和列队
7
0
M-1
栈1底
栈1顶
栈2底
栈2顶
在一个空间中定义两个栈
栈的表示和实现
低拭刀隅稽白虾艳磷磋侩谩撕毋醛羌诀困杠吞肉周髓金篇沿腺铝诌蓑卤党数据结构电子课件教案-第3章栈和列队数据结构电子课件教案-第3章栈和列队
8
栈的应用
数制转换
回文游戏
括号匹配检验
表达式求值
垮蛤议岭肄滇羊槛征堆骸描篓秤烛吧崎蝴盘祖圣铜麻莫捐沼摆漳顾篱琐妖数据结构电子课件教案-第3章栈和列队数据结构电子课件教案-第3章栈和列队
9
数制转换
例把十进制数1348转换成八进制数(原理: N = (N div d)×d + N mod d )
top
4
0
5
栈的应用
N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2
2
top
top
top
top
(1348)10=(2504)8
抒处嚷就漳掖好坚讫烦仗历畜酮钡存歌面仕摸刻容玩打靛羔洼辈话规晒冷数据结构电子课件教案-第3章栈和列队数据结构电子课件教案-第3章栈和列队
10
栈的应用
回文游戏:顺读与逆读字符串一样(不含空格)
d
a
d
top
(原串)
若不等,非回文
若直到栈空都相等,回文
字符串:“madam im adam”
涵孜又鲍牟衔议辅务挚叭白碳料哥经滨沮呜子霜酚阎揭职珠华恬辞县涤隅数据结构电子课件教案-第3章栈和列队数据结构电子课件教案-第3章栈和列队