3.3、栈和队列的实际应用
3.3.1、栈的顺序栈存储结构的实际应用
（1）判断括号是否正确匹配
编写算法实现判断一个表达式中的括号是否正确匹配，表达式已经存入字符数组A[ ]中，表达式中的字符个数为n。假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序任意即（[ ]( )）或[（[ ][ ]）]等均为正确的格式，[（]）或（[0）均为不正确的格式。
算法思想：
1）首先初始化一个空栈，按顺序读入表达式中的括号。
3）若是左括号，则压入栈中。算法执行完成后，栈应该为空，若栈不为空，则表达式中的括号序列不匹配，结束算法。
2）若是右括号，则将栈顶元素出栈，判断是否两个括号匹配。若匹配，则消掉一对括号，继续遍历。若不匹配，则表达式中的括号序列不匹配，结束算法。
算法代码实现：
bool isMatch（char A[ ]，int n）{
char stack[maxSize]; // 定义栈的最大容量
int top = -1; //初始化栈为空
for（int i=0；i<n；++i） //循环遍历括号序列进行判断
{
if ( A [i]==’(’ ) // 如果遇到“（”，则入栈等待后面匹配到右括号再处理
stack[++top] = ’(’ ; // 入栈操作
if（ A [i]==’）’ ）{
if（top == -1） // 如果当前遇到的括号是“）”并且栈已空，则不匹配，返回false
return false；
else
--top; //如果栈不空，则出栈，相当于划掉两个括号
}
}
if（top==-1）// 栈空说明所有括号都被处理掉，则括号序列是匹配的，返回true
return true；
else //否则括号序列不匹配，返回false
return false；
}
（2）表达式求值
编写算法求后缀式的数值，其中后缀式存于一个字符数组A[ ]中，A中最后一个字符为“\0”，作为结束符，并且假设后缀式中的数字都只有一位。本题中所出现的除法运算，皆为整除运算，如2/3结果为0、3/2结果为1。
算术表达式有3种形式：前缀式、中缀式、后缀式。
中缀式为（a + b + c x d）/e。
前缀式为 /++abxcde。
后缀式为 abcdx++e/。
中缀式转化成后缀式或者前缀式，结果并不一定唯一。因此对于一个中缀式可能有多种后缀式或者前缀式。例如，a+b+c可以先算a+b，也可以先算b+c，这样就有两种后级式与其对应，分别是ab+c+和abc++。
算法思想：
通过后缀表示计算表达式值的过程为：顺序扫描表达式的每一项，然后根据它的类型做如下相应操作：若该项是操作数，则将其压入栈中；若该项是操作符<op>，则连续从栈中退出两个操作数Y和X，形成运算指令X<op>Y，并将计算结果重新压入栈中。当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。
算法代码实现：
int op（int a，char Op，int b）{
// 此方法为是运算函数，用来实现算式“a op b”的运算
if（Op ==’+’） return a+b；// 若是加法，则返回a+b
if（Op==’-’）return a-b； // 若是减法，则返回a+b
if（Op==’*’）return a*b； // 若是乘法，则返回a+b
if（Op==’/’） // 若是除法，判断除数是否为0，若不为0，则返回a/b，否则返回0，提示错误信息
{
if（b==0） // 若除数为0，则返回0，输出错误提示
{
cout<<"ERROR"<<end1；
return 0；
}
else
return a/b； // 若不为0，则返回a/b
}
}
int sum（ char A[ ]）{
//此方法实现后缀式计算结果
int i，a，b，c；// a、b为操作数，c来保存结果
int stack[maxsize]； // 定义栈的最大容量
int top = -1; //初始化栈为空
char Op； // Op用来取运算符
for（i=0；A [i]！='\0'；++i）{
if（A [i]>=’10’&& A [i]<=’9’）//如果遇到操作数，则入栈等待处理
stack[++top]=A[i]-'0'；//字符型和整型的转换
else //如果遇到运算符，则说明前边待处理的数字的处理条件己经具备，开始运算
{
Op=exp[i]；// 取运算符
b=stack[top--]；//取第二个操作数（因为第二个操作数后入栈,先出栈的是第二个操作数）
a=stack[top--]；//取第一个操作数
c= op（a，Op，b）；//将两个操作数结合运算符Op进行运算，结果保存在c中
stack[++top]=c；//运算结果入栈
}
}
return stack[top];
}
（3）递归
递归是一种重要的程序设计方法。简单地说，若在一个函数、过程或数据结构的定义中又应用了它自身，则这个函数、过程或数据结构称为是递归定义的，简称递归。
它通常把一个大型的复杂问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的代码就可以描述出解题过程所需要的多次重复计算，大大减少了程序的代码量。但在通常情况下，它的效率并不是太高。
以斐波那契数列为例，其定义为
斐波那契数列递归实现代码：
int Fib( int n){
if(n==0) // 若n=0,返回0
return 0;
else if(n==1) // 若n=1,返回1
return 1;
else // 若n不为0也不为1,则递归调用
return Fib(n-1)+ Fib(n-2);
}
必须注意递归模型不能是循环定义的，其必须满足下面的两个条件：
1）递归表达式（递归体）。
2）边界条件（递归出口）。
递归的精髓在于能否将原始问题转换为属性相同但规模较小的问题。
斐波那契数列使用栈实现代码：// TODO
3.3.2、栈的链栈存储结构的实际应用
用不带头结点的单链表存储链栈，设计初始化栈、判断栈是否为空、进栈和出栈等相应的算法。
算法分析：
不带头结点的单链表lst为空的条件是st==NULL，进栈和出栈操作都是在表头进行的。算法如下：
void initStack（Lnode *&st）{ //初始化栈
st=NULL；
}
int isEmpty（Lnode *st）//判断栈是否为空
{
if（st==NULL）
return 1；
else
return 0；
}
void push（Lnode *&st，int x） { //进栈
Lnode *p；
p=（LNode*）malloc（sizeof（LNode））；
p->next=NULL；
p->data=x；
st=p；
}
int pop（Lnode *&st，int &x）{//元素出栈
Lnode *p；
if（st==NULL）//栈空的情况
return 0；
p=st； // p指向第一个数据结点
x=p->data；
st=p->next；
free（p）；
return 1；
}
3.3.3、队列在层次遍历中实际应用
用二又树（见图3.17）层次遍历的例子，说明队列的应用。表3.2显示了层次遍历二叉树的过程。
算法分析：
①根结点入队。
②若队空（所有结点都已处理完毕），则结束遍历；否则重复③操作。
③队列中第一个结点出队，并访问之。若其有左孩子，则将左孩子入队；若其有右孩子，则将右孩子入队，返回②。
3.3.4、队列在计算机系统中的实际应用
两个方面来简述队列在计算机系统中的作用：
第一个方面是解决主机与外部设备之间速度不匹配的问题。
第二个方面是解决由多用户引起的资源竞争问题。
第一个方面，仅以主机和打印机之间速度不匹配的问题为例做简要说明。主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快得多，由于速度不匹配，若直接把输出的数据送给打印机打印显然是不行的。解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入这个缓冲区，写满后就暂停输出，转去做其他的事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求。主机接到请求后再向缓冲区写入打印数据。这样做既保证了打印数据的正确，又使主机提高了效率。由此可见，打印数据缓冲区中所存储的数据就是一个队列。
第二个方面，CPU（即中央处理器，它包括运算器和控制器）资源的竞争就是一个典型的例子。在一个带有多终端的计算机系统上，有多个用户需要CPU各自运行自己的程序，它们分别通过各自的终端向操作系统提出占用CPU的请求。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把CPU分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后，令其出队，再把CPU分配给新的队首请求的用户使用。这样既能满足每个用户的请求，又使CPU能够正常运行。
3.4、特殊矩阵的压缩存储
3.4.1、数组的定义
数组是由n（n≥1）个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。数组与线性表的关系：数组是线性表的推广。一维数组可视为一个线性表；二维数组可视为其元素也是定长线性表的线性表。数组一旦被定义，其维数和维界就不再改变。因此，除结构的初始化和销毁外，数组只有存取元素和修改元素的操作。
3.4.2、数组的存储结构
逻辑意义上的数组可采用计算机语言中的数组数据类型进行存储，一个数组的所有元素在内存中占用一段连续的存储空间。
以一维数组A[0..n-1]为例，其存储结构关系式为
LOC(ai) = LOC（an）+(i) x L（0≤i<n）
其中，L是每个数组元素所占的存储单元。
对于多维数组，有两种映射方法：按行优先和按列优先。以二维数组为例，按行优先存储的基本思想是：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。设二维数组的行下标与列下标的范围分别为[0，h1]与[0，h2]，则存储结构关系式为
例如，对于数组A2x3，它按行优先方式在内存中的存储形式如图3.19所示。
当以列优先方式存储时，得出存储结构关系式为
例如，对于数组A2x3，它按列优先方式在内存中的存储形式如图3.20所示。
3.4.3、矩阵的压缩存储
压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是节省存储空间。
特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有对称矩阵、上（下）三角矩阵、对角矩阵等。
特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中。
（1）对称矩阵
若对一个n阶方阵A[1…n][1…n]中的任意一个元素ai，j都有a i，j = a j，i（1≤i，j≤n），则称其为对称矩阵。对于一个n阶方阵，其中的元素可以划分为3个部分，即上三角区、主对角线和下三角区，如图3.21所示。
对于n阶对称矩阵，上三角区的所有元素和下三角区的对应元素相同，若仍采用二维数组存放，则会浪费几乎一半的空间，为此将对称矩阵A[1..n][1..n]存放在一维数组B[n（n+1）/2]中，即元素a i，j，存放在bk中。只存放下三角部分（含主对角）的元素。
在数组B中，位于元素a i，j（i≥j）前面的元素个数为
第1行：1个元素（a1,1）。
第2行：2个元素（a2,1，a2,2）。
……
第i-1行：i-1个元素（ai-1,1, ai-1,2，…，ai-1,i-1）。
第i行：j-1个元素（ai,1，ai,2, ... ,ai,i-1）。
因此，元素ai,j在数组B中的下标k=1+2+ … +（i-1）+j-1=i（i-1）/2+j-1（数组下标从0开始）。因此，元素下标之间的对应关系如下：
（2）三角矩阵
下三角矩阵[见图3.23（a）]中，上三角区的所有元素均为同一常量。其存储思想与对称矩阵类似，不同之处在于存储完下三角区和主对角线上的元素之后，紧接着存储对角线上方的常量一次，故可以将下三角矩阵A[1..n][1..n]压缩存储在B[n（n+1）/2+1]中。
元素下标之间的对应关系为
下三角矩阵在内存中的压缩存储形式如图3.22所示。
上三角矩阵[见下，图3.23（b）]中，下三角区的所有元素均为同一常量。只需存储主对角线、上三角区上的元素和下三角区的常量一次，可将其压缩存储在B[n（n+1）/2+1]中。
在数组B中，位于元素ai,j,（i≤j）前面的元素个数为
第1行：n个元素
第2行：n-1个元素
……
第i-1行：n-i+2个元素
第i行：j-i个元素
因此，元素ai,j在数组B中的下标
k=n+（n-1）+…+（n-i+2）+(j-i+1）-1=( i-1)( 2n-i+2)/2+j-i
因此，元素下标之间的对应关系如下：
上三角矩阵在内存中的压缩存储形式如图3.24所示。
（3）三对角矩阵
对角矩阵也称带状矩阵。对于n阶方阵A中的任一元素ai,j,当| i-1| >1时，有ai,j=0（1≤i,j≤n），则称为三对角矩阵，如图3.25所示。
在三对角矩阵中，所有非零元素都集中在以主对角线为中心的3条对角线的区域，其他区域的元素都为零。三对角矩阵A也可以采用压缩存储，将3条对角线上的元素按行优先方式存放在一维数组B中，且a1,1存放于B[0]中，其存储形式如图3.26所示。
由此可以计算矩阵A中3条对角线上的元素ai,j（1≤i，j≤n，| i-1|≤1）在一维数组B中存放的下标为k=2i+j-3。
反之，若已知三对角线矩阵中某元素ai,j,在一维数组B的第k个位置，则i=⌞ (k+1)/3+1⌟，j=k-2i+3。例如，当k=0时，i=⌞(0+1）/3+1⌟=1，j=0-2×1+3=1,存放的是a1,1;当k=2时，i=⌞(2+1）/3+1⌟=2，j=2-2×2+3=1，存放的是a2,1：当k=4时，i=⌞(4+1）/3+1⌟=2，j=4-2×2+3=3，存放的是a2,3。
3.4.4、稀疏矩阵
矩阵中非零元素的个数t，相对矩阵元素的个数s来说非常少，即s>t的矩阵称为稀疏矩阵。
例如，一个矩阵的阶为100×100，该矩阵中只有少于100个非零元素。
若采用常规的方法存储稀疏矩阵，则相当浪费存储空间，因此仅存储非零元素。但通常零元素的分布没有规律，所以仅存储非零元素的值是不够的，还要存储它所在的行和列。因此，将非零元素及其相应的行和列构成一个三元组（行标，列标，值），如图3.27所示。然后按照某种规律存储这些三元组。稀疏矩阵压缩存储后便失去了随机存取特性。
稀疏矩阵的三元组既可以采用数组存储，也可以采用十字链表法存储。