第3章 栈与队列.

Presentation on theme: "第3章 栈与队列."— Presentation transcript:

1 第3章 栈与队列

2 目录 1.栈 2. 栈的应用举例 3. 栈与递归 4. 队列 5. 应用实例

3 3.1 栈 3.1.1 栈的定义及其运算 栈（Stack）是限定插入和删除运算只能在表尾进行的线性表。
通常称允许插入、删除的这一端为栈顶，另一端称为栈底。 当表中没有元素时称为空栈。 其中数据元素的个数n定义为表的长度。

4 后进先出（Last In First Out）的线性表，简称为LIFO表。
图3.1是一个栈的示意图，通常用指针top指示栈顶的位置，用指针bottom指向栈底。栈顶指针top动态反映栈的当前位置。 图3.1所示的栈中，元素是以a1， a2，…，an的顺序进栈，而出栈 的次序却是an，an-1，…，a1。 也就是说，栈的修改是按后进先 出的原则进行的。因此，栈又称为 后进先出（Last In First Out）的线性表，简称为LIFO表。

5 栈的ADT声明如下： ADT Stack { Typedef struct Stack S; InitStack(S,maxSize);
StackSize(S); 说明：求栈中元素的数目 isEmpty(S); 说明：判栈S是否为空栈 isFull(S); 说明：判栈S是否已“满”

6 GetTop(S,e); 说明：取栈顶元素 Push (S,e); 说明：值为e的数据元素进栈（插入、压栈） Pop(S); 说明：栈顶元素出栈（删除、退栈） };

7 3.1.2 栈的顺序存储结构 栈的顺序存储结构称为顺序栈，是用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。
因为栈底位置是固定不变的，栈顶位置是随着进栈和退栈 操作而变化的，故需用一个变量top来指示当前栈顶位置， 通常称top为栈顶指针，参看图3.2。

