第4章栈和队列 章线和队列 计算机教研宦 第1页 2021/2/19
Data Structure 数据结构—— 第4章栈和队列 胡建华 2021/2/19 计算机教研室 第 1 页 第 4 章 栈和队列
r4.1栈 章线和队列 计算机教研宦 第2页 2021/2/19
Data Structure 数据结构—— 第4章栈和队列 胡建华 2021/2/19 计算机教研室 第 2 页 4.1 栈
◎4.11栈的结构特点和操作 ·栈(tack)是限制在表的一端进行插入和删除 运算的线性表。通常称插入、删除的这一端为 栈顶(Top),另一端为栈底( Bottom)。当表中 没有元素时称为空栈 假设栈S=(a1,a2 ,a,。。 an),则a称为栈底元 素,an为栈顶元素。栈中元素按a1,a2, 3,…a2的次序进栈,退栈的第一个元素应为 栈顶元素。换句话说,栈的修改是按后进先出 章线和队列 的原则进行的。因此,栈称为后进先出表 (LIFO) 计算机教研宦 第3页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第3页 4.1.1 栈的结构特点和操作 • 栈(Stack)是限制在表的一端进行插入和删除 运算的线性表。通常称插入、删除的这一端为 栈顶(Top)，另一端为栈底(Bottom)。当表中 没有元素时称为空栈。 • 假设栈S=(a1，a2，a3，…an)，则a1称为栈底元 素，an为栈顶元素。栈中元素按a1，a2， a3，…an的次序进栈，退栈的第一个元素应为 栈顶元素。换句话说，栈的修改是按后进先出 的原则进行的。因此，栈称为后进先出表 （LIFO）
由栈的定义可以发现,栈有如下特点 1、进、出都在同一端进行; 2、先进去的后出来。 栈顶 a a n ●。 章线和队列 2 栈底 a1 计算机教研宦 第4页 2021/2/19
Data Structure 数据结构—— 第4章栈和队列 胡建华 2021/2/19 计算机教研室 第 4 页 由栈的定义可以发现 ，栈有如下特点： 1 、 进 、出都在同一端进行； 2 、先进去的后出来 。 a 1 a 2 a n - 1 a n …… 栈顶 栈底
@4.1.2栈的表示和操作的实现 顺序栈(参见程序 Stack. cpp) 链栈 章线和队列 计算机教研宦 第5页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第5页 4.1.2 栈的表示和操作的实现 • 顺序栈（参见程序Stack.cpp) • 链栈
黑42栈的应用举例 章线和队列 计算机教研宦 第6页 2021/2/19
Data Structure 数据结构—— 第4章栈和队列 胡建华 2021/2/19 计算机教研室 第 6 页 4.2 栈的应用举例
@例41数制转换 ·十进制数N和其他d进制数的转换是计算机实现计算的 基本问题,其解决方法很多,其中一个简单算法基于 下列原理: N=( n diy d)×d+ n mod d (其中:div为整除运算,mod为求余运算) 例如:(1348)10=(2504)8,其运算过程如下: n div 8 n mod 8 1348 168 168 21 章线和队列 21 2 4052 计算机教研宦 第7页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第7页 例4.1 数制转换 • 十进制数N和其他d进制数的转换是计算机实现计算的 基本问题，其解决方法很多，其中一个简单算法基于 下列原理： N = (N div d)×d + N mod d (其中：div 为整除运算，mod 为求余运算） 例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2
@算法4.1数制转换问题 void conversion(( ∥对于输入的任意一个非负十进制整数,打印输出与其等值的八进制数 nitstack(S);∥构造空栈 cin>>N; while(Ni Push(s,N%8);∥余数”入栈 N=N/8;∥“商”继续运算 3/while Whle( StackEmpty){∥和“求余”所得相逆的顺序输出八进制 章线和队列 的各位数 Pop(s, e) cout<<e: while 第8页
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第8页 算法 4.1 数制转换问题 void conversion () { // 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 InitStack(S); // 构造空栈 cin>>N; while (N) { Push(S, N % 8); // “余数”入栈 N = N/8; // “商”继续运算 }//while while (!StackEmpty) { // 和“求余”所得相逆的顺序输出八进制 的各位数 Pop(S,e); cout< <e； }//while } // conversion
@例42括号匹配的检验 假设表达式中允许包含两种括号:圆括号和方括号 其嵌套的顺序随意,即([]()或[( 等为正确的格式,[(])或([())或()])均为 不正确的格式。检验括号是否匹配的方法可用″期待 的急迫程度”这个概念来描述。例如考虑下列括号序 列: [([][])] 12345678 分析可能出现的不匹配的情况: 意1.到来的右括弧非是所“期待”的; 2.到来的是“不速之客 双3.直到结束,也没有到来所“期待”的。 计算机教研宦 第9页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第9页 例4.2 括号匹配的检验 • 假设表达式中允许包含两种括号：圆括号和方括号， 其嵌套的顺序随意，即([ ］( ))或［(［ ］［ ］)］ 等为正确的格式，［( ］)或(［( ) )或 (( )])均为 不正确的格式。检验括号是否匹配的方法可用"期待 的急迫程度"这个概念来描述。例如考虑下列括号序 列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 • 分析可能出现的不匹配的情况: 1. 到来的右括弧非是所“期待”的; 2. 到来的是“不速之客”; 3. 直到结束，也没有到来所“期待”的
@栈和递归函数的关系 递归:函数直接或间接的调用自身叫 实现:建立递归工作栈 ·例递归的执行情况分析 void print(int w) i int i if(w!=0) print(w-1) for(i=l; K<=w; ++i) printf( o3d,, w); 章线和队列 printf(/n” 计算机教研宦 第10页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第10页 栈和递归函数的关系 • 递归：函数直接或间接的调用自身叫~ • 实现：建立递归工作栈 • 例 递归的执行情况分析 void print(int w) { int i; if ( w!=0) { print(w-1); for(i=1;i<=w;++i) printf(“%3d,”,w); printf(“/n”); } }
