数据结构-04栈与队列

1、第四章堆栈和队列，4.1堆栈4.1.1堆栈的结构特征和操作4.1.2实现堆栈的显示和操作4.2堆栈的应用实例4.3队列4.3.1队列的结构特征和操作4.3.2实现队列的显示和操作4.4队列的应用实例，4.1堆栈、3.3 在此，将允许插入和删除的一侧称为“堆叠顶部”，将另一侧称为“堆叠底部”。 数据元素数为零的堆栈是“空堆栈”堆栈是“先入先出(LIFO )”的线性表。 例如：堆栈中的元素按(a1，a2，an )的顺序被堆栈，堆栈的第一个元素是an .a1，a2，an，堆栈的第一个元素是堆栈元素，那么，an，a2，a1，应用程序中常用的堆栈堆栈进行(s ) :判断堆栈s是否为空，如果为空则返回“T

2、RUE”，否则返回“FALSE”，4.1.2堆栈的基本操作，Push(/初始分配的最大空间量Const STACKINCREMENT=10； /互补空间量Typedef struct SElemType *elem； /记忆空间的基地址int top /堆栈顶部指针int satcksize； /当前分配的最大容量int incrementsize /约定的互补空间Sqstack； /stacksize和incrementsize是以SElemType为单位，对于以c编写的语言，通常以top=-1表示顺序堆栈为空。 1 .顺序堆栈、基本操作的实现初始化操作voidsinitstack _ sq

3、 (sqstack )/init stack _ sq复杂度为O(1)，堆栈要素bool GetTop_Sq(SqStack S，smeletype )，1.0 S.top S.top，将新的要素压入堆栈的操作： void Push_Sq(SqStack /Push_Sq，1 .顺序堆栈，例如：已知顺序堆栈s，如图所示，x=“数据结构”为push(S，x ) S.top，1 .顺序删除堆栈顶层要素的操作bool Pop_Sq(SqStack /Pop_Sq复杂度为O(1)，1 .顺序堆栈，执行后，c语言，数据结构，S.top，S.top，例：堆栈e=“数据结构”，序列堆栈在使用时受到最大容量的

4、限制，如果当前堆栈满，需要添加新的数据元素，则需要添加存储空间。 这是使用顺序堆栈时的弱点之一。 堆栈的另一存储结构链接堆栈以链表结构表示，并且是实现的堆栈。 链路堆栈的节点结构与链表的节点结构相同，包括数据域和指针域两部分。 在此，将存储数据要素自身的域称为数据域，将存储直接后续的要素的存储位置的域称为指针域。 链堆栈中的多个节点用指针链接，并设置指向堆栈顶部元素的指针堆栈顶部的指针。 2 .链堆栈、数据、下一个、堆栈顶部、堆栈底部、2 .链堆栈、typedefstructlnode elemtype数据； 结构节点*下一步； LNode、* LinkList； 类型链路列表链路堆栈； 如果

5、s是LinkStack型的变量，则s是堆栈指针。 如果S=NULL，则该链堆栈为空，堆栈的链存储描述：s，链堆栈的基本操作void InitStack_L(LinkStack /修改堆栈顶部指针) push_L，2 .链堆栈，2 .s，SS，bool pop _ l (链接堆栈)/pop _ l，2 .链堆栈，2 .链堆栈，p，e=3，4.2堆栈的应用实例，示例4.1 :将非负十进制数转换为八进制数的问题。 根据十进制数和八进制数之间的变换关系，对应的八进制数以十进制数除以八的逆顺序，可根据堆栈LIFO的特征，在堆栈上实现。 语音转换(intn ) /init stack (s ) while

6、 (n ) push (s，N%8)； N=N/8； /while While (！ 堆栈空间(s，e )； cout0 /knapsack，例4.4式评价。表达式：5360操作数运算符操作数：5360简单变量|表达式有三种不同的表达方法：前缀表达方法： OP S1 S2中的后缀表达方法： S1 S2 OP，4.2堆栈的应用实例前缀表达式： *ab*-c/def b (c-d/e)*f后缀表达式： ab*cde/-f*，前缀表达式和后缀表达式包含特定的运算顺序，但前缀表达式的运算顺序通常需要用括弧来确定。 像后缀表达式一样，每个运算符及其前面出现的两个操作数构成最小表达式。后缀表达式的计算、4

7、.2堆栈的应用例子、后缀表达式是没有括号的表达式，计算时不需要考虑运算符的优先级，操作数堆栈后缀表达式计算时读取的方向只需设定从左到右后缀表达式的计算顺序，1 .建立操作数堆栈，初始化为空的2 .式被读取从左向右读取表达式的运算单元3 .如果是操作数，直接进入堆栈4 .如果是运算符，从操作数堆栈中取出两个操作数进行运算，并将结果压入堆栈。 5 .重复2到4，直到读取表达式，最后一个堆栈顶元素得到计算结果。 例如： ABC/D-，空操作数堆栈，读a，读b，a，读c，“/，读d，”，读“，A B/C-D，”，计算的结果，请读4.2堆栈的应用例。 读教材p12算法4.4，把词缀式转换为词缀式(规则)

8、，作出4.2堆栈的应用例，1 .运算符堆栈2 .公式的终止符和运算符堆栈底“#”3 .把公式(1)从左向右读的话，就变成了操作数(2)读的是(。 如果读入的是“”，则将堆栈顶部运算符输出为后缀式，直到“”(4)弹出为止读入非括号运算符时，与堆栈顶部运算符进行比较：比堆栈顶部运算符的优先数高时，直接放入堆栈的其他情况下，是堆栈顶部运算符4 .如果表达式尚未读完，则重复3。如果堆栈不为空，则堆栈中的运算符将传递给后缀表达式，直到堆栈为空。将a (b (c/d-e)*f #转换为后缀式，4.2堆栈的应用例，a，a，#，读取的操作单元，后缀式， 运算符堆栈程序代码参考教材p13算法4.5，示例4.5堆

9、栈对递归函数的应用递归函数的执行是函数自身的调用，而调用函数和被调用函数之间的链接和信息交换通常是由编译系统通过堆栈来实现的。 堆栈中存储的信息主要是返回地址。调用函数时所有局部变量的值，以及值传递格式参数的值所有参照参数和常数参照参数的定义。 4.2堆栈应用实例，递归解决问题的一般步骤：定义递归执行部分，以确定递归终止条件。 4.2堆栈的应用例子，函数Ackerman的定义如下： 4.2堆栈的应用例子，n和y都不等于0的情况下，该函数的执行是递归调用的过程，看a (3，2，1 )计算过程中堆栈的一部分内容的变化。 4.2堆栈的应用例：3，2，1，3，2，0，2，1，2，1，0，0，2，1，2

10、，2，2，2，0，0，0，1，1，1，1，0，0，0 int xval； int yval； ElemType； 4.2堆栈的应用实例，int Aackerman (int n、int x、int y) /堆栈s中的Aackerman函数的值InitStack(S )； e.nval=n； e.xval=x； e.yval=y； 推式(s，e ) do 获取(s，e )； PS (e.nval！=0/if /while (！ StackEmpty(S) /Aackerman，4.2堆栈的应用例，n皇后问题(递归后退)是将n人的皇后放在NN的棋盘上，皇后的行驶范围为上下、左、右、左上、右上、左下、右下8个方向，将任意2个皇后放在同一行寻求安置n位女王的方法。 N=4、第一皇后、第二皇后、不能继续走，追溯到第二皇后的位置，n皇后问题，n皇后问题，n皇后问题，第二皇后的位置，寻找第三皇后的位置，第四皇后的位置，、第四皇后的位置， 追溯第三皇后的位置，n皇后问题，寻找第三皇后的位置，、的位置， 没有追溯到第二女王，第二女王找不到新的位置，第四女王找不到新的位置，第三女王找不到新的位置，第三女王找不到新的位置，第