1、4.1堆栈的概念及其运算 堆栈（a1, a2, , an）栈顶栈顶栈底栈底abc入栈入栈出栈出栈栈底栈底栈顶栈顶栈顶栈顶栈顶栈顶4.1堆栈的概念及其运算4.1堆栈的概念及其运算栈底栈底栈顶栈顶ab栈顶栈顶c栈顶栈顶 情况情况1：出栈序列：出栈序列：c出栈序列：出栈序列：c、b出栈序列：出栈序列：c、b、a栈底栈底栈顶栈顶ab栈顶栈顶 情况情况2：出栈序列：出栈序列：b4.1堆栈的概念及其运算栈底栈底a出栈序列：出栈序列：b出栈序列：出栈序列：b、c出栈序列：出栈序列： b、 c、ac栈顶栈顶栈顶栈顶注意：注意：栈只是对表插入和删除操作的位置进行了限栈只是对表插入和删除操作的位置进行了限制，并没
2、有限定插入和删除操作进行的时间。制，并没有限定插入和删除操作进行的时间。 情况情况2：4.1堆栈的概念及其运算4.1堆栈的概念及其运算 0 1 2 3 4 5 6 7 8a1确定用数组的哪一端表示栈底。确定用数组的哪一端表示栈底。附设指针附设指针top指示栈顶元素在数组中的位置。指示栈顶元素在数组中的位置。 top4.2堆栈的顺序存储结构出栈：出栈：top减减1进栈：进栈：top加加1栈空：栈空：top= - -1 0 1 2 3 4 5 6 7 8a1topa2topa3top栈满：栈满：top= MAX_SIZE4.2堆栈的顺序存储结构4.2堆栈的顺序存储结构4.2堆栈的顺序存储结构4.2
3、堆栈的顺序存储结构a1 a2 aitop10 1 2 S-1top2bj b2 b1栈栈1底底栈栈2底底4.2堆栈的顺序存储结构top1= -1a1 a2 aitop10 1 2 S-1top2bj b2 b1top14.2堆栈的顺序存储结构top1= -1a1 a2 aitop10 1 2 S-1top2bj b2 b1top2top2= MaxSize4.2堆栈的顺序存储结构top1= -1a1 a2 aitop10 1 2 S-1top2bj b2 b1top2= MaxSizetop2= top1+14.2堆栈的顺序存储结构4.2堆栈的顺序存储结构4.2堆栈的顺序存储结构heada1a
4、2anai4.3堆栈的链式存储结构栈顶栈顶栈底栈底topanan-1a1heada1a2anaitopa1an-1an栈顶栈顶栈底栈底4.3堆栈的链式存储结构4.3堆栈的链式存储结构4.3堆栈的链式存储结构 4.4堆栈的应用递归 4.4堆栈的应用递归4.4堆栈的应用递归-*=时时当当时时当当 )!1( 1!n1n1nnn4.4堆栈的应用递归4.4堆栈的应用递归 4.4堆栈的应用递归4.4堆栈的应用递归4.4堆栈的应用递归Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move (A,C)Move (A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move (C,B)Hanio(1,C,A,B)Move (A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move (B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move (A,C)Hanio(2,B,A,C)Move (B,A)Hanio(1,A,B,C)结束结束4.4堆栈的应用4.4堆栈的应用4.4堆栈的应用4.4堆栈的应用4.4堆栈的应用运算优先级运算优先级()#(#=当前运算符栈顶运算符4.4堆栈的应用4.4堆栈的应用