8 我们先以整数元素为例，给出顺序栈的基本算法，在下一节，将给出顺序栈的模板类接口定义以及基本运算的实现代码和应用实例。
Typedef struct { int *elem; // elem是数据元素数组 int top; // 栈顶指针 int maxSize; // 栈容量 }sqStack;

9 void InitStack(S,maxSize) // 栈初始化
{ S.top=-1; S.elem=new int[maxSize]; } bool isEmpty(S) // 判栈空否？ { return S.top==-1; } bool isFull (S) // 判栈满否？ { return top==S.maxSize-1; } bool Push (sqStack S, int e) // 值为e的数据元素进栈(插入 、 压栈) { if(isFull(S)) // 栈满（溢出）无法进栈, 返回false { cout << " ERROR: overflow !!\n"; return false; } S.elem[++S.top] = e ; return true ; //栈顶指针增1元素进栈, 返回true }

10 bool Pop(sqStack S) // 栈顶元素出栈(删除)
{ if(isEmpty(S)) // 栈空无法删除, 返回false { cout << “ ERROR: underflow !!\n”; return false ; } S.top--; return true; // 元素出栈 } bool GetTop(sqStack S, int &e) // 取栈S的栈顶元//素 { if(isEmpty(S)) // 栈空（下溢） e=S.elem[S.top] ; return true ; // 元素存e, 栈顶指针不变(元素没出栈)

11 栈的使用非常广泛，常常会出现在一个程序中需要同时使用多个栈的情形。为了不因栈上溢而产生错误中断，要给每个栈预分较大空间，但各个栈实际所用最大空间很难估计。而且各个栈的实际容量在使用期间是变化的，往往会出现某个栈发生上溢，而另一个栈还是空的。 试设想，若令多个栈共享空间，则将提高空间的使用效率，并减少发生栈上溢的可能性。

12 假设在程序中需设两个栈，并共享一维数组空间v[m]。则利用“栈底位置不变”的特性，可将两个栈的栈底分别设在数组空间的两端，然后各自向中间伸展（如图3.3所示），仅当两个栈的栈顶相遇时才可能发生上溢。由于两个栈之间可以做到互补余缺，使得每个栈实际可利用的最大空间大于m/2。显然，两个栈顶的初值分别为-1和m。

13 3.1.3 栈的链式存储结构 栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行。
由于只能在链表头部进行操作， 故链栈没有必要象单链表那样 附加上头结点。栈顶指针就是 链表的头指针，如图3.4所示， 链栈就是无头结点的单链表 （头指针改称栈顶指针），因 此不再重新讨论。

14 3.2 栈的应用举例 栈的应用非常广泛，只要问题满足LIFO原则，均可使 用栈做数据结构。 //顺序栈的模板类接口定义以及基本运算的实现代码
template <class T> class sqStack { protected: int *elem ; // 指向存放数据元素的数组指针 int top ; // 栈顶指针 int maxSize; // 栈容量 public: sqStack(int ms=10); // 构造函数

15 sqStack (const sqStack<T>&); // 复制构造函数
~sqStack() { delete[] elem; } // 析构函数 sqStack& operator=(const sqStack<T>&); // “=”运算符重载 bool isEmpty() { return top = = -1 ; } // 判栈“空”否？ bool isFull() // 判栈“满” 否？ { return top == maxSize-1; } bool Push(T); // 进栈 (插入、压栈) bool Pop(); // 出栈 (删除、退栈) bool GetTop(T &); // 取栈顶元素 };

16 template <class T>sqStack<T>::sqStack(int ms)
// 构造“空” 栈 { if(ms<=0) { cout<<"ERROR:invalid MaxSize!!\n"; return; } elem=new T[ms]; MaxSize=ms; top=-1; } template <class T>bool sqStack<T>::Push(T e) // 元素e压栈 { if(isFull()) // 栈满（溢出） { cout << “ ERROR: overflow !!\n”; return false; } elem[++top]=e; // 栈顶指针增1, 元素进栈 return true;

17 template <class T>bool sqStack<T>::Pop()
{ if(isEmpty()) // 栈空（下溢） { cout << “ ERROR: underflow !!\n”; return false; } top--; //栈顶指针减1(元素出栈) return true; } template <class T>bool sqStack<T>::GetTop(T &e) // 取栈顶元素 { if(isEmpty(S)) // 栈空（下溢） e=elem [top]; // 元素存e, 栈顶不变(元素没出栈)

18 return true; } template <class T>sqStack<T>::sqStack(const sqStack<T>& obj) //由顺序栈obj复制构造新栈 { MaxSize=obj.MaxSize; //被构造栈与obj容量应相同 elem=new T [MaxSize]; top = obj.top; //申请空间, 栈顶指针赋值 for(int j=0; j<=top; j++) elem[j]= obj.elem[j]; // 复制数据元素

19 template<classT>sqStack<T>&sqStack<T>::operator=(const sqStack<T>&origin) //"="运算符重载 { if(MaxSize!=origin.MaxSize) // 栈容量不等 // 需释放原来的存放数据元素空间，重新为当前栈申请空间 { delete[] elem; MaxSize=origin.MaxSize; elem=new T [MaxSize]; } top=origin.top; //栈顶指针赋值 for(int j=0; j<=top; j++) elem[j]=origin.elem[j]; //复制数据元素

20 【例3.1】用栈实现程序设计语言中的子程序调用
和返回。 假设有一个主程序main和三个子程序A1，A2和A3，其调用关系如图3.5所示。

21 从图3.5可知，主程序main调用子程序A1，子程序A1完成之后，返回到主程序的r处继续执行。但是，因为子程序A1又调用了子程序A2，所以在A2执行完毕并返回之前，A1是不可能结束的。类似地，A2也必须在A3执行完毕并返回之后才能从t处继续进行。其调用与返回的过程如图3.6所示。 显然，调用次序和返回次序是 相反的，最后调用到的子程序 最先返回。为了保证各个被调 用子程序能正确地返回，可以 在程序运行期间设置一个工作 栈来保存返回地址。

22 当调用某一个子程序时，将该子程序的返回地址进栈；当某一子程序执行完毕时将当前栈顶的返回地址出栈，并按该地址返回。注意，某一子程序P执行完毕，当前栈顶内容一定是P的返回地址。因为只有当执行P时所调用的其它子程序都已返回，P才能结束，这就保证了当P返回时，其相应的返回地址正好是在当前栈顶，参看图3.7。

23 【例3.2】 表达式转换（中缀表达式改写成后缀表 示法）
算术表达式有三种表示方法：⑴<操作数> <操作符> <操作数>，如A+B，称为中缀(infix)表示；⑵<操作符> <操作数> <操作数>，如+AB称为前缀(prefix)表示；⑶<操作数> <操作数> <操作符>，如AB+，称为后缀(postfix)表示。 在后缀表达式中，没有括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行，整个计算过程仅需一遍扫描便可完成，显然比中缀表达式的计算要简单得多。因此，程序设计语言的编译系统要将通常的中缀表达式转换成后缀表达式

24 例如，A*(B+C)的后缀表达式是ABC+*, 因’+’运算符在前，’*’ 运算符在后，所以应先做加法，后做乘法。
再如，表达式A/B*C+D*(E-A)+C/(D*B) 的后缀形式是AB/C*DEA-*+CDB*/+ . 怎样设计算法把运算符放在两个运算对象中间的中缀表达 式转换为后缀形式呢？ 观察一下两种形式的表达式，我们注意到操作数在两种形 式中出现的次序是相同的。所以在扫描表达式时，凡遇到 操作数就马上输出，剩下的事情就是处理所遇到的运算符。 解决的办法是把遇到的运算符存放到栈中，直到某个适当 时刻再将运算符退栈并输出。

25 我们来看两个例子： （1）要由表达式A+B*C产生出后缀表达式ABC*+，必须按照如表3.1所示的操作顺序执行（栈向右增长）。到达第4步时必须确定是’*’进入栈顶，还是’+’退栈；由于’*’的优先级更高，应该是’*’进栈，从而产生第5步；现在已从表达式中取完所有的符号，于是我们输出运算符栈中所有剩余的运算符得到： ABC*+ （2）表达式A*(B+C)/D 的后缀形式为ABC+* D/，当遇到左括号时必须入栈，遇到右括号时，必须依次把栈中元素退栈。直到相应的左括号为止，然后去掉左右括号。如表3.2所示。

26

27 这些例子启发我们，算术运算符和括号可用如表3.3所示分级方案实现。其规则是：
只要运算符在栈中的优先级isp(in-stack priori ty)大于或等于新运算符进来时的优先级icp(in-c oming priority)，则运算符就从栈中取出。 isp(x)和icp(x)是函数，它们返回运算符按上述 给定的优先级值。

28 具体算法如下： //将表达式的中缀形式转换为后缀形式 #include <fstream.h>
#include "SQStack.h" ofstream ofile; // 创建输出流文件 void postfix(char*e); // 将中缀表达式e转换为后缀形式输出的原型声明 void InitStack(S,maxSize) // 栈初始化 { S.top=-1; S.elem=new int[maxSize]; } bool isEmpty(S) //判栈空否？ { return S.top==-1; }

29 bool isFull (S) // 判栈满否？
{ return top==S.maxSize-1; } bool Push (sqStack S, int e) // 值为e的数据元素进栈(插入、压栈) { if(isFull(S)) // 栈满 { cout << “ ERROR: overflow !!\n”; return false; } S.elem[++S.top]=e; // 栈顶指针增1元素进栈 return true ; void main() { char s[30]; int i, n; // s 存从输入流读入的待翻译的表达式字符串 ifstream infile; // 创建输入文件infile

30 infile.open(“expression.in”);
// infile与磁盘文件expression.in 相关联 ofile.open("expression.out"); // ofile与磁盘文件expression.out相关联 infile >> n; // 从文件读入要翻译的表达式数 for(i=0; i<n; i++) // 从文件逐一读入n个中缀表达式 { infile >> s; ofile <<“ \n infix: ”<<s <<" \npostfix: "; postfix(s); // 转换中输出对应的//后缀表达式 } ofile <<endl; infile.close(); ofile.close();

31 int isp(char x) // 返回栈中运算符的优先级(in- stack priority) { if(x==‘*’||x==‘/’) return 2; else if(x=='+'||x=='-') return 1; else if(x=='(')return 0; else return -1; } int icp(char x) // 返回读入运算符的优先级(in-coming priority) { if(x=='*'||x=='/')return 2; else return 3; void postfix(char *e) // 将中缀式e转换为后缀式输出

32 { char y, x= *e; sqStack<char> stack ;
stack.Push(‘#’); // 栈底予置一“#” while(x!=‘\0’) // x不是“空白符”(结束符) { if(x==‘)’) // 判断x是右括号吗？ 是则执行退栈, 直到 '(' do{ stack.GetTop(y); stack.Pop(); if(y!='(') ofile.put(y); }while(y!='('); else // x不是右括号, 判是其它运算符？不是,则输出(操作数) if (x!=‘(’&&x!=‘+’&&x!=‘-’&&x!=‘*’&&x!=‘/’) ofile.put(x); else // x是运算符

33 { do{ // 栈顶算符优先级>=读入算符优先级, 则弹 //出算符//栈的运算符并输出
stack.GetTop(y); // 取栈顶算符 if(isp(y)>=icp(x)) // 弹出算符 { ofile.put(y); Stack.Pop(); } else break; }while(true); stack.Push(x); // 刚刚读入运算符进栈 } //end_if(x!='(' … e++; x=*e; // 取表达式e的下一符号 } // 结束while(x!='\0')循环 while(stack.GetTop(x), stack.Pop(),x!=‘#’) ofile.put(x); // 输出栈中其余运算符 (#不输出) }

34 3.3 栈与递归 递归（recursion）是最常用的算法设计思想，采用递归 的方法来编写求解程序，使程序非常简洁而清晰，本节重点 讨论递归在计算机内的实现，以及怎样把一个递归的子程序 变换成一个等价的非递归的子程序，读者将会看到，在这里 起关键作用的是栈。 3.3.1 栈的定义及其运算 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。

35 在以下三种情况下，常常用到递归方法。 ⑴ 定义是递归的；如，我们熟悉的Factorial函数,Ackerman函数，Fibnocci函数等。 ⑵ 数据结构是递归的；例如，单链表结构，每个结点 的next域指向的仍然是单链表的结点。我们后面将要 学习的二叉树、广义表等数据结构，它们的定义就是 递归的（具有固有的递归特性）因此自然采用递归方 法进行处理。

36 ⑶ 问题的解法是递归的。 例如，汉诺塔(Tower of Hanoi)问题传说婆罗门庙 里有一个塔台，台上有三根标号为A,B,C的用钻石 做成的柱子，在A柱上放着64个金盘，每一个都比 下面的略小一些。把A柱上的金盘全部移到C柱上的 那一天就是世界末日。移动的条件是：一次只能移 动一个金盘，移动过程中大金盘不能放在小金盘上 面。庙里的僧人一直在移个不停。因为全部的移动 是264 -1次，如果移动一次需要一秒的话，需要500 亿年。

37 用递归方法求解问题是将一个较复杂的（规 模较大）的问题转换成一个与原问题同类型 的稍简单（规模稍小）的问题来解决，使之 比原问题进了一步（更靠近边界条件一步）， 直至到达边界条件（直接求解，不再递归）。

38 递归子程序的实现 要理解递归算法，就必须了解计算机内递归是如何实现的？我们通过例子说明之。 【例3.3】汉诺塔问题：设需移动的金盘数为n（问题的规模），当n=1时，只要将编号为1的金盘从柱A直接移至柱C即可；当n>1时，需利用柱B作辅助柱子。

39 算法思路：若能设法将压在编号为n的金盘之上的n-1个金盘从柱A依照上述法则移至柱B；则可先将编号为n的金盘从柱A移至柱C，然后再将柱B上的n-1个金盘依照上述法则移至柱C。而如何将n-1个金盘从一个柱移至另一个柱的问题是一个和原问题具有相同特征属性的问题，只是问题的规模小了1；因此可以用同样的方法求解。

40 void Hanoi(int n, char A, char B, char C)
{ if(n= =1) cout<<”move disk 1: “<<A<<”→”<<C; // 将1号盘从A移到C else { Hanoi(n-1,A,C,B); // 将A上编号为1~n-1的盘移至B上, C 用作过渡 cout<<”move disk “<<n<<“: “<<A<<“→“<<C; // 将n号盘从A移到C Hanoi (n-1,B,A,C); // 将B上编号为1~n-1的盘移至C上, A 用作过渡 }

41 图 3.8显示了问题规模n=4时Hanoi塔问题的调用过程

42

43 和汇编程序设计中主程序和子程序之间的链 接和信息交换相类似，在高级语言编制的程 序中，主调程序和被调子程序之间的链接和
显然，递归算法Hanoi在执行过程中，需多次调 用它本身。那末，递归子程序是如何执行的呢？ 和汇编程序设计中主程序和子程序之间的链 接和信息交换相类似，在高级语言编制的程 序中，主调程序和被调子程序之间的链接和 信息交换也须通过栈来进行。

44 ① 将所有的实在参数、返回地址等信息传递 给被调子程序保存； ② 为被调子程序的局部变量分配存储区； ③ 将控制转移到被调子程序的入口。
通常，当程序在运行期间调用另一个程序时，在运行 被调程序之前，系统必须完成3件工作： ① 将所有的实在参数、返回地址等信息传递 给被调子程序保存； ② 为被调子程序的局部变量分配存储区； ③ 将控制转移到被调子程序的入口。

45 ① 保存被调子程序的计算结果： ② 释放被调子程序的数据区； ③ 恢复被调子程序保存的返回地址将控制转 回到主调程序。
而从被调子程序返回主调程序之前，系统也应完成 3件工作： ① 保存被调子程序的计算结果： ② 释放被调子程序的数据区； ③ 恢复被调子程序保存的返回地址将控制转 回到主调程序。 当有多个程序间构成嵌套调用时，按照“后调用先返 回”的原则。

46 上述程序之间的信息传递和控制转移必须通过“栈”
来实现； 即系统将整个程序运行时所需的数据空间安排在一 个栈中。每当调用一个程序时，就为它在栈顶分配 一个存储区；每当退出一个程序时，就释放它的存 储区；则当前正运行程序的数据区必然在栈顶。 递归程序的运行子程序类似于例3.1中多个程序的嵌 套调用；只是主调程序和被调子程序是同一个程序而 已。

47 3.3.3 递归技术相关问题 ⒈ 递归与分治法 分治法的思想：将一个难以直接解决的大问题，分割成
递归技术相关问题 ⒈ 递归与分治法 任何一个可用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。 分治法的思想：将一个难以直接解决的大问题，分割成 一些规模较小的相同问题，以便各个击破，分而治之。

48 如果原问题可分割成k个子问题(1<k≤n)，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么分治法就是可行的。
由分治法产生的子问题往往是原问题的较小模式， 这就为使用递归技术提供了方便。在这种情况下，反 复应用分治手段，可以使子问题与原问题类型一致而 其规模却不断缩小，最终使子问题缩小到很容易直接 求出其解。这自然导致递归过程的产生。分治与递归 像一对孪生兄弟，经常同时应用在算法设计之中，并 由此产生许多高效算法。

49 ⒉ 递归与迭代 例如，求解阶乘函数的递归算法如下： 递归与迭代都是基于程序设计语言的控制结构，迭代用重复结构，递归用选择结构。
long Factorial (long n) { if(n==0) return 1; else return n*Factorial(n-1);　 }

50 任何能用递归解决的问题也能用迭代方法解决。
迭代算法如下： long Factorial (long n) { long i , p = 1; for (i=2; i<=n; i ++) p*=i; return p ;　 } 任何能用递归解决的问题也能用迭代方法解决。

51 递归方法能更自然地描述问题，使算法容易理解和调试 （可读性好）；但是递归方法要耗费更多的时间与空间
究竟应当如何选择递归和迭代呢？我们将两种方法做个比较。 递归方法能更自然地描述问题，使算法容易理解和调试 （可读性好）；但是递归方法要耗费更多的时间与空间 （效率低）；迭代方法发生在函数(子程序)内部，不需 进行“转子、返回”及“参数压栈”等操作，因此时空 效率高。 一般对于象斐波那契数列和阶乘阶乘这样一些单向递归和尾递归 可直接用迭代方法，而没有明显迭代方案的如阿克曼函数，汉诺 塔问题还是应当采用递归方法，如果一定要转换为非递归算法， 则必须借助于栈实现，有兴趣的读者可参看参看文献[1]。

52 【例3.4】 在8*8的国际象棋上摆放八个皇后，使其不能互相攻击,即任意两个皇后不能处于同一行、同一列或同一斜线上，问有多少种摆法。
下面，我们就十九世纪著名的数学家高斯1850年提出的“八皇 后问题” 分别用递归与迭代方法给出源程序，做为本小节的 应用例。 【例3.4】 在8*8的国际象棋上摆放八个皇后，使其不能互相攻击,即任意两个皇后不能处于同一行、同一列或同一斜线上，问有多少种摆法。 // 递归回溯算法 #include <fstream.h> int sum=0, x[9]; // x[1] ~ x[8]存放当前解, // x[i] = j表示第i行的皇后放在第j列 。

53 ofstream out("QueenOUT.dat"); // out声明输出流 //(文件) out并打开之
void Backtrack(int); // 递归回溯法原型声明 void main(void) { Backtrack(1) ; // 主调函数从Backtrack(1)开始//回溯法 out<<“\nThe number of solution Queen is ”<<sum<<endl; //输出可行解的总数 out.close(); }

54 bool Place(int k) // 检测k皇后能否放在x[k]列 (是//否与以前的皇后不能相互攻击)
{ for(int j=1; j<k; j++) if((abs(kj)==abs(x[j]x[k]))||x[j]==x[k]) return false; return true; } void Backtrack(int i) //递归回溯法 { int j ; if(i>8) //找到一组解，输出 { for(j=1; j<=8; j++)out<<" "<<x[j] ; out<<endl ; sum++;

55 for(j=1; j<=8; j++) // 在循环中递归调用, 对每一皇后都测试了所有位置, 因此 // 可得到所有解 { x [i] = j ; if(Place(i))Backtrack(i+1); //确定当前皇后的位置, 找下一皇后位置 } //迭代回溯算法 #include <math.h> #include <fstream.h>

56 void Backtrack(); // 找出所有解并输出之的函数, 原 // 型声明
int x[9]; void main() // 主函数仅仅调用Backtrack() , 注意 // Backtrack() 没有参数 { Backtrack(); } bool Place(int k) // 检测k皇后能否放在x[k]列(是否 // 与以前的皇后不能相互攻击) { for(int j=1; j<k; j++) if((abs(k-j)==abs(x[j]-x[k])) || x[j]==x[k]) return false; return true; }

57 void Backtrack() //迭代回溯
{ ofstream out("QueenOUT.dat"); int k=1, sum=0; while (k > 0) // 若k==0，则已搜索完所有的解, // 结束回溯 { x[k]++; // 列号增1, 为k皇后测试下一位置 while((x[k]<=8) && !(Place(k))) x[k]++; if(x[k]<=8) // 确定了皇后的位置 if(k==8) //找到一组解，输出 { sum++; for(int i=1; i<=8; i++)out<<“ "<<x[i]; out<<endl; }

58 else x [++k]=0; // k增1, 为下一皇后找安 // 全的位置, 注意x [k]=0, 为什么?
else k--; // 回溯 } out<<"\nThe number of solution Queen is "<<sum<<endl; out.close(); 该算法得到了92组可行解，但实际上只有12组不同构的解（随书 光盘给出了12组解图，由于篇幅关系，这儿不再画出），其余的 解可以从这12组解经旋转或左右对称变换得到。

59 3.4 队列 3.4.1 队列的定义及其运算 队列(Queue)是限定只能在表尾插入元素，而在表头删除元素的线性表。
3.4 队列 队列的定义及其运算 队列(Queue)是限定只能在表尾插入元素，而在表头删除元素的线性表。 这和我们日常生活中的排队是一致的，最早进入队列的元素最 早离开。因此也称其为：先进先出（First In First Out，缩 写为FIFO）表。 允许插入的一端叫做队尾， 允许删除的一端则称为队头。

60 假设队列为:Q = (a1，a2，…，an)，那么，a1就是队头
元素，an则是队尾元素。队列中的元素是按照a1，a2， …，an的顺序进入的，退出队列也只能按照这个次序依 次退出，也就是说，只有在a1，a2，…，an-1都离开队 列之后，an才能退出队列。 图3.9是队列的示意图。

61 队列在程序设计中也经常出现。 一个最典型的例子就是操作系统中的作业排队。在允 许多道程序运行的计算机系统中，同时有几个作业运 行。如果运行的结果都需要通过通道输出，那就要按 请求输出的先后次序排队。每当通道传输完毕可以接 受新的输出任务时，队头的作业先从作业队列中退出 做输出操作。凡是申请输出的作业都从队尾进入队列。

62 队列的ADT声明如下： ADT Queue { Typedef struct Stack Q; InitStack(Q,maxSize);
QueueSize(Q); 说明：队列中元素的数目 isEmpty(Q); 说明：判队列Q是否为空 isFull(Q); 说明：判队列Q是否已“满” GetFront(Q,e); 说明：取队头元素 EnQueue(Q,e); 说明：值为e的数据元素进入队列 Del Queue(Q); 说明：队头元素出队（删除） };

63 顺序队列－－队列的顺序存储结构 队列的顺序存储结构称为顺序队列。与顺序栈相同顺序队列也是用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置均是变化的，因而要设置两个指针，分别指示当前队头元素和队尾元素的位置。 规定：队头指针总是指向当前队头元素的前一个位置 队尾指针指向当前队尾元素的位置

64 初始，队头和队尾指针均指向向量空间的前一个置。
图3.10说明了顺序队列中出队和入队运算时队列中 的元素及其头尾指针的变化状况。

65 我们先以整数元素为例，给出顺序队列的基本运算的 实现代码。
Typedef struct { int *elem; // elem是数据元素数组，初始化操作InitStack(Q)中分配存储空间 int front, rear; // 队头，队尾指针 int maxSize; // 初始化操作InitStack (S)中为栈分配单元数// （栈容量） }sqStack; void InitStack(Q, maxSize) // 队列初始化 { Q.front=Q.rear=-1; Q.elem=new int[maxSize]; }

66 bool isEmpty(Q) // 判队列空否？
{ return Q.front==Q.rear; } bool isFull(Q) // 判队列满否？ { return Q.rear==Q.maxSize-1; } Bool EnQueue(sqStack Q, int x) // 值为x的数据//元素进队列(插入) { if(isFull(Q)) // 队列满（溢出）无法进队列, 返回// false { cout << " ERROR: overflow !!\n"; return false ; } Q.elem[++Q.rear]=x; return true; // 队尾指//针增1元素进队列, 返回true }

67 bool DelQueue()(sqStack Q) // 队头元素出队(删除)
{ if(isEmpty(Q)) // 队列空（下溢）无法删除, 返回// false { cout << " ERROR: underflow !!\n"; return false; } Q.front++; return true; // 队头指针增1, 元//素出队列,返回true } bool GetFront(sqStack Q, int &e) // 取队头元素 { if(isEmpty(Q)) // 队列空（下溢） e=Q.elem[Q.front+1]; return true ; // 元素//存e, 队头指针不变(元素没出队列)

68 由上面的算法可看出空队列的判定条件为 front==rear。
而值得考虑的是队列满（即上溢）的判定条件是什么？ 假设当前队列处于图3.10(d)的状态。即MaxSize=5， rear=4，front=2，因为rear==maxsize-1，故此时 不能作入队操作，但当前队列并不满，我们把这种 现象称为“假上溢”。 产生该现象的原因是被删元素的空间永远使用不到

69 一个较巧妙的办法方法是：将 *elem设想成一个首尾相接的圆环，即：elem[0]接在elem [MaxSize-1]之 后。
为克服这一缺点，可以在每次出队时将整个队列中的元素向前移 动一个位置，也可以在发生假上溢时将整个队列中的元素向前移 动直至头指针为零。但这两种方法都会引起大量元素的移动，所 以在实际应用中很少采用。 一个较巧妙的办法方法是：将 *elem设想成一个首尾相接的圆环，即：elem[0]接在elem [MaxSize-1]之 后。 我们将这种意义下的向量称为循环向量，并将循环向量中的队 列称为循环队列(Circular Queue)。 如图3.11所示。

70 当rear == MaxSize -1时，若要做入队操作时，只要elem[0]是
算来实现循环队列的运算。 入队为: rear = (rear+1) % MaxSize ; elem [rear] = x ; 出队为： front = (front+1) % MaxSize ;

71 在循环队列中如何判别队满和队空？ 由图3.11(b)、(c)看出，当队列空时，头、尾指针指向了队列中的同一位置；而队列满时，头、尾指针亦指向同一位置。因此，只凭等式front == rear不足以判别循环队列的状态是“空”还是“满”。 对此，有两种解决办法: 一是另设一个标志位，以区别队“空”还是队“满”； 另一较简单的办法是不设标志位，而把“尾指针从后面追上 头指针”当作队满时的特征。即 如果 (rear+1) % MaxSize == front则认为队满，不能进队 （此时队列中尚留有一个空额）。这样虽损失了一个空间， 但避免了判另外设的标志而造成的时间上的损失。

72 循环队列的模板类接口定义以及基本运算的实现代码 如下：
template <class T> class sqQueue { protected: int *elem; //elem是指向存放数据元素的数组指 // 针 int front, rear; // 队头，队尾指针 int maxSize; // 队列的容量 public: sqQueue(int ms=10); // 构造函数 sqQueue(const sqQueue<T>&);// 复制构造函数 ~sqQueue(){ delete[] elem; } // 析构函数 sqQueue& operator=(const sqQueue<T>&); // " = " 运//算符重载

73 bool isEmpty() // 判 队列 " 空 " //否？
{ return front==rear; } bool isFull() // 判 队列 " 满 " 否？注意: 当 // 队尾指针将追上头指针时, 报“满” { return (rear+1)%MaxSize==front; } bool EnQueue(T); // 进队 (插入) bool EnQueue(); // 出队 (删除) bool GetFront(T &); // 取队头元素 }; template <class T>sqQueue<T>::sqQueue(int ms) //构造“空” 队列 { if (ms<=0) { cout<<"ERROR:invalid MaxSize!!\n"; return; } elem = new T [ms];MaxSize=ms; front=rear=0; }

74 template <class T>bool sqQueue<T>::EnQueue(T x)
{ if(isFull()) // 队列满（溢出） { cout<<" ERROR: overflow !!\n"; return false; } rear=(rear+1)%MaxSize; // 队尾指针模MaxSize加1 elem[rear]=x; // 元素x进队 return true; } template <class T>bool sqQueue<T>::DelQueue() // 队头元素出队 { if(isEmpty()) // 队空（下溢） { cout<<" ERROR: underflow !!\n"; return false;

75 front=(front+1)%MaxSize;//队头指针模MaxSize加1
return true; } template <class T>bool sqQueue<T>::GetFront(T &e) // 取队头元素 { if(isEmpty(S)) // 队列空（下溢） { cout<<" ERROR: underflow !!\n"; return false; } e=elem [(front+1)%MaxSize]; //元素存e, 队头指针 // 不变(元 // 素没出队列) Template<classT>sqQueue<T>::sqQueue(const sqQueue<T>& obj) // 由顺序队列obj复制构造新队列 { MaxSize=obj.MaxSize; // 被构造队列与obj容量应相同

76 elem=new T[MaxSize]; // 申请空间
Front=obj.front; rear=obj.rear; // 头、尾指针赋值 int f=(front+1)% MaxSize; // 计算队头元素的位置 for( intj=f; j!=rear; j=(j+1)%MaxSize ) elem[j] = obj.elem[j]; // 复制队中除了队尾元素 (j==rear时) 外的其余数据元素 elem[j]=obj.elem[j]; // 复制队尾元素 } template<classT>sqQueue<T>&sqQueue<T>::operator=(const sqQueue<T>&origin) // "=" 运算符重载 , 请读者自己完成 { … }

77 3.4.3 链队列－－队列的链式存储结构 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。
链队列－－队列的链式存储结构 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。 显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表上的最后一个结点。于是，一个链队列由一个头指针和一个尾指针唯一地确定。 链队列的模板类可以继承单链表的模板类LinkedList（增加一 个数据成员rear），读者可以参考第2章中单链表类的实现部分 完成链队列的实现代码。

78 图3.12所示为无头结点的链队列，图3.13则表示带有头结点的链队列。

79 3.5 应用实例 ⒈ 问题描述 在我们日常生活中经常会遇到许多为了维护社会正常秩序而需要
3.5 应用实例 在我们日常生活中经常会遇到许多为了维护社会正常秩序而需要 排队的情况。这样一类事情的模拟程序通常要用到队列和线性表 这一类数据结构，因而是队列应用例子之一。在此，向读者介绍 一个银行业务的模拟程序。 ⒈ 问题描述 假设某银行有4个窗口对外接待客户，从早晨开门起不断有客户 进入银行。由于每个窗口只能接待一个客户，因此在客户人数众 多时需在每个窗口前顺序排队，对于刚进入银行的客户，如果某 个窗口的业务员正空闲，则可上前办理业务；反之，若4个窗口 均有客户所占，他便会排在人数最少的队伍后面。现在需要编制

80 ⒉ 数据结构 一个程序以模拟银行的这种业务活动，并计算一天中客户在银行 逗留的平均时间。
分析：为了计算平均时间，我们需要知道每一客户到达银行和离 开银行这两个时间，后者减去前者即为每个客户在银行逗留的时 间。所有客户逗留时间的总和被一天内办理业务的客户数除便是 所求的平均时间。每个客户到达银行的时间是自然形成的，而离 开银行的时间则和银行的整个对外业务活动有关。假设客户到达 后即刻办理业务，则他在银行逗留的时间即为他办理业务所需的 时间；否则尚需加上他排队等候的时间。

81 ⑴ 队列及队列的头结点数组 因此，应当采用的数据结构为： 用4个队列表示4个窗口前的客户排队情况。
由于队列中的最大元素无法预测，而且长度变化较大，故采用单 链表作存储结构为宜。链表中每个结点包含两个数据域： arrivetime和duration（分别表示客户到达银行的时间和办理业 务所需的时间）（如图3.14(a)所示）。 为便于查找最短队列，将有关每个队的信息（由三个域组成： front，rear和num）另组成一个数组，图3.14(b)是初始化时设 置4个队列均为“空”的情况。

82

83 模拟时，每个队列中的队头元素表示正被银行业务员接待的客户。有5种情况的发生会使队列发生变化：①新的客户进入银行，他将加入人数最少的队列而成为该队列的队尾元素；②、③、④、⑤分别是0、1、2、3号窗口的客户办理完业务离开银行，则紧排在其后面的客户开始被接待，成为新的队头元素。 我们把上述5种情况的发生称作事件，并按事件发生的先后构成 一个事件表。在任何时刻，事件表中至多只有5个元素，表示即 将发生的5类事件。其一表示有某个客户到达银行（除了银行关 门不再有客户进入），另4个则表示正在4个窗口办理业务的客 户将在某个时刻离开银行。整个模拟程序就是按时间先后一个接 一个处理这些事件。这样一种模拟程序称为离散事件驱动模拟。

84 ⒊ 事件驱动模拟的过程 ⑵ 事件表 模拟的过程是按照时间先后顺序一个接一个处理事件 表中的事件，直到事件表为“空”。
由于事件需按事件发生的先后有序，且每一时刻事件表中最多有 5个元素，因此用大小为5的有序顺序表存储即可。 ⒊ 事件驱动模拟的过程 模拟的过程是按照时间先后顺序一个接一个处理事件 表中的事件，直到事件表为“空”。 那么应当如何处理事件呢？可以将5种类型的事件分为两个处理 子程序：

85 ① 该客户办理业务所需时间； ②下一客户将到达银行的时间间隔。 ⑴ 处理类型为4的“客户到达”事件：首先应得到两个时间：
此时模拟程序应做的工作是： ①比较4个队列中的元素个数，将新到客户加入到元素个数最少 的队列中成为新的队尾元素。若刚进队的元素是这个队列的队头 元素（已经开始办理业务），则还应设定“该客户办理完业务离 开银行”的事件插入事件表； ②设定一个新的事件 -- 下一个客户即将到达银行的事件插入事 件表；

86 ⑵ 处理类型为 i∈{0,1,2,3} 的“某客户在i号队列
办理完业务离开银行”事件。 这时，程序需做的工作是： ①该客户出队列，并计算他在银行逗留的时间； ②当i号队列非空时，计算新的队头元素将离开 银行的时间，并由此设定一个新的离开事件插 入事件表。

87 ⒋ 算法实现 #include <fstream.h> #include <iomanip.h>
#include <stdlib.h> #include <time.h> #include "SQList.h" #include <iostream.h> struct qnode { int arrivetime,duration; // 队列中结点结构 qnode *next; }; struct queue { qnode *front,*rear; // 队列数组元素结构 int number;

88 class evenData // 事件表的数据域
{ protected: int occurtime; // 事件发生的时间 int ntype; // 事件类型 public: void GetData(int &t, int &i) // 获得事件表中数据元素的数据域 { t=occurtime, i=ntype; } void SetData(int t, int i) // 设置事件表中数据元素的数 据域 { occurtime=t, ntype=i; } bool operator>(const evenData& right) // ">"运算符重 // 载 { return occurtime < right.occurtime; } };

89 // 注意：由于事件表要求有序，因此要重载运算符" >" (插入到有序表中的元素比较符号)
// 模拟中总要从事件表中删除“时间值小”的事件，为了删除时不移动元素，我们让 // 事件表中元素按“时间值”从大到小排列，这样，最早发生的事件排在表尾。 int closetime,dut,interval; queue q[4]; // 队列数组 void simulate(); // 模拟程序原型声明 void main() // 主函数 { time_t st; srand((unsigned)time(&st)); //初始化随时间变化的随机数种子 simulate(); // 调用模拟程序 }

90 int shortq() //返回最短队列的序号函数, 被模拟程序调用
{ int i, j, m=32767; for(i=0; i<4; i++) if(q[i].number<m) { m=q [i].number; j=i; } return j; } void EnQueue(int i, int octime, int dutime) // 向第i个队列中加入一个结点 { qnode *p; p=new qnode; p->arrivetime=octime; p->duration=dutime; p->next=NULL; if(q [i].number= =0) q [i].front=p; else q [i].rear->next=p; q [i].number ++; q [i].rear = p;

91 qnode *DelQueue(int i) // 从第i个队列中删除一个结 // 点，返回指向该结点的指针
{ qnode *p; if(q[i].fnumber==0) { cout<<"ERROR: queue "<<i<<"empty !\n"; return NULL; } else {p=q[i].front; q[i].front=q[i].front->next;} q[i].number--; return p; } void simulate() // 模拟程序 { sqList<evenData> ev(5); evenData e; int totaltime=0,count=0,waitime=0; int t,y,dutime,intime,i,j,c=0;

92 cout<<"请输入3个整数: 模拟时间 处理业务时间 客户到
达间隔: "; cin>>closetime>>dut>>interval; ofstream out("simulate.out"); // 建立并打开输 // 出文件流out out<<"closetime="<<closetime; // 输出结果表 // 的表头 out<<" dutime="<<dut<<"inteval="<<interval; out<<"\n\neveno.occurtimetypeq[i]duration interval(arrive)time"; out<<"\n \n"; for(i=0; i<4; i++) //初始化队列数组 {q[i].front=q[i].rear=NULL; q[i].number=0;} // 将第一个客户到达事件插入事件表，以此驱动模拟开始 e.SetData(0,4); ev.InsertNode(e);

93 while(!ev.isEmpty()) // 事件表不空，则继续模拟
{ ev.DeleteNode(ev.Length(),e); // 从事件表ev删除(表尾)结点存入e e.GetData(t,y); // 将当前事件的发生时间存入t,类型存入y out<<setw(6)<<++c<<setw(9)<<t<<setw(5)<<y; // 输出当前事件 if( y==4 ) // 模拟客户到达事件 { // 产生两个随机数,分别是该客户处理业务所需时 // 间和下一客户到达的间隔时间. count++; dutime=(rand()%dut+3); ntime=(rand()%interval+1); if((j=t+intime)<closetime) // 在关门 // 之前到达， 则生成

94 { e.SetData(j,4); ev.InsertNode(e); } // 客户到达//事件插入表
i=shortq(); EnQueue(i,t,dutime); // 把当前到达客户插入最短队列 out<<setw(4)<<i<<setw(10)<<dutime <<setw(9)<<intime<<endl; if(q[i].number= =1) //生成队头元素离队事件 {e.SetData(t+dutime,i); ev.InsertNode(e); } } else // 当前处理事件是客户离队事件y∈{0,1,2,3} { qnode *f=DelQueue(y); // 处理y号队列的 // 离队事件 j=t-f->arrivetime; totaltime+=j;

95 waitime+=(j-f->duration);
out<<setw(14)<<f->duration<<setw(17) <<f->arrivetime<<endl; delete f;//释放离队客户所占用的队列结点空间 if(q [y].fnumber>0) // 若第i个队列客户离 // 队后队不空,生成新的离队事件 {e.SetData(t+q[y].front->duration,y); ev.InsertNode(e); } } // end_if__else } // end_while out<<" \n"; out<<"total time="<<totaltime<<"customer =“ <<count<<endl; out<<"The average cost time is“ <<totaltime*1.0/count<<endl;

96 out<<"The average wait time is“
<<waitime*1.0/count<<endl; out.close(); }

97