第 3章 栈与队列
目录
1.栈
2,栈的 应用举例
3,栈与递归
4,队列
5,应用实例
3.1 栈
3.1.1 栈的定义及其运算
栈 （ Stack） 是限定插入和删除运算只能在表尾
进行的线性表。
通常称允许插入、删除的这一端为栈顶，另一端
称为栈底。
当表中没有元素时称为空栈。
其中数据元素的个数 n定义为表的长度。
图 3.1是一个栈的示意图，通常用指针 top指示栈顶的位
置，用指针 bottom指向栈底。栈顶指针 top动态反映栈
的当前位置。
图 3.1所示的栈中，元素是以 a1，
a2,…, an的顺序进栈，而出栈
的次序却是 an,an-1,…, a1。
也就是说，栈的修改是按后进先
出的原则进行的。 因此，栈又称为
后进先出（ Last In First Out）的线性表，简称为
LIFO表。
ADT Stack
{ Typedef struct Stack S;
InitStack(S,maxSize);
说明：构造空栈 S,即栈的初始化
StackSize(S);
说明：求栈中元素的数目
isEmpty(S);
说明：判栈 S是否为空栈
isFull(S);
说明：判栈 S是否已, 满,
栈的 ADT声明如下,
GetTop(S,e);
说明：取栈顶元素
Push (S,e);
说明：值为 e的数据元素进栈 （ 插入, 压栈 ）
Pop(S);
说明：栈顶元素出栈 （ 删除, 退栈 ）
};
栈的顺序存储结构称为顺序栈, 是用一组地址连续的
存储单元依次存放自栈底到栈顶的数据元素 。
3.1.2 栈的顺序存储结构
因为栈底位置是固定不变的, 栈顶位置是随着进栈和退栈
操作而变化的, 故需用一个变量 top来指示当前栈顶位置,
通常称 top为栈顶指针, 参看图 3.2。
Typedef struct
{ int *elem; // elem是数据元素数组
int top; // 栈顶指针
int maxSize; // 栈容量
}sqStack;
我们先以整数元素为例，给出顺序栈的基本
算法，在下一节，将给出顺序栈的模板类接口
定义以及基本运算的实现代码和应用实例。
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; }
boolPush (sqStack S,int e)
// 值为 e的数据元素进栈 (插入, 压栈 )
{ if(isFull(S)) // 栈满 （ 溢出 ） 无法进栈,返回 false
{ cout << " ERROR,overflow !!\n";
return false; }
S.elem[++S.top] = e ; return true ;
//栈顶指针增 1元素进栈,返回 true
}
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)) // 栈空 （ 下溢 ）
{ cout <<, ERROR,underflow !!\n” ;
return false ; }
e=S.elem[S.top] ; return true ;
// 元素存 e,栈顶指针不变 (元素没出栈 )
}
栈的使用非常广泛，常常会出现在一个程序中需要
同时使用多个栈的情形。为了不因栈上溢而产生错
误中断，要给每个栈预分较大空间，但各个栈实际
所用最大空间很难估计。而且各个栈的实际容量在
使用期间是变化的，往往会出现某个栈发生上溢，
而另一个栈还是空的。
试 设想,若令多个栈共享空间，则将提高空间的使
用效率，并减少发生栈上溢的可能性。
假设在程序中需设两个栈，并共享一维数组空间 v[m]。
则利用, 栈底位置不变, 的特性，可将两个栈的栈底分
别设在数组空间的两端，然后各自向中间伸展（如图 3.3
所示），仅当两个栈的栈顶相遇时才可能发生上溢。由
于两个栈之间可以做到互补余缺，使得每个栈实际可利
用的最大空间大于 m/2。显然，两个栈顶的初值分别为 -1
和 m。
栈的链式存储结构称为链栈, 它是运算受限的单链表,
其插入和删除操作仅限制在表头位置上进行 。
3.1.3 栈的链式存储结构
由于只能在链表头部进行操作，
故链栈没有必要象单链表那样
附加上头结点。栈顶指针就是
链表的头指针，如图 3.4所示，
链栈就是无头结点的单链表
（头指针改称栈顶指针），因
此不再重新讨论。
3.2 栈的应用举例
栈的应用非常广泛，只要问题满足 LIFO原则，均可使
用栈做数据结构。
//顺序栈的模板类接口定义以及基本运算的实现代码
template <class T> class sqStack
{ protected:
int *elem ; // 指向存放数据元素的数组指针
int top ; // 栈顶指针
int maxSize; // 栈容量
public:
sqStack(int ms=10); // 构造函数
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 &); // 取栈顶元素
};
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;
}
template <class T>bool sqStack<T>::Pop()
//栈顶元素出栈,被删元素存 e
{ if(isEmpty()) // 栈空 （ 下溢 ）
{ cout <<, ERROR,underflow !!\n” ;
return false; }
top--; //栈顶指针减 1(元素出栈 )
return true;
}
template <class T>bool sqStack<T>::GetTop(T &e)
// 取栈顶元素
{ if(isEmpty(S)) // 栈空 （ 下溢 ）
{ cout <<, ERROR,underflow !!\n” ;
return false; }
e=elem [top]; // 元素存 e,栈顶不变 (元素没出栈 )
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]; // 复制数据元素
}
template<classT>sqStack<T>&sqStack<T>::operato
r=(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]; //复制数据元素
}
【 例 3.1】 用栈实现程序设计语言中的子程序调用
和返回 。
假设有一个主程序 main和三个子程序 A1,A2和 A3，
其调用关系如图 3.5所示 。
从图 3.5可知，主程序 main调用子程序 A1，子程序 A1完成之
后，返回到主程序的 r处继续执行。但是，因为子程序 A1又调
用了子程序 A2，所以在 A2执行完毕并返回之前,A1是不可能
结束的。类似地,A2也必须在 A3执行完毕并返回之后才能从
t处继续进行。其调用与返回的过程如图 3.6所示。
显然，调用次序和返回次序是
相反的，最后调用到的子程序
最先返回。为了保证各个被调
用子程序能正确地返回，可以
在程序运行期间设置一个工作
栈来保存返回地址 。
当调用某一个子程序时，将该子程序的返回地址进栈；当
某一子程序执行完毕时将当前栈顶的返回地址出栈，并按
该地址返回。注意，某一子程序 P执行完毕，当前栈顶内
容一定是 P的返回地址。因为只有当执行 P时所调用的其它
子程序都已返回,P才能结束，这就保证了当 P返回时，其
相应的返回地址正好是在当前栈顶，参看图 3.7。
【 例 3.2】 表达式转换 （ 中缀表达式改写成后缀表
示法 ）
算术表达式有 三种表示方法, ⑴ <操作数 > <操作符 > <操作
数 >,如 A+B,称为中缀 (infix)表示； ⑵ <操作符 > <操作数
> <操作数 >,如 +AB称为前缀 (prefix)表示； ⑶ <操作数 > <
操作数 > <操作符 >,如 AB+,称为后缀 (postfix)表示 。
在后缀表达式中, 没有括号, 也不存在优先级的差别, 计算
过程完全按照运算符出现的先后次序进行, 整个计算过程仅
需一遍扫描便可完成, 显然比中缀表达式的计算要简单得多 。
因此, 程序设计语言的编译系统要将通常的中缀表达式转换
成后缀表达式
例如, A*(B+C)的后缀表达式是 ABC+*,因 ’ +’ 运算符
在前, ’ *’ 运算符在后, 所以应先做加法, 后做乘法 。
再如, 表达式 A/B*C+D*(E-A)+C/(D*B) 的后缀形式是
AB/C*DEA-*+CDB*/+,
怎样设计算法把运算符放在两个运算对象中间的中缀表达
式转换为后缀形式呢？
观察一下两种形式的表达式，我们注意到操作数在两种形
式中出现的次序是相同的。所以在扫描表达式时，凡遇到
操作数就马上输出，剩下的事情就是处理所遇到的运算符。
解决的办法是把遇到的运算符存放到栈中，直到某个适当
时刻再将运算符退栈并输出。
我们来看两个例子：
（ 1） 要由表达式 A+B*C产生出后缀表达式 ABC*+,必
须按照如表 3.1所示的操作顺序执行 （ 栈向右增长 ） 。
到达第 4步时必须确定是 ’ *’ 进入栈顶, 还是 ’ +’
退栈；由于 ’ *’ 的优先级更高, 应该是 ’ *’ 进栈,
从而产生第 5步；现在已从表达式中取完所有的符号,
于是我们输出运算符栈中所有剩余的运算符得到：
ABC*+
（ 2） 表达式 A*(B+C)/D 的后缀形式为 ABC+* D/，
当遇到左括号时必须入栈, 遇到右括号时, 必须依次
把栈中元素退栈 。 直到相应的左括号为止, 然后去掉
左右括号 。 如表 3.2所示 。
这些例子启发我们, 算术运算符和括号可用如表
3.3所示分级方案实现 。 其规则是：
只要运算符在栈中的优先级 isp(in-stack priori
ty)大于或等于新运算符进来时的优先级 icp(in-c
oming priority)，则运算符就从栈中取出。
isp(x)和 icp(x)是函数，它们返回运算符按上述
给定的优先级值。
//将表达式的中缀形式转换为后缀形式
#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; }
具体算法如下：
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
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();
}
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 if(x=='+'||x=='-') return 1;
else return 3;
}
void postfix(char *e) // 将中缀式 e转换为后缀式输出
{ 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是运算符
{ 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); // 输出栈中其余运算符 (#不输出 )
}
3.3 栈与递归
3.3.1 栈的定义及其运算
若一个对象部分地包含它自己,或用它自己给自己定
义,则称这个对象是递归的；若一个过程直接地或间
接地调用自己,则称这个过程是递归的过程。
递归（ recursion）是最常用的算法设计思想，采用递归
的方法来编写求解程序，使程序非常简洁而清晰，本节重点
讨论递归在计算机内的实现，以及怎样把一个递归的子程序
变换成一个等价的非递归的子程序，读者将会看到，在这里
起关键作用的是栈。
⑴ 定义是递归的； 如, 我们熟悉的 Factorial函
数,Ackerman函数, Fibnocci函数等 。
在以下三种情况下，常常用到递归方法。
⑵ 数据结构是递归的； 例如，单链表结构，每个结点
的 next域指向的仍然是单链表的结点。我们后面将要
学习的二叉树、广义表等数据结构，它们的定义就是
递归的（具有固有的递归特性）因此自然采用递归方
法进行处理。
⑶ 问题的解法是递归的。
例如，汉诺塔 (Tower of Hanoi)问题传说婆罗门庙
里有一个塔台，台上有三根标号为 A,B,C的用钻石
做成的柱子，在 A柱上放着 64个金盘，每一个都比
下面的略小一些。把 A柱上的金盘全部移到 C柱上的
那一天就是世界末日。移动的条件是：一次只能移
动一个金盘，移动过程中大金盘不能放在小金盘上
面。庙里的僧人一直在移个不停。因为全部的移动
是 264 -1次，如果移动一次需要一秒的话，需要 500
亿年。
用递归方法求解问题是将一个较复杂的（规
模较大）的问题转换成一个与原问题同类型
的稍简单（规模稍小）的问题来解决，使之
比原问题进了一步（更靠近边界条件一步），
直至到达边界条件（直接求解，不再递归）。
要理解递归算法, 就必须了解计算机内递归是如何实
现的？ 我们通过例子说明之 。
3.3.2 递归子程序的实现
【 例 3.3】 汉诺塔问题：设需移动的金盘数为
n（ 问题的规模 ）, 当 n=1时, 只要将编号为 1
的金盘从柱 A直接移至柱 C即可；当 n>1时, 需
利用柱 B作辅助柱子 。
算法思路,若能设法将压在编号为 n的金盘之
上的 n-1个金盘从柱 A依照上述法则移至柱 B；
则可先将编号为 n的金盘从柱 A移至柱 C,然后
再将柱 B上的 n-1个金盘依照上述法则移至柱 C。
而如何将 n-1个金盘从一个柱移至另一个柱的
问题是一个和原问题具有相同特征属性的问
题, 只是问题的规模小了 1；因此可以用同样
的方法求解 。
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 用作过渡
c o u t < <, move d i s k, < < n < <,,
,<<A<<,→,<<C;
// 将 n号盘从 A移到 C
Hanoi (n-1,B,A,C);
// 将 B上编号为 1~n-1的盘移至 C上,A 用作过渡
}
}
图 3.8显示了问题规模 n=4时 Hanoi塔问题的调用过程
显然，递归算法 Hanoi在执行过程中，需多次调
用它本身。那末，递归子程序是如何执行的呢？
和汇编程序设计中主程序和子程序之间的链
接和信息交换相类似，在高级语言编制的程
序中，主调程序和被调子程序之间的链接和
信息交换也须通过 栈 来进行。
通常，当程序在运行期间调用另一个程序时，在运行
被调程序之前，系统必须完成 3件工作：
① 将所有的实在参数、返回地址等信息传递
给被调子程序保存；
② 为被调子程序的局部变量分配存储区；
③ 将控制转移到被调子程序的入口。
而从被调子程序返回主调程序之前，系统也应完成
3件工作：
① 保存被调子程序的计算结果：
② 释放被调子程序的数据区；
③ 恢复被调子程序保存的返回地址将控制转
回到主调程序。
当有多个程序间构成嵌套调用时，按照, 后调用先返
回, 的原则。
上述程序之间的信息传递和控制转移必须通过,栈”
来实现；
即系统将整个程序运行时所需的数据空间安排在一
个栈中。每当调用一个程序时，就为它在栈顶分配
一个存储区；每当退出一个程序时，就释放它的存
储区；则当前正运行程序的数据区必然在栈顶。
递归程序的运行子程序类似于例 3.1中多个程序的嵌
套调用；只是 主调程序和被调子程序是同一个程序 而
已。
⒈ 递归与分治法
3.3.3 递归技术相关问题
任何一个可用计算机求解的问题所需的计算时间都与其
规模有关 。 问题的规模越小, 越容易直接求解, 解题所需的
计算时间也越少 。 例如, 对于 n个元素的排序问题, 当 n=1时,
不需任何计算 。 n=2时, 只要作一次比较即可排好序 。 n=3
时只要作 3次比较即可, ? 。 而当 n较大时, 问题就不那么容
易处理了 。 要想直接解决一个规模较大的问题, 有时是相当
困难的 。
分治法的思想,将一个难以直接解决的大问题，分割成
一些规模较小的相同问题，以便各个击破，分而治之。
如果原问题可分割成 k个子问题 (1<k≤n),且这些子
问题都可解，并可利用这些子问题的解求出原问题
的解，那么分治法就是可行的。
由分治法产生的子问题往往是原问题的较小模式，
这就为使用递归技术提供了方便。在这种情况下，反
复应用分治手段，可以使子问题与原问题类型一致而
其规模却不断缩小，最终使子问题缩小到很容易直接
求出其解。这自然导致递归过程的产生。 分治与递归
像一对孪生兄弟,经常同时应用在算法设计之中，并
由此产生许多高效算法。
⒉ 递归与迭代
递归与迭代都是基于程序设计语言的控制结构, 迭代用重复
结构, 递归用选择结构 。
例如，求解阶乘函数的递归算法如下：
long Factorial (long n)
{ if(n==0) return 1;
else return n*Factorial(n-1);
}
迭代算法如下：
long Factorial (long n)
{
long i,p = 1;
for (i=2; i<=n; i ++) p*=i;
return p ;
}
任何能用递归解决的问题也能用迭代方法解决。
究竟应当如何选择递归和迭代呢？我们将两种方法做个比较。
一般对于象斐波那契数列和阶乘阶乘这样一些 单向递归和尾递归
可直接用迭代 方法，而没有明显迭代方案的如阿克曼函数，汉诺
塔问题还是应当采用递归方法，如果一定要转换为非递归算法，
则必须借助于栈实现，有兴趣的读者可参看参看文献 [1]。
递归方法能更自然地描述问题，使算法容易理解和调试
（可读性好） ；但是递归方法要耗费更多的时间与空间
（效率低） ；迭代方法发生在函数 (子程序 )内部，不需
进行“转子、返回”及“参数压栈”等操作，因此 时空
效率高 。
【 例 3.4】 在 8*8的国际象棋上摆放八个皇后, 使
其不能互相攻击,即任意两个皇后不能处于同一行,
同一列或同一斜线上, 问有多少种摆法 。
下面，我们就十九世纪著名的数学家高斯 1850年提出的“八皇
后问题” 分别用递归与迭代方法给出源程序，做为本小节的
应用例。
// 递归回溯算法
#include <fstream.h>
int sum=0,x[9]; // x[1] ~ x[8]存放当前解,
// x[i] = j表示第 i行的皇后放在第 j列 。
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();
}
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++;
}
for(j=1; j<=8; j++)
// 在循环中递归调用,对每一皇后都测试了所有位置,因此
// 可得到所有解
{ x [i] = j ;
if(Place(i))Backtrack(i+1);
//确定当前皇后的位置,找下一皇后位置
}
}
//迭代回溯算法
#include <math.h>
#include <fstream.h>
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;
}
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;
}
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组解经旋转或左右对称变换得到。
3.4 队列
3.4.1 队列的定义及其运算
队列 (Queue)是限定只能在表尾插入元素，而在表
头删除元素的线性表。
这和我们日常生活中的排队是一致的，最早进入队列的元素最
早离开。因此也称其为,先进先出（ First In First Out，缩
写为 FIFO）表。
允许插入的一端叫做 队尾,
允许删除的一端则称为 队头 。
假设队列为,Q = (a1,a2,?, an)，那么,a1就是队头
元素,an则是队尾元素。队列中的元素是按照 a1,a2，
?, an的顺序进入的，退出队列也只能按照这个次序依
次退出，也就是说，只有在 a1,a2,?, an-1都离开队
列之后,an才能退出队列。
图 3.9是队列的示意图。
队列在程序设计中也经常出现。
一个最典型的例子就是操作系统中的作业排队。在允
许多道程序运行的计算机系统中，同时有几个作业运
行。如果运行的结果都需要通过通道输出，那就要按
请求输出的先后次序排队。每当通道传输完毕可以接
受新的输出任务时，队头的作业先从作业队列中退出
做输出操作。凡是申请输出的作业都从队尾进入队列。
队列的 ADT声明如下：
ADT Queue
{ Typedef struct Stack Q;
InitStack(Q,maxSize);
说明：构造空队列 Q，即队列的初始化
QueueSize(Q); 说明：队列中元素的数目
isEmpty(Q); 说明：判队列 Q是否为空
isFull(Q); 说明：判队列 Q是否已“满”
GetFront(Q,e); 说明：取队头元素
EnQueue(Q,e); 说明：值为 e的数据元素进入队列
Del Queue(Q); 说明：队头元素出队（删除）
};
3.4.2 顺序队列－－队列的顺序存储结构
队列的顺序存储结构称为 顺序队列 。与顺序栈相同顺
序队列也是用一个向量空间来存放当前队列中的元素。
由于队列的队头和队尾的位置均是变化的，因而要设
置两个指针，分别指示当前队头元素和队尾元素的位
置。
规定：队头指针总是指向当前队头元素的前一个位置
队尾指针指向当前队尾元素的位置
初始，队头和队尾指针均指向向量空间的前一个置 。
图 3.10说明了顺序队列中出队和入队运算时队列中
的元素及其头尾指针的变化状况。
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];
}
我们先以整数元素为例，给出顺序队列的基本运算的
实现代码。
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
}
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)) // 队列空 （ 下溢 ）
{ cout << " ERROR,underflow !!\n";
return false; }
e=Q.elem[Q.front+1]; return true ; // 元素
//存 e,队头指针不变 (元素没出队列 )
}
由上面的算法可看出 空队列的判定条件为 front==rear。
而值得考虑的是队列满（即上溢）的判定条件是什么？
假设当前队列处于图 3.10(d)的状态。即 MaxSize=5，
rear=4,front=2，因为 rear==maxsize-1，故此时
不能作入队操作，但当前队列并不满，我们把这种
现象称为,假上溢” 。
产生该现象的原因是 被删元素的空间永远使用不到
一个较巧妙的办法方法是：将 *elem设想成一个首尾
相接的圆环，即,elem[0]接在 elem [MaxSize-1]之
后。
我们将这种意义下的向量称为 循环向量,并将循环向量中的队
列称为 循环队列 (Circular Queue)。
如图 3.11所示。
为克服这一缺点，可以在每次出队时将整个队列中的元素向前移
动一个位置，也可以在发生假上溢时将整个队列中的元素向前移
动直至头指针为零。但这两种方法都会引起大量元素的移动，所
以在实际应用中很少采用。
当 rear == MaxSize -1时，若要做入队操作时，只要 elem[0]是
自由空间，下一个元素就进入 elem[0]，这可以利用“求模”运
算来实现循环队列的运算。
入队为, rear = (rear+1) % MaxSize ; elem [rear] = x ;
出队为,front = (front+1) % MaxSize ;
由图 3.11(b),(c)看出，当队列空时，头、尾指针指向了队列
中的同一位置；而队列满时，头、尾指针亦指向同一位置。因
此，只凭等式 front == rear不足以判别循环队列的状态是“空
”还是“满”。
对此，有两种解决办法,
在循环队列中如何判别队满和队空？
一是另设一个标志位，以区别队“空”还是队“满”；
另一较简单的办法是不设标志位，而把“尾指针从后面追上
头指针”当作队满时的特征。即
如果 (rear+1) % MaxSize == front则认为队满，不能进队
（此时队列中尚留有一个空额）。这样虽损失了一个空间，
但避免了判另外设的标志而造成的时间上的损失。
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>&);
// " = " 运 //算符重载
循环队列的模板类接口定义以及基本运算的实现代码
如下：
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;
}
template <class T>bool sqQueue<T>::EnQueue(T x)
// 元素 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;
}
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,队头指针
// 不变 (元 // 素没出队列 )
return true;
}
Template<classT>sqQueue<T>::sqQueue(const
sqQueue<T>& obj) // 由顺序队列 obj复制构造新队列
{ MaxSize=obj.MaxSize; // 被构造队列与 obj容量应相同
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>::operato
r=(const sqQueue<T>&origin)
// "=" 运算符重载,请读者自己完成
{ … }
3.4.3 链队列－－队列的链式存储结构
队列的链式存储结构简称为 链队列,它是限制仅在表
头删除和表尾插入的单链表 。
显然仅有单链表的头指针不便于在表尾做插入操作，
为此再增加一个尾指针，指向链表上的最后一个结点
。于是,一个链队列由一个头指针和一个尾指针唯一
地确定。
链队列的模板类可以继承单链表的模板类 LinkedList（增加一
个数据成员 rear），读者可以参考第 2章中单链表类的实现部分
完成链队列的实现代码。
图 3.12所示为无头结点的链队列，图 3.13则表示带有
头结点的链队列。
3.5 应用实例
在我们日常生活中经常会遇到许多为了维护社会正常秩序而需要
排队的情况。这样一类事情的模拟程序通常要用到队列和线性表
这一类数据结构，因而是队列应用例子之一。在此，向读者介绍
一个银行业务的模拟程序。
⒈ 问题描述
假设某银行有 4个窗口对外接待客户，从早晨开门起不断有客户
进入银行。由于每个窗口只能接待一个客户，因此在客户人数众
多时需在每个窗口前顺序排队，对于刚进入银行的客户，如果某
个窗口的业务员正空闲，则可上前办理业务；反之，若 4个窗口
均有客户所占，他便会排在人数最少的队伍后面。现在需要编制
一个程序以模拟银行的这种业务活动，并计算一天中客户在银行
逗留的平均时间。
⒉ 数据结构
分析,为了计算平均时间，我们需要知道每一客户到达银行和离
开银行这两个时间，后者减去前者即为每个客户在银行逗留的时
间。所有客户逗留时间的总和被一天内办理业务的客户数除便是
所求的平均时间。每个客户到达银行的时间是自然形成的，而离
开银行的时间则和银行的整个对外业务活动有关。假设客户到达
后即刻办理业务，则他在银行逗留的时间即为他办理业务所需的
时间；否则尚需加上他排队等候的时间。
因此，应当采用的数据结构为：
⑴ 队列及队列的头结点数组
用 4个队列 表示 4个窗口前的客户排队情况。
由于队列中的最大元素无法预测，而且长度变化较大，故采用 单
链表 作存储结构为宜。链表中每个结点包含两个数据域：
arrivetime和 duration（分别表示客户到达银行的时间和办理业
务所需的时间）（如图 3.14(a)所示）。
为便于查找最短队列，将有关每个队的信息（由三个域组成：
front,rear和 num）另组成一个数组，图 3.14(b)是初始化时设
置 4个队列均为“空”的情况。
模拟时, 每个队列中的队头元素表示正被银行业务员接待的客
户 。 有 5种情况的发生会使队列发生变化,① 新的客户进入银
行, 他将加入人数最少的队列而成为该队列的队尾元素； ②,
③, ④, ⑤ 分别是 0,1,2,3号窗口的客户办理完业务离开银
行, 则紧排在其后面的客户开始被接待, 成为新的队头元素 。
我们把上述 5种情况的发生称作 事件,并按事件发生的先后构成
一个 事件表 。在任何时刻，事件表中至多只有 5个元素，表示即
将发生的 5类事件。其一表示有某个客户到达银行（除了银行关
门不再有客户进入），另 4个则表示正在 4个窗口办理业务的客
户将在某个时刻离开银行。整个模拟程序就是按时间先后一个接
一个处理这些事件。这样一种模拟程序称为 离散事件驱动模拟 。
⑵ 事件表
由于事件需按事件发生的先后有序，且每一时刻事件表中最多有
5个元素，因此用大小为 5的有序顺序表存储即可。
模拟的过程是按照时间先后顺序一个接一个处理事件
表中的事件，直到事件表为“空”。
⒊ 事件驱动模拟的过程
那么应当如何处理事件呢？可以将 5种类型的事件分为两个处理
子程序：
⑴ 处理类型为 4的“客户到达”事件：首先应得到两个时间：
此时模拟程序应做的工作是：
① 该客户办理业务所需时间；
②下一客户将到达银行的时间间隔。
① 比较 4个队列中的元素个数，将新到客户加入到元素个数最少
的队列中成为新的队尾元素。若刚进队的元素是这个队列的队头
元素（已经开始办理业务），则还应设定“该客户办理完业务离
开银行”的事件插入事件表；
② 设定一个新的事件 -- 下一个客户即将到达银行的事件插入事
件表；
⑵ 处理类型为 i∈{0,1,2,3} 的“某客户在 i号队列
办理完业务离开银行”事件。
这时，程序需做的工作是：
① 该客户出队列，并计算他在银行逗留的时间；
② 当 i号队列非空时，计算新的队头元素将离开
银行的时间，并由此设定一个新的离开事件插
入事件表。
#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;
};
⒋ 算法实现
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; }
};
// 注意：由于事件表要求有序, 因此要重载运算符 " >" (插入
到有序表中的元素比较符号 )
// 模拟中总要从事件表中删除,时间值小,的事件, 为了删除时
不移动元素, 我们让
// 事件表中元素按,时间值,从大到小排列, 这样, 最早发生的
事件排在表尾 。
int closetime,dut,interval;
queue q[4]; // 队列数组
void simulate(); // 模拟程序原型声明
void main() // 主函数
{ time_t st; srand((unsigned)time(&st));
//初始化随时间变化的随机数种子
simulate(); // 调用模拟程序
}
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;
}
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;
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);
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) // 在关门
// 之前到达, 则生成
{ 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;
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;
out<<"The average wait time is“
<<waitime*1.0/count<<endl;
out.close();
}
目录
1.栈
2,栈的 应用举例
3,栈与递归
4,队列
5,应用实例
3.1 栈
3.1.1 栈的定义及其运算
栈 （ Stack） 是限定插入和删除运算只能在表尾
进行的线性表。
通常称允许插入、删除的这一端为栈顶，另一端
称为栈底。
当表中没有元素时称为空栈。
其中数据元素的个数 n定义为表的长度。
图 3.1是一个栈的示意图，通常用指针 top指示栈顶的位
置，用指针 bottom指向栈底。栈顶指针 top动态反映栈
的当前位置。
图 3.1所示的栈中，元素是以 a1，
a2,…, an的顺序进栈，而出栈
的次序却是 an,an-1,…, a1。
也就是说，栈的修改是按后进先
出的原则进行的。 因此，栈又称为
后进先出（ Last In First Out）的线性表，简称为
LIFO表。
ADT Stack
{ Typedef struct Stack S;
InitStack(S,maxSize);
说明：构造空栈 S,即栈的初始化
StackSize(S);
说明：求栈中元素的数目
isEmpty(S);
说明：判栈 S是否为空栈
isFull(S);
说明：判栈 S是否已, 满,
栈的 ADT声明如下,
GetTop(S,e);
说明：取栈顶元素
Push (S,e);
说明：值为 e的数据元素进栈 （ 插入, 压栈 ）
Pop(S);
说明：栈顶元素出栈 （ 删除, 退栈 ）
};
栈的顺序存储结构称为顺序栈, 是用一组地址连续的
存储单元依次存放自栈底到栈顶的数据元素 。
3.1.2 栈的顺序存储结构
因为栈底位置是固定不变的, 栈顶位置是随着进栈和退栈
操作而变化的, 故需用一个变量 top来指示当前栈顶位置,
通常称 top为栈顶指针, 参看图 3.2。
Typedef struct
{ int *elem; // elem是数据元素数组
int top; // 栈顶指针
int maxSize; // 栈容量
}sqStack;
我们先以整数元素为例，给出顺序栈的基本
算法，在下一节，将给出顺序栈的模板类接口
定义以及基本运算的实现代码和应用实例。
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; }
boolPush (sqStack S,int e)
// 值为 e的数据元素进栈 (插入, 压栈 )
{ if(isFull(S)) // 栈满 （ 溢出 ） 无法进栈,返回 false
{ cout << " ERROR,overflow !!\n";
return false; }
S.elem[++S.top] = e ; return true ;
//栈顶指针增 1元素进栈,返回 true
}
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)) // 栈空 （ 下溢 ）
{ cout <<, ERROR,underflow !!\n” ;
return false ; }
e=S.elem[S.top] ; return true ;
// 元素存 e,栈顶指针不变 (元素没出栈 )
}
栈的使用非常广泛，常常会出现在一个程序中需要
同时使用多个栈的情形。为了不因栈上溢而产生错
误中断，要给每个栈预分较大空间，但各个栈实际
所用最大空间很难估计。而且各个栈的实际容量在
使用期间是变化的，往往会出现某个栈发生上溢，
而另一个栈还是空的。
试 设想,若令多个栈共享空间，则将提高空间的使
用效率，并减少发生栈上溢的可能性。
假设在程序中需设两个栈，并共享一维数组空间 v[m]。
则利用, 栈底位置不变, 的特性，可将两个栈的栈底分
别设在数组空间的两端，然后各自向中间伸展（如图 3.3
所示），仅当两个栈的栈顶相遇时才可能发生上溢。由
于两个栈之间可以做到互补余缺，使得每个栈实际可利
用的最大空间大于 m/2。显然，两个栈顶的初值分别为 -1
和 m。
栈的链式存储结构称为链栈, 它是运算受限的单链表,
其插入和删除操作仅限制在表头位置上进行 。
3.1.3 栈的链式存储结构
由于只能在链表头部进行操作，
故链栈没有必要象单链表那样
附加上头结点。栈顶指针就是
链表的头指针，如图 3.4所示，
链栈就是无头结点的单链表
（头指针改称栈顶指针），因
此不再重新讨论。
3.2 栈的应用举例
栈的应用非常广泛，只要问题满足 LIFO原则，均可使
用栈做数据结构。
//顺序栈的模板类接口定义以及基本运算的实现代码
template <class T> class sqStack
{ protected:
int *elem ; // 指向存放数据元素的数组指针
int top ; // 栈顶指针
int maxSize; // 栈容量
public:
sqStack(int ms=10); // 构造函数
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 &); // 取栈顶元素
};
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;
}
template <class T>bool sqStack<T>::Pop()
//栈顶元素出栈,被删元素存 e
{ if(isEmpty()) // 栈空 （ 下溢 ）
{ cout <<, ERROR,underflow !!\n” ;
return false; }
top--; //栈顶指针减 1(元素出栈 )
return true;
}
template <class T>bool sqStack<T>::GetTop(T &e)
// 取栈顶元素
{ if(isEmpty(S)) // 栈空 （ 下溢 ）
{ cout <<, ERROR,underflow !!\n” ;
return false; }
e=elem [top]; // 元素存 e,栈顶不变 (元素没出栈 )
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]; // 复制数据元素
}
template<classT>sqStack<T>&sqStack<T>::operato
r=(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]; //复制数据元素
}
【 例 3.1】 用栈实现程序设计语言中的子程序调用
和返回 。
假设有一个主程序 main和三个子程序 A1,A2和 A3，
其调用关系如图 3.5所示 。
从图 3.5可知，主程序 main调用子程序 A1，子程序 A1完成之
后，返回到主程序的 r处继续执行。但是，因为子程序 A1又调
用了子程序 A2，所以在 A2执行完毕并返回之前,A1是不可能
结束的。类似地,A2也必须在 A3执行完毕并返回之后才能从
t处继续进行。其调用与返回的过程如图 3.6所示。
显然，调用次序和返回次序是
相反的，最后调用到的子程序
最先返回。为了保证各个被调
用子程序能正确地返回，可以
在程序运行期间设置一个工作
栈来保存返回地址 。
当调用某一个子程序时，将该子程序的返回地址进栈；当
某一子程序执行完毕时将当前栈顶的返回地址出栈，并按
该地址返回。注意，某一子程序 P执行完毕，当前栈顶内
容一定是 P的返回地址。因为只有当执行 P时所调用的其它
子程序都已返回,P才能结束，这就保证了当 P返回时，其
相应的返回地址正好是在当前栈顶，参看图 3.7。
【 例 3.2】 表达式转换 （ 中缀表达式改写成后缀表
示法 ）
算术表达式有 三种表示方法, ⑴ <操作数 > <操作符 > <操作
数 >,如 A+B,称为中缀 (infix)表示； ⑵ <操作符 > <操作数
> <操作数 >,如 +AB称为前缀 (prefix)表示； ⑶ <操作数 > <
操作数 > <操作符 >,如 AB+,称为后缀 (postfix)表示 。
在后缀表达式中, 没有括号, 也不存在优先级的差别, 计算
过程完全按照运算符出现的先后次序进行, 整个计算过程仅
需一遍扫描便可完成, 显然比中缀表达式的计算要简单得多 。
因此, 程序设计语言的编译系统要将通常的中缀表达式转换
成后缀表达式
例如, A*(B+C)的后缀表达式是 ABC+*,因 ’ +’ 运算符
在前, ’ *’ 运算符在后, 所以应先做加法, 后做乘法 。
再如, 表达式 A/B*C+D*(E-A)+C/(D*B) 的后缀形式是
AB/C*DEA-*+CDB*/+,
怎样设计算法把运算符放在两个运算对象中间的中缀表达
式转换为后缀形式呢？
观察一下两种形式的表达式，我们注意到操作数在两种形
式中出现的次序是相同的。所以在扫描表达式时，凡遇到
操作数就马上输出，剩下的事情就是处理所遇到的运算符。
解决的办法是把遇到的运算符存放到栈中，直到某个适当
时刻再将运算符退栈并输出。
我们来看两个例子：
（ 1） 要由表达式 A+B*C产生出后缀表达式 ABC*+,必
须按照如表 3.1所示的操作顺序执行 （ 栈向右增长 ） 。
到达第 4步时必须确定是 ’ *’ 进入栈顶, 还是 ’ +’
退栈；由于 ’ *’ 的优先级更高, 应该是 ’ *’ 进栈,
从而产生第 5步；现在已从表达式中取完所有的符号,
于是我们输出运算符栈中所有剩余的运算符得到：
ABC*+
（ 2） 表达式 A*(B+C)/D 的后缀形式为 ABC+* D/，
当遇到左括号时必须入栈, 遇到右括号时, 必须依次
把栈中元素退栈 。 直到相应的左括号为止, 然后去掉
左右括号 。 如表 3.2所示 。
这些例子启发我们, 算术运算符和括号可用如表
3.3所示分级方案实现 。 其规则是：
只要运算符在栈中的优先级 isp(in-stack priori
ty)大于或等于新运算符进来时的优先级 icp(in-c
oming priority)，则运算符就从栈中取出。
isp(x)和 icp(x)是函数，它们返回运算符按上述
给定的优先级值。
//将表达式的中缀形式转换为后缀形式
#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; }
具体算法如下：
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
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();
}
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 if(x=='+'||x=='-') return 1;
else return 3;
}
void postfix(char *e) // 将中缀式 e转换为后缀式输出
{ 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是运算符
{ 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); // 输出栈中其余运算符 (#不输出 )
}
3.3 栈与递归
3.3.1 栈的定义及其运算
若一个对象部分地包含它自己,或用它自己给自己定
义,则称这个对象是递归的；若一个过程直接地或间
接地调用自己,则称这个过程是递归的过程。
递归（ recursion）是最常用的算法设计思想，采用递归
的方法来编写求解程序，使程序非常简洁而清晰，本节重点
讨论递归在计算机内的实现，以及怎样把一个递归的子程序
变换成一个等价的非递归的子程序，读者将会看到，在这里
起关键作用的是栈。
⑴ 定义是递归的； 如, 我们熟悉的 Factorial函
数,Ackerman函数, Fibnocci函数等 。
在以下三种情况下，常常用到递归方法。
⑵ 数据结构是递归的； 例如，单链表结构，每个结点
的 next域指向的仍然是单链表的结点。我们后面将要
学习的二叉树、广义表等数据结构，它们的定义就是
递归的（具有固有的递归特性）因此自然采用递归方
法进行处理。
⑶ 问题的解法是递归的。
例如，汉诺塔 (Tower of Hanoi)问题传说婆罗门庙
里有一个塔台，台上有三根标号为 A,B,C的用钻石
做成的柱子，在 A柱上放着 64个金盘，每一个都比
下面的略小一些。把 A柱上的金盘全部移到 C柱上的
那一天就是世界末日。移动的条件是：一次只能移
动一个金盘，移动过程中大金盘不能放在小金盘上
面。庙里的僧人一直在移个不停。因为全部的移动
是 264 -1次，如果移动一次需要一秒的话，需要 500
亿年。
用递归方法求解问题是将一个较复杂的（规
模较大）的问题转换成一个与原问题同类型
的稍简单（规模稍小）的问题来解决，使之
比原问题进了一步（更靠近边界条件一步），
直至到达边界条件（直接求解，不再递归）。
要理解递归算法, 就必须了解计算机内递归是如何实
现的？ 我们通过例子说明之 。
3.3.2 递归子程序的实现
【 例 3.3】 汉诺塔问题：设需移动的金盘数为
n（ 问题的规模 ）, 当 n=1时, 只要将编号为 1
的金盘从柱 A直接移至柱 C即可；当 n>1时, 需
利用柱 B作辅助柱子 。
算法思路,若能设法将压在编号为 n的金盘之
上的 n-1个金盘从柱 A依照上述法则移至柱 B；
则可先将编号为 n的金盘从柱 A移至柱 C,然后
再将柱 B上的 n-1个金盘依照上述法则移至柱 C。
而如何将 n-1个金盘从一个柱移至另一个柱的
问题是一个和原问题具有相同特征属性的问
题, 只是问题的规模小了 1；因此可以用同样
的方法求解 。
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 用作过渡
c o u t < <, move d i s k, < < n < <,,
,<<A<<,→,<<C;
// 将 n号盘从 A移到 C
Hanoi (n-1,B,A,C);
// 将 B上编号为 1~n-1的盘移至 C上,A 用作过渡
}
}
图 3.8显示了问题规模 n=4时 Hanoi塔问题的调用过程
显然，递归算法 Hanoi在执行过程中，需多次调
用它本身。那末，递归子程序是如何执行的呢？
和汇编程序设计中主程序和子程序之间的链
接和信息交换相类似，在高级语言编制的程
序中，主调程序和被调子程序之间的链接和
信息交换也须通过 栈 来进行。
通常，当程序在运行期间调用另一个程序时，在运行
被调程序之前，系统必须完成 3件工作：
① 将所有的实在参数、返回地址等信息传递
给被调子程序保存；
② 为被调子程序的局部变量分配存储区；
③ 将控制转移到被调子程序的入口。
而从被调子程序返回主调程序之前，系统也应完成
3件工作：
① 保存被调子程序的计算结果：
② 释放被调子程序的数据区；
③ 恢复被调子程序保存的返回地址将控制转
回到主调程序。
当有多个程序间构成嵌套调用时，按照, 后调用先返
回, 的原则。
上述程序之间的信息传递和控制转移必须通过,栈”
来实现；
即系统将整个程序运行时所需的数据空间安排在一
个栈中。每当调用一个程序时，就为它在栈顶分配
一个存储区；每当退出一个程序时，就释放它的存
储区；则当前正运行程序的数据区必然在栈顶。
递归程序的运行子程序类似于例 3.1中多个程序的嵌
套调用；只是 主调程序和被调子程序是同一个程序 而
已。
⒈ 递归与分治法
3.3.3 递归技术相关问题
任何一个可用计算机求解的问题所需的计算时间都与其
规模有关 。 问题的规模越小, 越容易直接求解, 解题所需的
计算时间也越少 。 例如, 对于 n个元素的排序问题, 当 n=1时,
不需任何计算 。 n=2时, 只要作一次比较即可排好序 。 n=3
时只要作 3次比较即可, ? 。 而当 n较大时, 问题就不那么容
易处理了 。 要想直接解决一个规模较大的问题, 有时是相当
困难的 。
分治法的思想,将一个难以直接解决的大问题，分割成
一些规模较小的相同问题，以便各个击破，分而治之。
如果原问题可分割成 k个子问题 (1<k≤n),且这些子
问题都可解，并可利用这些子问题的解求出原问题
的解，那么分治法就是可行的。
由分治法产生的子问题往往是原问题的较小模式，
这就为使用递归技术提供了方便。在这种情况下，反
复应用分治手段，可以使子问题与原问题类型一致而
其规模却不断缩小，最终使子问题缩小到很容易直接
求出其解。这自然导致递归过程的产生。 分治与递归
像一对孪生兄弟,经常同时应用在算法设计之中，并
由此产生许多高效算法。
⒉ 递归与迭代
递归与迭代都是基于程序设计语言的控制结构, 迭代用重复
结构, 递归用选择结构 。
例如，求解阶乘函数的递归算法如下：
long Factorial (long n)
{ if(n==0) return 1;
else return n*Factorial(n-1);
}
迭代算法如下：
long Factorial (long n)
{
long i,p = 1;
for (i=2; i<=n; i ++) p*=i;
return p ;
}
任何能用递归解决的问题也能用迭代方法解决。
究竟应当如何选择递归和迭代呢？我们将两种方法做个比较。
一般对于象斐波那契数列和阶乘阶乘这样一些 单向递归和尾递归
可直接用迭代 方法，而没有明显迭代方案的如阿克曼函数，汉诺
塔问题还是应当采用递归方法，如果一定要转换为非递归算法，
则必须借助于栈实现，有兴趣的读者可参看参看文献 [1]。
递归方法能更自然地描述问题，使算法容易理解和调试
（可读性好） ；但是递归方法要耗费更多的时间与空间
（效率低） ；迭代方法发生在函数 (子程序 )内部，不需
进行“转子、返回”及“参数压栈”等操作，因此 时空
效率高 。
【 例 3.4】 在 8*8的国际象棋上摆放八个皇后, 使
其不能互相攻击,即任意两个皇后不能处于同一行,
同一列或同一斜线上, 问有多少种摆法 。
下面，我们就十九世纪著名的数学家高斯 1850年提出的“八皇
后问题” 分别用递归与迭代方法给出源程序，做为本小节的
应用例。
// 递归回溯算法
#include <fstream.h>
int sum=0,x[9]; // x[1] ~ x[8]存放当前解,
// x[i] = j表示第 i行的皇后放在第 j列 。
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();
}
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++;
}
for(j=1; j<=8; j++)
// 在循环中递归调用,对每一皇后都测试了所有位置,因此
// 可得到所有解
{ x [i] = j ;
if(Place(i))Backtrack(i+1);
//确定当前皇后的位置,找下一皇后位置
}
}
//迭代回溯算法
#include <math.h>
#include <fstream.h>
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;
}
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;
}
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组解经旋转或左右对称变换得到。
3.4 队列
3.4.1 队列的定义及其运算
队列 (Queue)是限定只能在表尾插入元素，而在表
头删除元素的线性表。
这和我们日常生活中的排队是一致的，最早进入队列的元素最
早离开。因此也称其为,先进先出（ First In First Out，缩
写为 FIFO）表。
允许插入的一端叫做 队尾,
允许删除的一端则称为 队头 。
假设队列为,Q = (a1,a2,?, an)，那么,a1就是队头
元素,an则是队尾元素。队列中的元素是按照 a1,a2，
?, an的顺序进入的，退出队列也只能按照这个次序依
次退出，也就是说，只有在 a1,a2,?, an-1都离开队
列之后,an才能退出队列。
图 3.9是队列的示意图。
队列在程序设计中也经常出现。
一个最典型的例子就是操作系统中的作业排队。在允
许多道程序运行的计算机系统中，同时有几个作业运
行。如果运行的结果都需要通过通道输出，那就要按
请求输出的先后次序排队。每当通道传输完毕可以接
受新的输出任务时，队头的作业先从作业队列中退出
做输出操作。凡是申请输出的作业都从队尾进入队列。
队列的 ADT声明如下：
ADT Queue
{ Typedef struct Stack Q;
InitStack(Q,maxSize);
说明：构造空队列 Q，即队列的初始化
QueueSize(Q); 说明：队列中元素的数目
isEmpty(Q); 说明：判队列 Q是否为空
isFull(Q); 说明：判队列 Q是否已“满”
GetFront(Q,e); 说明：取队头元素
EnQueue(Q,e); 说明：值为 e的数据元素进入队列
Del Queue(Q); 说明：队头元素出队（删除）
};
3.4.2 顺序队列－－队列的顺序存储结构
队列的顺序存储结构称为 顺序队列 。与顺序栈相同顺
序队列也是用一个向量空间来存放当前队列中的元素。
由于队列的队头和队尾的位置均是变化的，因而要设
置两个指针，分别指示当前队头元素和队尾元素的位
置。
规定：队头指针总是指向当前队头元素的前一个位置
队尾指针指向当前队尾元素的位置
初始，队头和队尾指针均指向向量空间的前一个置 。
图 3.10说明了顺序队列中出队和入队运算时队列中
的元素及其头尾指针的变化状况。
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];
}
我们先以整数元素为例，给出顺序队列的基本运算的
实现代码。
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
}
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)) // 队列空 （ 下溢 ）
{ cout << " ERROR,underflow !!\n";
return false; }
e=Q.elem[Q.front+1]; return true ; // 元素
//存 e,队头指针不变 (元素没出队列 )
}
由上面的算法可看出 空队列的判定条件为 front==rear。
而值得考虑的是队列满（即上溢）的判定条件是什么？
假设当前队列处于图 3.10(d)的状态。即 MaxSize=5，
rear=4,front=2，因为 rear==maxsize-1，故此时
不能作入队操作，但当前队列并不满，我们把这种
现象称为,假上溢” 。
产生该现象的原因是 被删元素的空间永远使用不到
一个较巧妙的办法方法是：将 *elem设想成一个首尾
相接的圆环，即,elem[0]接在 elem [MaxSize-1]之
后。
我们将这种意义下的向量称为 循环向量,并将循环向量中的队
列称为 循环队列 (Circular Queue)。
如图 3.11所示。
为克服这一缺点，可以在每次出队时将整个队列中的元素向前移
动一个位置，也可以在发生假上溢时将整个队列中的元素向前移
动直至头指针为零。但这两种方法都会引起大量元素的移动，所
以在实际应用中很少采用。
当 rear == MaxSize -1时，若要做入队操作时，只要 elem[0]是
自由空间，下一个元素就进入 elem[0]，这可以利用“求模”运
算来实现循环队列的运算。
入队为, rear = (rear+1) % MaxSize ; elem [rear] = x ;
出队为,front = (front+1) % MaxSize ;
由图 3.11(b),(c)看出，当队列空时，头、尾指针指向了队列
中的同一位置；而队列满时，头、尾指针亦指向同一位置。因
此，只凭等式 front == rear不足以判别循环队列的状态是“空
”还是“满”。
对此，有两种解决办法,
在循环队列中如何判别队满和队空？
一是另设一个标志位，以区别队“空”还是队“满”；
另一较简单的办法是不设标志位，而把“尾指针从后面追上
头指针”当作队满时的特征。即
如果 (rear+1) % MaxSize == front则认为队满，不能进队
（此时队列中尚留有一个空额）。这样虽损失了一个空间，
但避免了判另外设的标志而造成的时间上的损失。
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>&);
// " = " 运 //算符重载
循环队列的模板类接口定义以及基本运算的实现代码
如下：
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;
}
template <class T>bool sqQueue<T>::EnQueue(T x)
// 元素 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;
}
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,队头指针
// 不变 (元 // 素没出队列 )
return true;
}
Template<classT>sqQueue<T>::sqQueue(const
sqQueue<T>& obj) // 由顺序队列 obj复制构造新队列
{ MaxSize=obj.MaxSize; // 被构造队列与 obj容量应相同
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>::operato
r=(const sqQueue<T>&origin)
// "=" 运算符重载,请读者自己完成
{ … }
3.4.3 链队列－－队列的链式存储结构
队列的链式存储结构简称为 链队列,它是限制仅在表
头删除和表尾插入的单链表 。
显然仅有单链表的头指针不便于在表尾做插入操作，
为此再增加一个尾指针，指向链表上的最后一个结点
。于是,一个链队列由一个头指针和一个尾指针唯一
地确定。
链队列的模板类可以继承单链表的模板类 LinkedList（增加一
个数据成员 rear），读者可以参考第 2章中单链表类的实现部分
完成链队列的实现代码。
图 3.12所示为无头结点的链队列，图 3.13则表示带有
头结点的链队列。
3.5 应用实例
在我们日常生活中经常会遇到许多为了维护社会正常秩序而需要
排队的情况。这样一类事情的模拟程序通常要用到队列和线性表
这一类数据结构，因而是队列应用例子之一。在此，向读者介绍
一个银行业务的模拟程序。
⒈ 问题描述
假设某银行有 4个窗口对外接待客户，从早晨开门起不断有客户
进入银行。由于每个窗口只能接待一个客户，因此在客户人数众
多时需在每个窗口前顺序排队，对于刚进入银行的客户，如果某
个窗口的业务员正空闲，则可上前办理业务；反之，若 4个窗口
均有客户所占，他便会排在人数最少的队伍后面。现在需要编制
一个程序以模拟银行的这种业务活动，并计算一天中客户在银行
逗留的平均时间。
⒉ 数据结构
分析,为了计算平均时间，我们需要知道每一客户到达银行和离
开银行这两个时间，后者减去前者即为每个客户在银行逗留的时
间。所有客户逗留时间的总和被一天内办理业务的客户数除便是
所求的平均时间。每个客户到达银行的时间是自然形成的，而离
开银行的时间则和银行的整个对外业务活动有关。假设客户到达
后即刻办理业务，则他在银行逗留的时间即为他办理业务所需的
时间；否则尚需加上他排队等候的时间。
因此，应当采用的数据结构为：
⑴ 队列及队列的头结点数组
用 4个队列 表示 4个窗口前的客户排队情况。
由于队列中的最大元素无法预测，而且长度变化较大，故采用 单
链表 作存储结构为宜。链表中每个结点包含两个数据域：
arrivetime和 duration（分别表示客户到达银行的时间和办理业
务所需的时间）（如图 3.14(a)所示）。
为便于查找最短队列，将有关每个队的信息（由三个域组成：
front,rear和 num）另组成一个数组，图 3.14(b)是初始化时设
置 4个队列均为“空”的情况。
模拟时, 每个队列中的队头元素表示正被银行业务员接待的客
户 。 有 5种情况的发生会使队列发生变化,① 新的客户进入银
行, 他将加入人数最少的队列而成为该队列的队尾元素； ②,
③, ④, ⑤ 分别是 0,1,2,3号窗口的客户办理完业务离开银
行, 则紧排在其后面的客户开始被接待, 成为新的队头元素 。
我们把上述 5种情况的发生称作 事件,并按事件发生的先后构成
一个 事件表 。在任何时刻，事件表中至多只有 5个元素，表示即
将发生的 5类事件。其一表示有某个客户到达银行（除了银行关
门不再有客户进入），另 4个则表示正在 4个窗口办理业务的客
户将在某个时刻离开银行。整个模拟程序就是按时间先后一个接
一个处理这些事件。这样一种模拟程序称为 离散事件驱动模拟 。
⑵ 事件表
由于事件需按事件发生的先后有序，且每一时刻事件表中最多有
5个元素，因此用大小为 5的有序顺序表存储即可。
模拟的过程是按照时间先后顺序一个接一个处理事件
表中的事件，直到事件表为“空”。
⒊ 事件驱动模拟的过程
那么应当如何处理事件呢？可以将 5种类型的事件分为两个处理
子程序：
⑴ 处理类型为 4的“客户到达”事件：首先应得到两个时间：
此时模拟程序应做的工作是：
① 该客户办理业务所需时间；
②下一客户将到达银行的时间间隔。
① 比较 4个队列中的元素个数，将新到客户加入到元素个数最少
的队列中成为新的队尾元素。若刚进队的元素是这个队列的队头
元素（已经开始办理业务），则还应设定“该客户办理完业务离
开银行”的事件插入事件表；
② 设定一个新的事件 -- 下一个客户即将到达银行的事件插入事
件表；
⑵ 处理类型为 i∈{0,1,2,3} 的“某客户在 i号队列
办理完业务离开银行”事件。
这时，程序需做的工作是：
① 该客户出队列，并计算他在银行逗留的时间；
② 当 i号队列非空时，计算新的队头元素将离开
银行的时间，并由此设定一个新的离开事件插
入事件表。
#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;
};
⒋ 算法实现
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; }
};
// 注意：由于事件表要求有序, 因此要重载运算符 " >" (插入
到有序表中的元素比较符号 )
// 模拟中总要从事件表中删除,时间值小,的事件, 为了删除时
不移动元素, 我们让
// 事件表中元素按,时间值,从大到小排列, 这样, 最早发生的
事件排在表尾 。
int closetime,dut,interval;
queue q[4]; // 队列数组
void simulate(); // 模拟程序原型声明
void main() // 主函数
{ time_t st; srand((unsigned)time(&st));
//初始化随时间变化的随机数种子
simulate(); // 调用模拟程序
}
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;
}
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;
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);
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) // 在关门
// 之前到达, 则生成
{ 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;
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;
out<<"The average wait time is“
<<waitime*1.0/count<<endl;
out.close();
}
