教察 栈和队列 程序设计—数据结构 基本概念及应用 目录 3.1栈的基本概念 2 3.1.1栈的抽象数据类型定义 … 2 3.1.2顺序栈」 3 3.1.3链栈4 3.2栈的应用 4 3.2.1数制转换：将十进制数N转换成其他d进制数 ..4 3.2.2括号匹配的检验 3.2.3行输入处理程序 4 3.2.4迷宫求解. .5 3.2.5表达式求值 5 3.3栈与递归的实现… 6 3.4队列的基本概念 3.4.1队列的抽象数据类型定义 6 6 3.4.2链队列.… 3.4.3循环队列. 7 3.5队列与栈的应用 8 3.5.1离散事件模拟 9 .9 文档编号 完成时间 完成人张昱 修改时间 第1页
程序设计——数据结构 栈和队列 基本概念及应用 文档编号 完 成 人 张 昱 完成时间 修改时间 第 1 页 目 录 3.1 栈的基本概念...........................................................................................................2 3.1.1 栈的抽象数据类型定义....................................................................................2 3.1.2 顺序栈............................................................................................................3 3.1.3 链栈................................................................................................................4 3.2 栈的应用..................................................................................................................4 3.2.1 数制转换：将十进制数N转换成其他d进制数...................................................4 3.2.2 括号匹配的检验..............................................................................................4 3.2.3 行输入处理程序..............................................................................................4 3.2.4 迷宫求解.........................................................................................................5 3.2.5 表达式求值.....................................................................................................5 3.3 栈与递归的实现........................................................................................................6 3.4 队列的基本概念........................................................................................................6 3.4.1 队列的抽象数据类型定义................................................................................6 3.4.2 链队列............................................................................................................7 3.4.3 循环队列.........................................................................................................8 3.5 队列与栈的应用........................................................................................................9 3.5.1 离散事件模拟..................................................................................................9
敦案 栈和队列 程序设计—数据结构 基本概念及应用 第3章栈和队列 3.1栈的基本概念 3.1.1栈的抽象数据类型定义 1、栈的逻辑特征 1)限定在表尾进行插入或删除操作的线性表： 2)栈顶一一表尾端：栈底一一表头端 3)后进先出的线性表 2、抽象数据类型的定义 ADT Stack 数据对象：D={ala∈ElemSet,.i=l,2,…,n,n≥0} 数据关系：R={R1},R1={a-l,a>a-1,a∈D,i=2,3,…,n} 基本操作： InitStack(&S 操作结果：构造一个空的栈S DestroyStack(&S) 初始条件：栈S己存在 操作结果：销毁栈S ClearStack(&S 初始条件：栈S已存在 操作结果：将栈S重置为空栈 StackEmpty(S) 初始条件：栈S已存在 操作结果：若S为空栈，则返回TRUE,否则返回FALSE StackLength(S) 初始条件：栈S已存在 操作结果：返回栈S中数据元素的个数 GetTop(S,&e) 初始条件：栈S已存在且非空 操作结果：用e返回S中栈顶元素 Push(&S,e) 初始条件：栈S已存在 操作结果：插入元素e为新的栈顶元素 Pop(&S,&e) 初始条件：栈S已存在且非空 操作结果：删除S的栈顶元素，并用e返回其值 StackTraverse(S,visit()) 初始条件：栈S已存在且非空 操作结果：从栈底到栈顶依次对S的每个数据元素调用函数vist()。一 旦visit()失败，则操作失败 ADT Stack 思考：栈的取元素、插入、删除操作与线性表的相应操作有何区别，为什么？ 文档编号 完成时间 完成人张昱 修改时间 第2页
程序设计——数据结构 栈和队列 基本概念及应用 文档编号 完 成 人 张 昱 完成时间 修改时间 第 2 页 第3章 栈和队列 3.1 栈的基本概念 3.1.1 栈的抽象数据类型定义 1、栈的逻辑特征 1）限定在表尾进行插入或删除操作的线性表； 2）栈顶——表尾端；栈底——表头端 3）后进先出的线性表 2、抽象数据类型的定义 ADT Stack{ 数据对象：D={ai |ai∈ElemSet, i=1,2,…,n, n≥0} 数据关系：R={R1},R1={|ai-1,ai∈D, i=2,3,…,n } 基本操作： InitStack( &S ) 操作结果：构造一个空的栈 S DestroyStack( &S ) 初始条件：栈 S 已存在 操作结果：销毁栈 S ClearStack( &S ) 初始条件：栈 S 已存在 操作结果：将栈 S 重置为空栈 StackEmpty( S ) 初始条件：栈 S 已存在 操作结果：若 S 为空栈，则返回 TRUE，否则返回 FALSE StackLength( S ) 初始条件：栈 S 已存在 操作结果：返回栈 S 中数据元素的个数 GetTop( S, &e ) 初始条件：栈 S 已存在且非空 操作结果：用 e 返回 S 中栈顶元素 Push( &S, e ) 初始条件：栈 S 已存在 操作结果：插入元素 e 为新的栈顶元素 Pop( &S, &e ) 初始条件：栈 S 已存在且非空 操作结果：删除 S 的栈顶元素，并用 e 返回其值 StackTraverse( S, visit( ) ) 初始条件：栈 S 已存在且非空 操作结果：从栈底到栈顶依次对 S 的每个数据元素调用函数 visit( )。一 旦 visit( )失败，则操作失败 }ADT Stack 思考：栈的取元素、插入、删除操作与线性表的相应操作有何区别，为什么？
教黎 栈和队列 程序设计—数据结构 基本概念及应用 3.1.2顺序栈 1、增量式顺序栈的定义 #define STACK INIT_SIZE 100 体存储空间的初始分配量*/ #define STACKINCREMENT 10 体存储空间的分配增量*/ typedef struct ElemType *base; /*栈底指针 ElemType *top, /*栈顶指针（栈顶元素的下一个位置）/ int stacksize; 体当前分配的存储容量制 SqStack; 1)和顺序表一样采用增量式的空间分配： 2)操作和栈顶相关： 插入操作（入栈）：将待插元素插入到栈顶元素的下一个位置： 删除操作（出栈）：删除栈顶元素： 取元素操作：取栈顶元素的值。 各操作的操作位置与栈顶元素的位置或其下一个位置相关，希望在O(1)时间内能获取 操作位置，故可设置专门的栈顶指针top。 3)约定：top指向栈顶元素的下一个位置（便于表示空栈）。 4)栈顶的初始化：S.top=S.base(在上述3)约定下的空栈形式) 5)栈空：S.base=S.top,栈满：S.top-S.base>=S.stacksize 6)入栈：S.top+=e,出栈：e=-S.top 注意：4)，5)，6)步受3)制约。约定不同，相应的判定和处理也不一样。 如假设top就指向栈顶元素，此时4)，5)，6)如何？ 2、取栈顶元素GetTop_Sq 1)算法设计 参数：顺序栈S、取得的栈顶元素&e 分析：由于top指向栈顶元素的下一个位置，因此实际的栈顶元素的位置应是top-1: 栈非空时，此操作有效。 算法1 Status GetTop Sq(SqStack S,Elem Type &e){ 体判断栈是否为空*/ if(S.base ==S.top)return ERROR; e=*(S.top-1); return OK: } 3、入栈操作Push_Sq 1)算法设计 参数：顺序栈&S、插入元素e 分析：插入位置为栈顶元素的下一个，无须判断位置的合法性： 上溢即栈满的条件需要判断，由于是增量式分配，故栈满时需要重新申请空间； 算法2 Status Push_Sq(SqStack &S,ElemType e ) 体判断栈是否为满*/ if (S.top-S.base >=S.stacksize ) 体栈满，追加空间/ 文档编号 完成时间 完成人张昱 修改时间 第3页
程序设计——数据结构 栈和队列 基本概念及应用 文档编号 完 成 人 张 昱 完成时间 修改时间 第 3 页 3.1.2 顺序栈 1、增量式顺序栈的定义 #define STACK_INIT_SIZE 100 /* 存储空间的初始分配量 */ #define STACKINCREMENT 10 /* 存储空间的分配增量 */ typedef struct{ ElemType *base; /* 栈底指针 */ ElemType *top; /* 栈顶指针(栈顶元素的下一个位置) */ int stacksize; /* 当前分配的存储容量 */ }SqStack; 1）和顺序表一样采用增量式的空间分配； 2）操作和栈顶相关： 插入操作（入栈）：将待插元素插入到栈顶元素的下一个位置； 删除操作（出栈）：删除栈顶元素； 取元素操作：取栈顶元素的值。 各操作的操作位置与栈顶元素的位置或其下一个位置相关，希望在 O(1)时间内能获取 操作位置，故可设置专门的栈顶指针 top。 3）约定：top 指向栈顶元素的下一个位置（便于表示空栈）。 4）栈顶的初始化：S.top = S.base(在上述 3)约定下的空栈形式)， 5）栈空：S.base == S.top，栈满：S.top - S.base >= S.stacksize 6）入栈：*S.top ++ = e，出栈：e = *--S.top 注意：4), 5), 6)步受 3)制约。约定不同，相应的判定和处理也不一样。 如假设 top 就指向栈顶元素，此时 4),5),6)如何？ 2、取栈顶元素 GetTop_Sq 1) 算法设计 参数：顺序栈 S、取得的栈顶元素&e 分析：由于 top 指向栈顶元素的下一个位置，因此实际的栈顶元素的位置应是 top -1； 栈非空时，此操作有效。 算法 1 Status GetTop_Sq(SqStack S, ElemType &e){ /* 判断栈是否为空 */ if ( S.base == S.top) return ERROR; e = *( S.top -1); return OK; } 3、入栈操作 Push_Sq 1) 算法设计 参数：顺序栈&S、插入元素 e 分析：插入位置为栈顶元素的下一个，无须判断位置的合法性； 上溢即栈满的条件需要判断，由于是增量式分配，故栈满时需要重新申请空间; 算法 2 Status Push_Sq( SqStack &S, ElemType e ){ /* 判断栈是否为满 */ if ( S.top – S.base >= S.stacksize ){ /* 栈满，追加空间 */
敦黎 栈和队列 程序设计—数据结构 基本概念及应用 S.base =ElemType *realloc(S.base. (S.stacksize STACKINCREMENT )sizeof(ElemType)); if(S.base NULL exit(OVERFLOW); S.top=S.base +S.stacksize; S.stacksize +=STACKINCREMENT. *S.top++=e; return OK: 2)算法分析—时间Tn)=O1) 4、出栈操作Pop_Sq 1)算法设计 参数：顺序栈&S、删除的栈顶元素&e 分析：在栈非空时，删除栈顶元素 算法3 Status Pop_Sq(SqStack &S,ElemType &e) 体判断栈是否为空/ if(S.base==S.top)return ERROR; e=*(--S.top); /体注意与Get Top()的区别*/ return OK; } 2)算法分析一时间T(n)=O(1) 3.1.3链栈 与链表类似，只是链表的头指针即为栈顶指针。因其操作均在栈顶进行，故可以不引入头 结点。 思考：在链栈下的入栈、出栈以及取栈顶元素的操作的算法如何写？ 3.2栈的应用 3.2.1数制转换：将十进制数N转换成其他d进制数 算法思想：N=(N divd)×d+N mod d 1)将N%d的结果保存， 2)N=N/d, 3)若N=0结束，否则继续1)。 保存的余数从先到后依次表示转换后的d进制数的低位到高位，而输出是由高 位到低位的，因此必须定义先进后出的线性表一一栈来保存：当全部的余数求 出后，通过逐个出栈输出d进制数。 3.2.2括号匹配的检验 算法思想：从左至右扫描表达式，遇左括号入栈，遇右括号与栈顶元素比较：若左右括号 匹配，则继续扫描：否则说明不匹配，结束。在上述操作中，若栈为空，或扫 描结束后栈不为空，均说明不匹配。 3.2.3行输入处理程序 文档编号 完成时间 完成人张昱 修改时间 第4页
程序设计——数据结构 栈和队列 基本概念及应用 文档编号 完 成 人 张 昱 完成时间 修改时间 第 4 页 S.base = ( ElemType * ) realloc( S.base, ( S.stacksize + STACKINCREMENT ) * sizeof(ElemType) ); if ( S.base == NULL ) exit(OVERFLOW); S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; return OK; } 2) 算法分析——时间 T(n) = O(1) 4、出栈操作 Pop_Sq 1) 算法设计 参数：顺序栈&S、删除的栈顶元素&e 分析：在栈非空时，删除栈顶元素 算法 3 Status Pop_Sq( SqStack &S, ElemType &e){ /* 判断栈是否为空 */ if (S.base == S.top) return ERROR; e = *( --S.top); /* 注意与 GetTop( )的区别 */ return OK; } 2) 算法分析——时间 T(n) = O(1) 3.1.3 链栈 与链表类似，只是链表的头指针即为栈顶指针。因其操作均在栈顶进行，故可以不引入头 结点。 思考：在链栈下的入栈、出栈以及取栈顶元素的操作的算法如何写？ 3.2 栈的应用 3.2.1 数制转换：将十进制数 N 转换成其他 d 进制数 算法思想：N = ( N div d )×d + N mod d 1）将 N%d 的结果保存， 2）N=N/d， 3）若 N==0 结束，否则继续 1）。 保存的余数从先到后依次表示转换后的 d 进制数的低位到高位，而输出是由高 位到低位的，因此必须定义先进后出的线性表——栈来保存；当全部的余数求 出后，通过逐个出栈输出 d 进制数。 3.2.2 括号匹配的检验 算法思想：从左至右扫描表达式，遇左括号入栈，遇右括号与栈顶元素比较：若左右括号 匹配，则继续扫描；否则说明不匹配，结束。在上述操作中，若栈为空，或扫 描结束后栈不为空，均说明不匹配。 3.2.3 行输入处理程序
教案 栈和队列 程序设计—数据结构 基本概念及应用 处理规则：遇‘#’退一格：遇‘@’退一行 算法思想：引入栈，保存终端输入的一行字符（逐行处理）： 遇‘#’退一格一一出栈一次 遇‘@’退一行一一清栈 步骤： 1)初始化栈S 2)读入字符ch 3)ch!=EOF 3.1)ch!=EOF&&ch!='In' 3.1.1)ch为‘#'：Pop(S,c),转3.1.4) 3.1.2)ch为‘@'：ClearStack(S),转3.1.4) 3.1.3)ch为其他：Push(S,ch),转3.1.4) 3.1.4)再读入字符ch,继续3.1) 3.2)处理完一行，清空栈 3.3)如chl=EOF,读入字符ch,继续3) 3.2.4迷宫求解 问题：找从“入口”到“出口”的路径（所经过的通道方块） 分析： 1)方块的表示一一坐标，当前的状态（障碍、未走的通路、已走的通路）： 2)已走的路径： A.路径中各方块的位置及在路径中的序号： B.从各方块出发已探索的方向，注意不能重复（可约定按东、南、西、北的方向 顺次探索)： C.从当前方块无路可走时，将已走路径回退一个方块，继续探索其他未走的方向 栈一一存储己走的通道块 3.2.5表达式求值 1、问题描述 ·只包含+，，*，/四个双目运算符，且算符本身不具有二义性： ·三个运算规则→运算符优先关系（考虑算符本身的优先级和结合性）： ·只有'(==)，#==#： ·假设输入的是一个合法的表达式。 2、算法思想 引入OPTR和OPND两个栈 初始：OPTR有一个元素#，OPND为空 读入一字符c c=#:return(GetTop(OPND)) c非运算符：Push(OPND,c) c运算符：t=GetTop(OPTR),比较t和c的优先关系 tc:Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a); x=Operate(a,theta,b);Push(OPND,x); 继续读入字符处理。 文档编号 完成时间 完成人张昱 修改时间 第5页
程序设计——数据结构 栈和队列 基本概念及应用 文档编号 完 成 人 张 昱 完成时间 修改时间 第 5 页 处理规则：遇‘#’退一格；遇‘@’退一行 算法思想：引入栈，保存终端输入的一行字符（逐行处理）； 遇‘#’退一格——出栈一次 遇‘@’退一行——清栈 步骤： 1）初始化栈 S 2）读入字符 ch 3）ch!=EOF 3.1) ch!=EOF && ch!=’\n’ 3.1.1）ch 为‘#’：Pop(S, c), 转 3.1.4) 3.1.2）ch 为‘@’： ClearStack (S) , 转 3.1.4) 3.1.3）ch 为其他： Push (S, ch) , 转 3.1.4) 3.1.4）再读入字符 ch，继续 3.1) 3.2) 处理完一行，清空栈 3.3) 如 ch!=EOF，读入字符 ch，继续 3) 3.2.4 迷宫求解 问题：找从“入口”到“出口”的路径（所经过的通道方块） 分析： 1）方块的表示——坐标，当前的状态（障碍、未走的通路、已走的通路）； 2）已走的路径： A. 路径中各方块的位置及在路径中的序号; B. 从各方块出发已探索的方向，注意不能重复（可约定按东、南、西、北的方向 顺次探索）； C. 从当前方块无路可走时，将已走路径回退一个方块，继续探索其他未走的方向 栈——存储已走的通道块 3.2.5 表达式求值 1、问题描述 ·只包含+, -, *, / 四个双目运算符，且算符本身不具有二义性； ·三个运算规则→运算符优先关系（考虑算符本身的优先级和结合性）； ·只有 '('==')'，'#'=='#'； ·假设输入的是一个合法的表达式。 2、算法思想 引入 OPTR 和 OPND 两个栈 初始：OPTR 有一个元素'#'，OPND 为空 读入一字符 c c=='#'：return(GetTop(OPND)) c 非运算符：Push(OPND,c) c 运算符：t=GetTop(OPTR)，比较 t 和 c 的优先关系 tc：Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); x=Operate(a, theta, b); Push(OPND, x); 继续读入字符处理
教察 栈和队列 程序设计—数据结构 基本概念及应用 3.3栈与递归的实现 1、递归定义 直接或间接地调用自身的函数，称为递归函数。如右 图所示，递归表现为：在该函数的所有可能执行路径中， 开始 存在一条由于调用自身或其它函数所导致的环路路径：为 确保函数最终在有限的时间内执行完毕，必须在环路中存 在一个出口，即当某种条件成立时，不必执行环路，而直 形成 接执行一条通向结束的非环路线。 了环 2、递归应用 结 1)递归应用类型 ·递归定义的数学问题 ·具有递归特性的数据结构，其操作可以递归地表示 ·其它一些问题 2)递归应用的特点 对于一个问题，当问题规模很大时，往往难于直接求解，此时： ·将大问题分解成若干小问题 ·考虑如何利用这些小问题的解构成大问题的解 ·避免陷入考虑如何求解小问题 这种分解、合成的方法就是递归求解中的递归方法： 另外，递归应用要注意避免陷入死循环，递归必须有出口，即要确立递归的结束条件， 给出此时的直接求解方法。 3)递归应用举例 Hanoi塔问题 3、递归的实现 1)系统的处理 (1)调用前 现场保护，被调用函数的局部变量的空间分配，控制转移至被调用的函数入口。 (2)调用后 保存计算结果，释放被调函数的数据区，控制转移回调用处。 2)实现——栈 “后调用先返回”。系统利用递归工作栈记录各层调用的现场信息。 3.4队列的基本概念 3.4.1队列的抽象数据类型定义 1、队列的逻辑特征 1)先进先出的线性表 2)队头：允许删除的一端：队尾：允许插入的一端 3)应用举例：操作系统的作业排队 2、队列的抽象数据类型定义ADT Queue ADT Queue 文档编号 完成时间 完成人张昱 修改时间 第6页
程序设计——数据结构 栈和队列 基本概念及应用 文档编号 完 成 人 张 昱 完成时间 修改时间 第 6 页 3.3 栈与递归的实现 1、递归定义 直接或间接地调用自身的函数，称为递归函数。如右 图所示，递归表现为：在该函数的所有可能执行路径中， 存在一条由于调用自身或其它函数所导致的环路路径；为 确保函数最终在有限的时间内执行完毕，必须在环路中存 在一个出口，即当某种条件成立时，不必执行环路，而直 接执行一条通向结束的非环路线。 2、递归应用 1) 递归应用类型 ·递归定义的数学问题 ·具有递归特性的数据结构，其操作可以递归地表示 ·其它一些问题 2) 递归应用的特点 对于一个问题，当问题规模很大时，往往难于直接求解，此时： ·将大问题分解成若干小问题 ·考虑如何利用这些小问题的解构成大问题的解 ·避免陷入考虑如何求解小问题 这种分解、合成的方法就是递归求解中的递归方法； 另外，递归应用要注意避免陷入死循环，递归必须有出口，即要确立递归的结束条件， 给出此时的直接求解方法。 3) 递归应用举例 Hanoi 塔问题 3、递归的实现 1) 系统的处理 (1) 调用前 现场保护，被调用函数的局部变量的空间分配，控制转移至被调用的函数入口。 (2) 调用后 保存计算结果，释放被调函数的数据区，控制转移回调用处。 2) 实现——栈 “后调用先返回”。系统利用递归工作栈记录各层调用的现场信息。 3.4 队列的基本概念 3.4.1 队列的抽象数据类型定义 1、队列的逻辑特征 1) 先进先出的线性表 2) 队头：允许删除的一端；队尾：允许插入的一端 3) 应用举例：操作系统的作业排队 2、队列的抽象数据类型定义 ADT Queue ADT Queue{ 开始 结束 形成 了环
教黎 栈和队列 程序设计—数据结构 基本概念及应用 数据对象：D={ala∈ElemSet,.i=l,2,…,n,n≥0} 数据关系：R={R1},R1={a-1,a∈D,i=2,3,…,n} 基本操作： InitQueue(&O) 操作结果：构造一个空队列Q DestroyQueue(&Q) 初始条件：队列Q已存在 操作结果：销毁队列Q ClearOueue(&O) 初始条件：队列Q已存在 操作结果：将队列Q重置为空队列 QueueEmpty(Q) 初始条件：队列Q己存在 操作结果：若Q为空队列，则返回TRUE,否则返回FALSE QueueLength(O) 初始条件：队列Q已存在 操作结果：返回队列Q中数据元素的个数 GetHead(Q,&e) 初始条件：队列Q已存在且非空 操作结果：用e返回Q中队头元素 EnQueue(&Q,e) 初始条件：队列Q己存在 操作结果：插入元素e为Q的新的队尾元素 DeQueue(&Q,&e) 初始条件：队列Q己存在且非空 操作结果：删除Q的队头元素，并用e返回其值 QueueTraverse(Q,visit()) 初始条件：队列Q已存在且非空 操作结果：从队头到队尾依次对Q的每个数据元素调用函数visit()。一 旦visit()失败，则操作失败 }ADT Queue 3、双端队列 1)限定插入和删除在表的两端进行，应用举例：铁道转轨网络 2)输出受限的双端队列和输入受限的双端队列 3)双端队列→两个栈底相邻接的栈：限定双端队列，从某端点插入的元素只能从该端点删 除。 3.4.2链队列 1、链队列的定义 typedef struct QNode! ElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct QueuePtr front: 体队头指针，指向头元素 */ QueuePtr rear; 体队尾指针，指向队尾元素 文档编号 完成时间 完成人张昱 修改时间 第7页
程序设计——数据结构 栈和队列 基本概念及应用 文档编号 完 成 人 张 昱 完成时间 修改时间 第 7 页 数据对象：D={ai |ai∈ElemSet, i=1,2,…,n, n≥0} 数据关系：R={R1},R1={|ai-1,ai∈D, i=2,3,…,n } 基本操作： InitQueue(&Q) 操作结果：构造一个空队列 Q DestroyQueue(&Q) 初始条件：队列 Q 已存在 操作结果：销毁队列 Q ClearQueue(&Q) 初始条件：队列 Q 已存在 操作结果：将队列 Q 重置为空队列 QueueEmpty(Q) 初始条件：队列 Q 已存在 操作结果：若 Q 为空队列，则返回 TRUE，否则返回 FALSE QueueLength(Q) 初始条件：队列 Q 已存在 操作结果：返回队列 Q 中数据元素的个数 GetHead(Q,&e) 初始条件：队列 Q 已存在且非空 操作结果：用 e 返回 Q 中队头元素 EnQueue(&Q, e) 初始条件：队列 Q 已存在 操作结果：插入元素 e 为 Q 的新的队尾元素 DeQueue(&Q, &e) 初始条件：队列 Q 已存在且非空 操作结果：删除 Q 的队头元素，并用 e 返回其值 QueueTraverse(Q, visit()) 初始条件：队列 Q 已存在且非空 操作结果：从队头到队尾依次对 Q 的每个数据元素调用函数 visit()。一 旦 visit()失败，则操作失败 }ADT Queue 3、双端队列 1) 限定插入和删除在表的两端进行，应用举例：铁道转轨网络 2) 输出受限的双端队列和输入受限的双端队列 3) 双端队列→两个栈底相邻接的栈：限定双端队列，从某端点插入的元素只能从该端点删 除。 3.4.2 链队列 1、链队列的定义 typedef struct QNode{ ElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct { QueuePtr front; /* 队头指针，指向头元素 */ QueuePtr rear; /* 队尾指针，指向队尾元素 */
栈和队列 程序设计—数据结构 基本概念及应用 }LinkQueue: 1)引入队头指针、队尾指针：在O(1)时间内找到操作结点 2)引入头结点：队尾插入时，使队空和队不空的结点表示一致 3)队空的判断：头、尾指针均指向头结点 4)队满的判断转变成对申请空间是否成功的判断。 2、类型说明 操作实现：初始化、入队、出队 注意：队空的判断、入队、出队依赖于队列的表示及其约定。进一步考虑： 若无头结点，此时队列的初始化、入队、队空的条件、出队等如何表示与实现？ 3.4.3循环队列 1、循环队列的定义 采用顺序表存储，约定front指向队列头元素，rear指向队尾元素的下一位置。 #define MAXQSIZE 100 /体最大队列长度*/ typedef struct ElemType *base; 体存储空间 *八 int front: 体头指针，指向队列的头元素/ int rear: 体尾指针，指向队尾元素的下一个位置/ }SqQueue; /体非增量式的空间分配*/ 2、操作实现 1)空队：Q.front==Q.rear=0 2)入队：判断是否队满，非队满时，Q.rear位置放新插入的元素，Q.rear+ 3)出队：判断是否队空，非队空时，Q.front位置为待删除的元素，Q.front+-+ 4)队空条件：Q.front=Q.rear 5)队满条件：Q.rear=MAXQSIZE-1 问题：存在假上溢（由于出队操作，队列空间的上部可能存在空闲空间） 3、假上溢的解决 将队列假想为首尾相接的环，即循环队列。 1)入队：…，Q.rear=(Q.rear+l)%MAXQSIZE 2)出队：…，Q.front=(Q.front+-1)%MAXQSIZE 3)队空条件：Q.front=Q.rear,由于出队Q.front追上了Q.rear 4)队满条件：Q.front=Q.rear,由于入队Q.rear追上了Q.font 问题：队空和队满的判断条件一样 4、如何区分队空和队满 1)设标志位：不足在于需要额外对标志位的判断及维护 2)在队列的结构中引入长度成员，在初始化队列、入队、出队操作中维护这个成员。 3)少用一个元素空间，即队满的条件如下 (Q.rear+1)%MAXQSIZE ==Q.front 进一步思考： 1)对比4中所列的3种方法在队列操作中处理的不同。 2)若循环队列数组的下标起始为-3,1或3时，如何判断队空、队满，如何实现入队、出 队？ 文档编号 完成时间 完成人 张昱 修改时间 第8页
程序设计——数据结构 栈和队列 基本概念及应用 文档编号 完 成 人 张 昱 完成时间 修改时间 第 8 页 }LinkQueue; 1）引入队头指针、队尾指针：在 O(1)时间内找到操作结点 2）引入头结点：队尾插入时，使队空和队不空的结点表示一致 3）队空的判断：头、尾指针均指向头结点 4）队满的判断转变成对申请空间是否成功的判断。 2、类型说明 操作实现：初始化、入队、出队 注意：队空的判断、入队、出队依赖于队列的表示及其约定。进一步考虑： 若无头结点，此时队列的初始化、入队、队空的条件、出队等如何表示与实现？ 3.4.3 循环队列 1、循环队列的定义 采用顺序表存储，约定 front 指向队列头元素，rear 指向队尾元素的下一位置。 #define MAXQSIZE 100 /* 最大队列长度 */ typedef struct{ ElemType *base; /* 存储空间 */ int front; /* 头指针，指向队列的头元素 */ int rear; /* 尾指针，指向队尾元素的下一个位置 */ }SqQueue; /* 非增量式的空间分配 */ 2、操作实现 1）空队：Q.front=Q.rear=0; 2）入队：判断是否队满，非队满时，Q.rear 位置放新插入的元素，Q.rear++ 3）出队：判断是否队空，非队空时，Q.front 位置为待删除的元素，Q.front++ 4）队空条件：Q.front == Q.rear 5）队满条件：Q.rear == MAXQSIZE-1 问题：存在假上溢(由于出队操作，队列空间的上部可能存在空闲空间) 3、假上溢的解决 将队列假想为首尾相接的环，即循环队列。 1）入队：……，Q.rear = ( Q.rear+1)%MAXQSIZE 2）出队：……，Q.front = ( Q.front+1)%MAXQSIZE 3）队空条件：Q.front == Q.rear，由于出队 Q.front 追上了 Q.rear 4）队满条件：Q.front == Q.rear，由于入队 Q.rear 追上了 Q.front 问题：队空和队满的判断条件一样 4、如何区分队空和队满 1）设标志位：不足在于需要额外对标志位的判断及维护 2）在队列的结构中引入长度成员，在初始化队列、入队、出队操作中维护这个成员。 3）少用一个元素空间，即队满的条件如下 (Q.rear+1)% MAXQSIZE == Q.front 进一步思考： 1）对比 4 中所列的 3 种方法在队列操作中处理的不同。 2）若循环队列数组的下标起始为-3, 1 或 3 时，如何判断队空、队满，如何实现入队、出 队？
教黎 栈和队列 程序设计—数据结构 基本概念及应用 3.5队列与栈的应用 3.5.1离散事件模拟 文档编号 完成时间 完成人张昱 修改时间 第9页
程序设计——数据结构 栈和队列 基本概念及应用 文档编号 完 成 人 张 昱 完成时间 修改时间 第 9 页 3.5 队列与栈的应用 3.5.1 离散事件模拟
