线性表、栈和队列 s

null国家级精品课程—《数据结构与算法》国家级精品课程—《数据结构与算法》张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔：赵海燕 版权所有，转载或翻印必究第3章 栈与队列主要内容主要内容3.1 栈(Stack) 3.2 队列(Queue) 3.3 栈和队列的比较 大纲大纲2.1 线性表(linear list) 2.2 顺序表—向量(Sequential list—vector ) 2.3 链表(Linked list) 2.4 线性表实现方法的比较 2.5 栈(Stack) 2.6 队列(Queue)操作受限的线性表操作受限的线性表栈（Stack） 运算只在表的一端进行 队列（Queue） 运算只在表的两端进行 栈栈后进先出（LastInFirstOut） 一种限制访问端口的线性表 栈存储和删除元素的顺序与元素到达的顺序相反 也称为“下推表” 栈的主要元素 栈顶（top）元素：栈的唯一可访问元素 元素插入栈称为“入栈”或“压栈”（push） 删除元素称为“出栈”或“弹出”（pop） 栈底：另一端栈的示意图 栈的示意图 每次取出（并被删除）的总是刚压进的元素，而最先压入的元素则被放在栈的底部 当栈中没有元素时称为“空栈” 栈的主要操作栈的主要操作压栈（ push ） 出栈（pop） 读取栈顶元素（ top ） 判断栈是否为空（ isEmpty ）栈的抽象数据类型 栈的抽象数据类型 template // 栈的元素类型为 T class Stack { public: // 栈的运算集 void clear(); // 变为空栈 bool push(const T item); // item入栈，成功则返回真，否则返回假 bool pop(T & item); // 返回栈顶内容并弹出，成功返回真，否则返回假 bool top(T& item); // 返回栈顶内容但不弹出，成功返回真，否则返回假 bool isEmpty(; // 若栈已空返回真 bool isFull(); // 若栈已满返回真 };栈的实现方式栈的实现方式顺序栈（Array-based Stack） 使用向量实现，本质上是顺序表的简化版 栈的大小 关键是确定哪一端作为栈顶 链式栈（Linked Stack） 用单链表方式存储，其中指针的方向是从栈顶向下链接 顺序栈 顺序栈 template class arrStack : public Stack { private: // 栈的顺序存储 int mSize; // 栈中最多可存放的元素个数 int top; // 栈顶位置，应小于mSize T *st; // 存放栈元素的数组 public: // 栈的运算的顺序实现 arrStack(int size) { // 创建一个给定长度的顺序栈实例 mSize = size; top = -1; st = new T[mSize]; } arrStack() { // 创建一个顺序栈的实例 top = -1; } ~arrStack() { // 析构函数 delete [] st; } void clear() { // 清空栈内容 top = -1; } }顺序栈 顺序栈 按压入先后次序，最后压入的元素编号为4，然后依次为3，2，1 nullpush(st, ‘A’);Apush(st, ‘B’) ;Bpush(st, ‘C’);Cpop(st); pop(st); pop(st); 顺序栈示意顺序栈示意顺序栈示意顺序栈的溢出顺序栈的溢出上溢（Overflow） 当栈中已经有maxsize个元素时，如果再做进栈运算，所产生的现象 下溢（Underflow） 对空栈进行出栈运算时所产生的现象 顺序栈 顺序栈 若入栈的顺序为1,2,3,4的话，则出栈的顺序可以有哪些? 1234 1243 1324 1342 1423 1432 2134 2143 ……压栈操作压栈操作bool arrStack::push(const T item) { if (top == mSize-1) { // 栈已满 cout << "栈满溢出" << endl; return false; } else { // 新元素入栈并修改栈顶指针 st[++top] = item; return true; } }出栈操作出栈操作bool arrStack::pop(T & item) { // 出栈的顺序实现 if (top == -1) { // 栈为空 cout << "栈为空，不能执行出栈操作"<< endl; return false; } else { item = st[top--]; // 返回栈顶元素并修改栈顶指针 return true; } }读栈操作读栈操作bool arrStack:: top(T & item) { // 返回栈顶内容，但不弹出 if (top == -1) { // 栈空 cout << " 栈为空，不能读取栈顶元素"<< endl; return false; } else { item = st[top]; return true; } } 其他操作 其他操作 把栈清空 void arrStack::clear() { top = -1; } 栈满时，返回非零值（真值true） bool arrStack:: isFull() { return (top == maxsize-1) ; }栈的变种栈的变种两个独立的栈 底部相连：双栈 迎面增长 哪一种更好些？ 迎面增长的栈top1top2链式栈链式栈 ki+2 ki+1 ki k0  topdatanext用单链表方式存储 指针的方向从栈顶向下链接 链式栈的创建 链式栈的创建 template class lnkStack : public Stack { private: // 栈的链式存储 Link* top; // 指向栈顶的指针 int size; // 存放元素的个数 public: // 栈运算的链式实现 lnkStack(int defSize) { // 构造函数 top = NULL; size = 0; } ~lnkStack() { // 析构函数 clear(); } }压栈操作压栈操作// 入栈操作的链式实现 bool lnksStack:: push(const T item) { Link* tmp = new Link(item, top); top = tmp; size++; return true; }出栈操作出栈操作// 出栈操作的链式实现 bool lnkStack:: pop(T& item) { Link *tmp; if (size == 0) { cout << "栈为空，不能执行出栈操作"<< endl; return false; } item = top->data; tmp = top->next; delete top; top = tmp; size--; return true; }顺序栈和链式栈的比较顺序栈和链式栈的比较时间效率 所有操作都只需常数时间 顺序栈和链式栈在时间效率上难分伯仲 空间效率 顺序栈须说明一个固定的长度 链式栈的长度可变，但增加结构性开销顺序栈和链式栈的比较顺序栈和链式栈的比较实际应用中，顺序栈比链式栈用得更广泛些 存储开销低 顺序栈容易根据栈顶位置，进行相对位移，快速定位并读取栈的内部元素 顺序栈读取内部元素的时间为O(1)，而链式栈则需要沿着指针链游走，显然慢些，读取第k个元素需要时间为O(k) 一般来说，栈不允许“读取内部元素”，只能在栈顶操作 栈的应用栈的应用栈的特点：后进先出 体现了元素之间的透明性 常用来处理具有递归结构的数据 深度优先搜索 表达式求值 数制转换 行编辑处理 子程序／函数调用的管理 消除递归数制转换数制转换非负十进制数转换成其它进制的数的一种简单方法： 例，十进制转换成八进制：(66)10=(102)8 66/8=8 余 2 8/8=1 余 0 1/8=0 余 1 结果为余数的逆序：102 先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的先入后出性质，故可用栈来实现数制转换。 同理，一个非负十进制整数N转换为另一个等价的基为B的B进制数，可以采用"除B取余法"来解决 计算表达式的值计算表达式的值表达式的递归定义 基本符号集：{0，1，…，9，+，-，*，/，（，）} 语法成分集：{<表达式> , <项> , <因子> , <常数> , <数字> } 语法公式集 中缀表达式 23+(34*45)/(5+6+7) 后缀表达式 23 34 45 * 5 6 + 7 + / + 后缀表达式求值 中缀表达法的语法公式 中缀表达法的语法公式 <表达式> ∷= <项> + <项> | <项> － <项> | <项> <项> ∷= <因子> * <因子> | <因子> / <因子> | <因子> <因子> ∷= <常数> | （ <表达式> ） <常数> ∷= <数字> | <数字> <常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 中缀表达式的计算次序 中缀表达式的计算次序 先执行括号内的计算，后执行括号外的计算。在具有多层括号时，按层次反复地脱括号，左右括号必须配对 在无括号或同层括号时，先乘(*) 、除(／)，后加(+)、减(-) 在同一个层次，若有多个乘除（*、／）或加减 (+，-)的运算，那就按自左至右顺序执行 23+(34*45)/(5+6+7) = ? 计算特点？后缀表达式 后缀表达式 <表达式> ∷= <项> <项> + | <项> <项> - | <项> <项> ∷= <因子> <因子> * | <因子> <因子> / | <因子> <因子> ∷= <常数> <常数> ∷= <数字> | <数字> <常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 后缀表达式的计算后缀表达式的计算 23 34 45 * 5 6 + 7 + / + =？ 计算特点？中缀和后缀表达式的主要异同？ 23+(34*45)/(5+6+7) = ? 23 34 45 * 5 6 + 7 + / + = ?中缀表达式 to 后缀表达式从左到右扫描中缀表达式。用栈存放表达式中的操作数、开括号以及在此开括号后暂不确定计算次序的其他符号： (1) 当输入的是操作数时，直接输出到后缀表达式序列； (2) 当遇到开括号时，把它压入栈； (3) 当输入遇到闭括号时，先判断栈是否为空，若为空（括号不匹配），应该作为错误异常处理，清栈退出。 若非空，则把栈中元素依次弹出，直到遇到第一个开括号为止，将弹出的元素输出到后缀表达式序列中（弹出的开括号不放到序列中），若没有遇到开括号，说明括号不配对，做异常处理，清栈退出。 中缀表达式 to 后缀表达式中缀表达式 to 后缀表达式中缀表达式 to 后缀表达式从左到右扫描中缀表达式。用栈存放表达式中的操作数、开括号以及在此开括号后暂不确定计算次序的其他符号： （4）当输入为运算符op（ 四则运算 + - * / 之一）时 （a）循环 当（栈非空 and 栈顶不是开括号 and 栈顶运算符的优先级不低于输入的运算符的优先级）时，反复操作 将栈顶元素弹出，放到后缀表达式序列中； （b）将输入的运算符压入栈内； （5）最后，当中缀表达式的符号全部读入时，若栈内仍有元素，把它们全部依次弹出，放在后缀表达式序列的尾部。若弹出的元素遇到开括号，则说明括号不匹配，做异常处理，清栈退出。中缀表达式 to 后缀表达式中缀表达式 to 后缀表达式待处理中缀表达式： 输出后缀表达式： 栈的状态23/45567*＋＋＋()()34后缀表达式求值 后缀表达式求值 循环：依次顺序读入表达式的符号序列（假设以＝作为输入序列的结束），并根据读入的元素符号逐一分析： 1.当遇到的是一个操作数，则压入栈顶； 2.当遇到的是一个运算符, 就从栈中两次取出栈顶，按照运算符对这两个操作数进行计算。然后将计算结果压入栈顶 如此继续，直到遇到符号＝, 这时栈顶的值就是输入表达式的值 后缀表达式求值后缀表达式求值待处理后缀表达式：23/45567*＋＋＋34栈状态的变化1530111885108后缀计算器的类定义后缀计算器的类定义// Class Declaration 类的说明 (参见算法3.5) class Calculator { private: Stack s; // 这个栈用于压入保存操作数 // 从栈顶弹出两个操作数opd1和opd2 bool GetTwoOperands(double& opd1,double& opd2); // 取两个操作数，并按op对两个操作数进行计算 void Compute(char op); public: Calculator(void){} ; // 创建计算器实例，开辟一个空栈 void Run(void); // 读入后缀表达式，遇到符号"="时，求值计算结束 void Clear(void); //清除计算器，为下一次计算做准备 };栈与递归栈与递归函数的递归定义 主程序和子程序的参数传递 栈在实现函数递归调用中的作用 递归递归作为数学和计算机科学的基本概念，递归是解决复杂问题的一个有力手段，可使问题的描述和求解变得简洁、清晰、易懂 符合人类解决问题的思维方式，递归能够描述和解决很多问题，为此许多程序设计语言都提供了递归的机制 常常比非递归算法更易设计，尤其是当问题本身或所涉及的数据结构是递归定义的时候，使用递归算法特别合适 而计算机则只能按照指令集来顺序地执行 计算机内（编译程序）是如何将程序设计中的便于人类理解的递归程序转换为计算机可处理的非递归程序的? 递归递归直接或间接调用自己的函数或过程 递归步骤：将规模较大的原问题分解为一个或多个规模更小、但具有类似于原问题特性的子问题 即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题 递归出口：确定一个或多个无须分解、可直接求解的最小子问题（称为递归的终止条件） 相关概念 迭代 归纳递归定义阶乘n！函数 递归定义阶乘n！函数 阶乘n！的递归定义如下： 递归定义由两部分组成： 递归基础/出口 递归规则 正确性证明？ 计算阶乘n！的递归程序计算阶乘n！的递归程序// 递归定义的计算阶乘n!的函数 long fact(long n) { if (n <= 1) return 1; else return n * fact (n-1) ; // 递归调用 } if (n == 1)？ 递归问题求解过程示例：阶乘递归问题求解过程示例：阶乘 call fact(4) call fact(3) call fact(2) call fact(1) return 24 fact(4) return 6 fact(3) return 2 fact(2) return 1递归函数的实现递归函数的实现栈的一个最为广泛的应用对用户而言透明：程序运行环境所提供的函数调用机制 运行时环境：目标计算机上用来管理存储器并保存执行过程所需的信息的寄存器及存储器的结构 函数调用 静态分配：（在非递归）数据区的分配可以在程序运行前进行，直到整个程序运行结束才释放。采用静态分配时，函数的调用和返回处理比较简单，不需要每次分配和释放被调函数的数据区 动态分配：在递归调用的情况下，被调函数的局部变量不能静态地分配某些固定单元，而须每调用一次就分配一份，以存放当前所使用的数据，当返回时随即释放。故其存储分配只能在执行调用时才能进行：在内存中开辟一个称为运行栈（runtime stack）的足够大的动态区函数运行时的动态存储分配函数运行时的动态存储分配用作动态数据分配的存储区可按多种方式组织。典型的组织是将这个存储器分为栈（stack）区域和堆（heap）区域 栈区域用于分配发生在后进先出LIFO风格中的数据（诸如函数的调用） 堆区域则用于不符合LIFO（诸如指针的分配）的动态分配运行栈中的活动记录运行栈中的活动记录函数活动记录（activation record）是动态存储分配中一个重要的单元 当调用或激活函数时，函数的活动记录包含了为其局部数据分配的存储空间 运行栈中的活动记录运行栈中的活动记录运行栈随着程序执行时发生的调用链或生长或缩小 每次调用一个函数时，执行进栈操作，把被调函数的活动信息压入栈中，即每个新的活动记录都分配在栈的顶部 每次从函数返回时，执行出栈操作，释放本次的活动记录，恢复到上次调用所分配的数据区中 被调函数中变量地址全部采用相对于栈顶的相对地址来表示 一个函数在运行栈中可有若干不同的活动记录，每个代表一个不同的调用 对于递归函数来说，递归的深度就决定了其在运行栈中活动记录的数目 当函数递归调用时，函数体的同一个局部变量，在不同的递归层次被分配给不同的存储空间，放在内部栈的不同位置函数调用与返回处理函数调用与返回处理调用可以分解成以下三步来实现： 调用函数发送调用信息。调用信息包括调用方要传送给被调方的信息，诸如实参、返回地址等 分配被调方需要的局部数据区，用来存放被调方定义的局部变量、形参变量（存放实参）、返回地址等，并接受调用方传送来的调用信息 调用方暂停，把计算控制转到被调方，亦即自动转移到被调用的函数的程序入口 当被调方结束运行，返回到调用方时，其返回处理一般也分三步进行： 传送返回信息，包括被调方要传回给调用方的信息，诸如计算结果等 释放分配给被调方的数据区 按返回地址把控制转回调用方递归时运行栈的变化示例递归时运行栈的变化示例以阶乘为例： #include main() { int x; scanf(“%d”, &x)； printf(“%d\n”, fact (4)); }计算阶乘时的运行栈计算阶乘时的运行栈栈生长方向计算阶乘时的运行栈计算阶乘时的运行栈递归算法的非递归实现递归算法的非递归实现以阶乘为例，非递归方式建立迭代 递归转换为非递归计算阶乘n！的循环迭代程序 计算阶乘n！的循环迭代程序 // 使用循环迭代方法，计算阶乘n!的程序 long fact (long n) { int m = 1; int i ; if (n > 1) for ( i = 1; i <= n; i++ ) m = m * i ; return m ; } 递归的再研究递归的再研究递归 递归出口 递归规则递归 递归出口 意味? 递归规则 意味?阶乘n！的一种非递归实现阶乘n！的一种非递归实现long fact (long n) { Stack s; int m = 1; while (n>0) // ? s.push(n--); while (!isEmpty(s)) { // ? m *= s.pop(s); return m ; } 非递归程序的实现原理非递归程序的实现原理与递归函数的原理相同，只不过把由系统负责的保存工作信息变为由程序自己保存 减少保存数据的冗余(主要是节省了局部变量的空间)，提高存储效率 减少函数调用的处理以及冗余的重复计算，提高时间效率 程序要完成的工作分成两类： 手头工作 程序正在做的工作，必须有其结束条件，不能永远做下去 保存在栈中的待完成的工作 由于某些工作不能一步完成，必须暂缓完成，把它保存在栈中，保存的待完成工作必须含有完成该项工作的所有必要信息。 程序须有序地完成各项工作 手头工作和待完成工作可互相切换 待完成工作必须转换成手头工作才能处理待学了树形结构可知，所有递归问题，其递归过程可以展开成一棵树，叶结点是可解的递归转换为非递归的方法递归转换为非递归的方法机械方法 设置一工作栈保存当前工作记录 设置 t+2个语句标号 增加非递归入口 替换第 i (i = 1, …, t)个递归规则 所有递归出口处增加语句：goto label t+1; 标号为t+1的语句的格式 改写循环和嵌套中的递归 优化处理设置一工作栈保存当前工作记录设置一工作栈保存当前工作记录在函数中出现的所有参数和局部变量都必须用栈中相应的数据成员代替 返回语句标号域 (t+2个数值) 函数参数(值参、引用型) 局部变量 class elem { // 栈数据元素类型 int rd; // 返回语句的标号 Datatypeofp1 p1; // 函数参数 … Datatypeofpm pm; Datatypeofq1 q1; // 局部变量 … Datatypeofqn qn; }; Stack S;设置t+2个语句标号设置t+2个语句标号label 0 ：第一个可执行语句 label t+1 ：设在函数体结束处 label i (1<=i<=t)： 第i个递归返回处 增加非递归入口增加非递归入口// 入栈 elem tmp; tmp.rd = t+1; tmp.p1=p1; … tmp.pm = pm; tmp.q1 = q1; … tmp.qn = qn; S.push(tmp);替换第i (i=1,…,t)个递归规则替换第i (i=1,…,t)个递归规则假设函数体中第i (i=1, …, t)个递归调用语句为：recf(a1, a2, …, am)； 􀂄则用以下语句替换： S.push(i, a1, …, am)； // 实参进栈 goto label 0； ….. label i： x = S.pop()； /* 退栈，然后根据需要，将x中某些值赋给栈顶的工作记录S.top () — 相当于把引用型参数的值回传给局部变量 */所有递归出口处增加语句所有递归出口处增加语句 goto labelt+1; 标号为t+1的语句标号为t+1的语句switch ((x=S.top ()).rd) { case 0 : goto label 0; break; case 1 : goto label 1; break; ………. case t+1 : item = S.pop() // 返回处理 break; default : break; }改写循环和嵌套中的递归改写循环和嵌套中的递归对于循环中的递归，改写成等价的goto型循环 对于嵌套递归调用 譬如，recf (… recf()) 改为： exmp1 = recf ( ); exmp2 = recf (exmp1); … exmpk = recf (exmpk-1) 然后应用规则 4 解决优化处理优化处理经过上述变换所得到的是一个带goto语句的非递归程序。可以进一步优化 去掉冗余进栈/出栈 根据流程图找出相应的循环结构，从而消去goto语句 递归的非递归实现递归的非递归实现请大家思考，用机械的转换方法 2阶斐波那契函数 f0=0, f1=1, fn = fn-1+ fn-2 背包问题 Hanio Tower背包问题背包问题简化版：设有一背包可放入的物品重量为S，现有n件物品，重量分别为w0，w1， …，wn-1，问能否从这n件物品中选择若干件放入背包，使其重量之和正好为S。 若存在一种符合上述要求的选择，则称此背包问题有解，否则无解。 背包问题背包问题bool knap(int s, int n) { if (s == 0) return true; if ((s < 0) || (s>0 && n <1)) return false; if (knap (s-w[n-1], n-1)) { cout << w[n-1]; return true; } else return knap(s, n-1); }背包问题背包问题递归规则 若w[n-1]包含在解中，求解knap(s-w[n-1], n-1) 若w[n-1]不包含在解中，求解knap(s, n-1) + 递归出口，共有3种返回地址： 计算knap(s, n)完毕返回调用它的函数； 计算knap(s-w[n-1], n-1)完毕，返回到本调用函数继续计算； 计算knap(s, n-1)完毕，返回到本调用函数继续计算。背包问题背包问题转换如下： 1．凡调用语句knap(s, n)均代换成 (1) tmp.s = s; tmp.n = n; tmp.rd = 返回地址编号 (2) stack.push(tmp); (3) 转向递归入口 2．将调用出口的返回处理统一： (1) stack.pop(&tmp); (2) 分以下情况执行 i) tmp.rd = 0 时，算法结束 ii) tmp.rd = 1时，转规则1返回处理 iii) tmp.rd = 2时，转规则2返回处理 HanioTowerHanioTower源于印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。 此后演变为游戏： 有3个座A、B、C，开始时A座上有n个盘子，盘子大小不等，大的在下，小的在上。有个老和尚想把这n个盘子从A座移到C座，但每次只允许移动一个盘，且移动过程中在3个座上都始终保持大盘在下，小盘在上的。在移动过程中可以利用B座。Hanio TowerHanio Tower一种递归实现 // x    Source // y  Destination // n    Number of plates void Hanoi(int x, int y, int n) {     if (n == 0) return;     Hanoi(x, x^y, n-1);     Move(x, y);     Hanoi(x^y, y, n-1); } 其中，x、y可取1、2、3三数之一，并且x≠y，x^y表示x、y按位异或，得到除x、y之外的第三个数Hanio Tower的非递归实现Hanio Tower的非递归实现#define N 8 class HanioData {     int x;     int y;     int n; }; void Hanoi(HanioData hd) {     Stack< HanioData >  stack(N);     while (hd.n || !stack.isEmpty()) {   // 还有手头工作或待完成工作             while (hd.n)  { // 处理手头工作直到无现成的手头工作，从栈中取出下次的手头工作                                   hd.n --;       stack.push(hd);  // 保存待完成工作             hd.y ^= hd.x; // 新的手头工作         }         if (!stack.isEmpty()) {  // 存在待完成工作                   stack.pop(&hd);  // 从栈中取出             Move(hd.x, hd.y);    // 直接处理             hd.x ^= hd.y; // 未处理完的转换成手头工作         }     } } 队列队列先进先出（FirstInFirstOut） 限制访问点的线性表 按照到达的顺序来释放元素 所有的插入在表的一端进行，所有的删除都在表的另一端进行 主要元素 队头（front） 队尾（rear）队列示意图队列示意图队头队尾进队出队k0 k1 k2 …. kn-1允许删除的一端称为队头 允许插入的一端称为队尾 当队列中没有元素时称为空队列队列的主要操作队列的主要操作入队列（enQueue） 出队列（deQueue） 取队首元素（getFront） 判断队列是否为空（isEmpty） 队列的抽象数据类型队列的抽象数据类型template class Queue { public: // 队列的运算集 void clear(); // 变为空队列 bool enQueue(const T item); // 将item插入队尾，成功则返回真，否则返回假 bool deQueue(T& item); // 返回队头元素并将其从队列中删除，成功则返回真 bool getFront(T& item); // 返回队头元素，但不删除，成功则返回真 bool isEmpty(); // 返回真，若队列已空 bool isFull(); // 返回真，若队列已满 };队列的实现方式队列的实现方式顺序队列 关键是如何防止假溢出 链式队列 用单链表方式存储，队列中每个元素对于链表中的一个结点顺序队列 顺序队列 使用顺序表来实现队列 用数组存储队列元素，并用两个变量分别指向队列的前端和尾端 null76543210Q.front Q.reark0k1k2k5队列空再进队一个元素如何？队列示意：普通k4队列的溢出队列的溢出上溢 当队列满时，再做进队操作，所出现的现象 下溢 当队列空时，再做删除操作，所出现的现象 假溢出 当 rear = MAXNUM时，再作插入运算就会产生溢出，如果这时队列的前端还有许多空的（可用的）位置，这种现象称为假溢出 nullk4k5k6k6k5队列满队列示意：环形k0k1k2k3Q.front队列空k4null队列空： Q.rear == Q.front队列满： (Q.rear+1) mod M == Q.front队列示意：环形顺序队列的类定义 顺序队列的类定义 class arrQueue: public Queue { private: int mSize; // 存放队列的数组的大小 int front; // 表示队头所在位置的下标 int rear; // 表示队尾所在位置的下标 T *qu; // 存放类型为T的队列元素的数组 public: // 队列的运算集 arrQueue(int size) { // 创建队列的实例 mSize = size +1; // 浪费一个存储空间，以区别队列空和队列满 qu = new T [mSize]; front = rear = 0; } ~arrQueue() { // 消除该实例，并释放其空间 delete [] qu; } }新元素插入队列尾端新元素插入队列尾端入队列入队列bool arrQueue :: enQueue(const T item) { // item入队，插入队尾 if (((rear + 1 ) % mSize) == front) { cout << "队列已满，溢出" << endl; return false; } qu[rear] = item; rear = (rear +1) % mSize; // 循环后继 return true; }出队列出队列bool arrQueue :: deQueue(T& item) { // 返回队头元素并从队列中删除 if ( front == rear) { cout << "队列为空" << endl; return false; } item = qu[front]; front = (front +1) % mSize; return true; }队列的运行示意图队列的运行示意图队列的运行示意图队列的运行示意图链式队列链式队列单链表队列 链接指针的方向是从队列的前端向尾端链接链式队列的类定义链式队列的类定义template class lnkQueue: public Queue { private: int size; // 队列中当前元素的个数 Link* front; // 表示队头的指针 Link* rear; // 表示队尾的指针 public: // 队列的运算集 lnkQueue(int size) { // 创建队列的实例 size = 0; front = rear = NULL; } ~lnkQueue() { // 消除该实例，并释放其空间 clear(); } }链式队列的插入链式队列的插入// item入队，插入队尾 bool lnkQueue :: enQueue(const T item) { if (rear == NULL) { // 空队列 front = rear = new Link (item, NULL); } else { // 添加新的元素 rear-> next = new Link (item, NULL); rear = rear ->next; } size++; return true; }链式队列的删除链式队列的删除// 返回队头元素并从队列中删除 bool lnkQueue :: deQueue(T& item) { Link *tmp; if (size == 0) { // 队列为空，没有元素可出队 cout << "队列为空" << endl; return false; } &item = front->data; tmp = front; front = front -> next; delete tmp; if (front == NULL) rear = NULL; size--; return true; }顺序队列与链式队列的比较 顺序队列与链式队列的比较 顺序队列 固定的存储空间 方便访问队列内部元素 链式队列 可以满足浪涌大小无法估计的情况 访问队列内部元素不方便队列的应用 队列的应用 只要满足先来先服务特性的应用均可采用队列作为其数据组织方式或中间数据结构。 调度或缓冲 消息缓冲器 邮件缓冲器 计算机的硬设备之间的通信也需要队列作为数据缓冲 操作系统的资源管理 宽度优先搜索舞伴问题舞伴问题假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。 要求写一算法模拟上述舞伴配对问题 变种的栈或队列结构 变种的栈或队列结构 双端队列 双栈 超队列 超栈 小结 小结 栈 栈的特点 栈的实现 栈的应用 队列 队列的特点 队列的实现 队列的应用 课程和教材参考信息课程和教材参考信息国家级精品课程—《数据结构与算法》 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ “十一五”国家级规划教材：张铭，王腾蛟，赵海燕，《数据结构与算法》高等教育出版社，2008. 6。 本章主笔：赵海燕 版权所有，转载或翻印必究