第3章栈和队列

栈、队列、优先级队列和双端队列是4种特殊的线性表,它们的逻辑结构与线性表相同, 
只是其运算规则较线性表有更多的限制,故又称它们为运算受限的线性表。栈和队列被广
泛应用于各种系统的程序设计中。

3.栈
1 

栈是一种最常用和最重要的数据结构,它的用途非常广泛。例如,汇编处理程序中的句
法识别和表达式计算就是基于栈实现的。栈还经常使用在函数调用时的参数传递和函数值
的返回。

3.1 
栈的定义
1.
通常,栈(stack)可定义为只允许在表的末端进行插入和删除的线性表。允许插入和删
除的一端称为栈顶(top),而不允许插入和删除的另一端称为栈底(botom )。当栈中没有任
何元素时则成为空栈。

设给定栈S=(a2,…,),则称最后加入栈中的元

a1,an 
素an 
为栈顶。栈中按a1,a2,…,an 
的顺序进栈。而退栈的
顺序反过来,先退出,然后an-1才能退出,最后退出a1。换
句话说,后进者(a) 先出。因此,(n) 栈又称为后进先出(

lastinfirst 
out,LIFO)的线性表,如图3.1所示。图3.与线性表类似,可以借助C++类来定义栈的抽象数据类1 栈
型,如程序3.

1所示。

程序3.

1 栈的类定
义
constintmaxSize=50;
enol{astu


umbofle,re}
;
template<clasT>
clasStack{ //栈的类定
义
public:


Stack(){}; //构造函
数
virtualvoidPsh(T&x)=0; //新元素x进
栈
virtualbolPop(T(u) &x)=0; //栈顶元素出栈,由x返
回
virtualboolg(o) etTop(T&x)st=0; //读取栈顶元素,由x返
回
virtualboolIsEmpty()st(c) =(o) 0;(n) //判断栈空
否
virtualboolIsFl()cost(c) =(n) 0;(o) //判断栈满
否


}; 
virtualintgetSize(u) ()const(n) =0; //计算栈中元素个数

·81· 



3.2 
顺序栈
1.
栈的抽象数据类型有两种典型的存储表示:基于数组的存储表示和基于链表的存储表
示。基于数组的存储表示实现的栈称为顺序栈,基于链表的存储表示实现的栈称为链式栈。

顺序栈可以采用顺序表作为其存储表示,为此,可以在顺序栈的声明中用顺序表定义它
的存储空间。本书为简化问题起见,使用一维数组作为栈的存储空间。存放栈元素的数组
的头指针为*elements,该数组的最大允许存放元素个数为maxSize,当前栈顶位置由数组
下标指针top指示。如果栈不空时elements[0]是栈中第一个元素。

程序3.

2 顺序栈的类定
义
#inldseth>


cue<ar.
#inlde<isram.


cuoteh>
constintmaxStack=20;
constintstackIncreament=20; //栈溢出时扩展空间的增
量
template<clsT>
clasSeqStack{(a) //顺序栈的类定
义
public:


Setk(nz=50); //建立一个空栈

qScits
~SeqSt(a) ck(){dlete[]elements;} //析构函
数
idPsh(T(a) &x(a) (r) )
;

//(v) 如(o) 果Is(u) Ful(),则溢出处理;否则把x插入栈的栈
顶
blPop(T&x);//如(o) 果Is(o) Empty(),则不执行退栈,返回false;否则退掉位于栈顶的元素,返回true,
//退出的元素值通过引用型参数x返
回


blgetTop(T&x);//如(o) 果Is(o) Empty(),则返回false;否则返回true,并通过引用型参数x得到栈顶元素的
值
blIEmpt{tn(op== -re:flse;
}


ty()t1)?tua//如(o) 果栈(s) 中元素个(c) 数(n) 等于(r) 0,(r) (u) (e) (s) (o) 则返回true,否则返回false
blIl()t{n(o==xie1)?tre:fle;
}


FttpmaSz-uas//如(o) 果栈(s) 中(u) 元素(c) 个(n) 数等(r) 于(u) ma(r) (e) (s) (o) (o) xSize,则返回true,否则返回false
intgetSize()(rtrntop+1;) //函数返回栈中元素个
数
voidMakEmpttop=-//清空栈的内容

y(){(u) (e) 1;
}
fidota(e) m&optr<<(o) (ostream&os,SeqStack<T>&s);//(r) 输(e) 出(n) 栈(s) 中(r) 元(e) 素的重载(e) 操(o) 作


private:
T*elements; //存放栈中元素的栈数
组
inttop; //栈顶指
针
intmaxSize; //栈最大可容纳元素个
数


}; 
voidoverflowProces(); //栈的溢出处理

栈的构造函数用于在建立栈的对象时为栈的数据成员赋初值。函数中动态建立的栈数
组的最大尺寸为maxSize,由函数参数sz给出,并令top=-1,置栈为空。在这个函数实
现中,使用了一种断言(asert)机制,这是C+
+ 
提供的一种功能。若断言语句asert参数

·82· 


表中给定的条件满足,则继续执行后续的语句;否则出错处理,终止程序的执行。这种断言
语句格式简洁,逻辑清晰,不但降低了程序的复杂性,而且提高了程序的可读性。

程序3.

3 顺序栈的构造函
数
template<clasT>
SqSk<T>∷Stk(nz):o-xie(z)
{


tqScitstp(1),maSzs//建(e) 立一(a) 个最大尺寸(e) 为sz(a) (c) 的空栈,若分配不成功则错误处
理
elnts=newT[Size]; //创建栈的数组空
间
}; 
asert(e(eme) lements!=NU(ma) L(x) L); //断言:动态存储分配成功与
否


top指示的是最后加入的元素的存储位置。在实现进栈操作时,应先判断栈是否已满。
栈的最后允许存放位置为maxSize-1,如果栈顶指针top==maxSize-1,则说明栈中所
有位置均已使用,栈已满。这时若再有新元素进栈,将发生栈溢出,程序转入溢出处理。如
果top<maxSize-1,则先让栈顶指针加1,指到当前可加入新元素的位置,再按栈顶指针
所指位置将新元素插入。这个新插入的元素将成为新的栈顶元素如图3.2(a)所示。

另一个极端情况出现在栈底:如果在退栈时发现是空栈,即top== -1,则退栈操作
将执行栈空处理。栈空处理一般不是出错处理,而是使用这个栈的算法结束时需要执行的
处理。若当前top≥0,则可将栈顶指针减1, 2(所示。

等于栈顶退回到次栈顶位置如图3.b) 


图3.

2 进栈和退栈的情况

程序3.

4 栈的其他成员函数的实现
template<clasT> 
idSqStk<T>∷oflowProces(){

//(v) 私(o) 有函(e) 数:(a) 扩充栈的存(v) (c) 储(e) 空间(r) T*newAray=wT[xSize+stackIncreament]; 
if(ewAray==N(n) U(e) LL){(ma) r<<"存储分配失败!"<<endl;exit(1);} 

r((n) +)n(e) s[

i]=i]
;
maSize=maSize+stackIncreament;
delete[]e(x) lements;(x) 

·83· 

fointi=0;i<=top;i+(c) ewAray[element


elements=newAray;

}; 

template<clasT>
idSqStk<T>∷Ph(T&x){//(v) 共(o) 有函(e) 数:(a) 若栈不满则(u) 将(s) 元素x插入该栈的栈顶,否则溢出处理(c) if(sl()==uefowPoes();//栈满则溢出处
理


IFte)orlrc
}; 
elements(u) [++top]=(r) x;(v) //栈顶指针先加1,再进
栈


template<clasT>
blSqStk<T>∷Pp(T&x){//共(o) 有函(e) 数:(a) 若栈不空则(o) 函数返回该栈栈顶元素的值,然后栈顶指针减1(c) (o) 

if(stte)eunfle; //判断栈空否,若栈空则函数返回

IEmpy()==urtras
x=lttp//栈顶指针减
1


ens[o--];(r) }; 
returntrue;(eme) //退栈成
功


template<clT>
blSqStk<(a) T(s) >∷gtTop(T&x){//共(o) 有函(e) 数:(a) 若栈不空(c) (o) 则(e) 函数返回该栈栈顶元素的地
址


if(stte)eunfle; //判断栈空否,若栈空则函数返回

IEmpy()==urtras
returnelementtop];(r) 

}; 
returntrue;
s[//返回栈顶元素的值

template<clasT>
tam&optr<<(stream&os,SeqStack<T>&s)
{

//(o) 输(s) 出(e) 栈中元素(e) 的(a) 重载操(o) 作(o) os<<"top="<<stp<<edl; //输出栈顶位
置
foiti=.o;i+(o) //逐个输出栈中元素的
值


r(n0;i<=stp(.) +)(n) os<<seemeti]" 
;


.lns[<<
"
os<<endl;
returnos;


}; 

读取栈顶元素值的函数getTop(T&)与退栈函数Pop(T&)的区别在于前者没有改变
栈顶指针的值,后者改变了栈顶指针的值。

当栈满时要发生溢出,为了避免这种情况,需要为栈设立一个足够大的空间。但如果空
间设置得过大,而栈中实际只有几个元素,也是一种空间浪费。此外,程序中往往同时存在
几个栈,因为各个栈所需的空间在运行中是动态变化着的。如果给几个栈分配同样大小的
空间,则在实际运行时,可能有的栈膨胀得快,很快就产生了溢出,而其他的栈可能此时还有
许多空闲的空间。这时就必须调整栈的空间,防止栈的溢出。

例如,程序同时需要两个栈时,可以定义一个足够的栈空间。该空间的两端分别设为两
·84· 


个栈的栈底,用b[0](=-1)和b[1](=maxSize)指示。让两个栈的栈顶t[0]和t[1]都向
中间伸展,直到两个栈的栈顶相遇, 如图3.

才认为发生了溢出,3所示。


图3.

3 两个栈的情形

注意,每次进栈时t[加1,1] 退栈时t[减1,1]

0] t[减1; 0] t[加1。
两栈的大小不是固定不变的。在实际运算过程中,一个栈有可能进栈元素多而体积大
些,另一个栈则可能小些。两个栈共用一个栈空间,互相调剂,灵活性强。

在双栈的情形下,各栈的初始化语句为t[0]=b[0]=-1,t[1]=b[1]=maxSize。
栈满的条件为t[0]+1==t[1], 即当两个栈的栈顶指针相遇才算栈满;栈空的条件为
t[0]=b[0]或t[1]=b[1], 此时栈顶指针退到栈底。

程序3.

5 双栈的插入和删除操作的实
现
blPh(DulStck&DS,Tx,itd)
{//在(o) 双栈(u) 中插入(a) 元素(a) x。d(s) (o) =0,插入第(n) 0号栈;d≠0,插入第1号
栈


if(t[==t[rtras函数返回

DS.0]+1DS.1])eunfle;// 栈满
,
if(==t[// 栈顶指针加
1


d0)DS.0]++
;
t[1]


elseDS.--
;
DS.coDS.d]]=// 进
栈


Vetr[t[x;
returntrue;
}
;


blPp(DulStk&DS,T&x,intd)
{//从(o) 双栈(o) 中退出(a) 栈(a) 顶(c) 元素,(o) 通过x返回。d=0,从第0号栈退栈;d≠0,从第1号栈退
栈
if(t[DS.b[d])rturas函数返
回


DS.d]==enfle; // 栈空
,
x=Ver[t[// 取出栈顶元素的
值


DS.tDS.d]]
;
if(d==0)(c) D(o) t[0]--
;


st[
S.// 栈顶指针减
1
eleDS.1]++
;
returntrue;


}; 

n(个栈的情形有所不同,采用多个栈共享栈空间的顺序存储表示方式,处理十分

n>2)
复杂,在插入时元素的移动量很大,因而时间代价较高。特别是当整个存储空间即将充满
时,这个问题更加严重。解决的办法就是采用链接存储表方式作为栈的存储表示。

1.链式栈
3.3 
链式栈是线性表的链接存储表示。采用链式栈来表示一个栈,便于结点的插入与删除。
在程序中同时使用多个栈的情况下,用链接存储表示不仅能够提高效率,还可以达到共享存
储空间的目的。

从图3.4可知,链式栈的栈顶在链表的表头。因此,新结点的插入和栈顶结点的删除都
在链表的表头,即栈顶进行。下面给出链式栈的类声明。由于第2章给出的单链表结点是
·85· 


图3.

4 链式栈

用stut定义的,在链式栈的情形中可以直接使用,所以在程序3.

rc6中没有定义链式栈的
结点。

程序3.

6 链式栈的类定
义
#inlde<isram.


cuoteh>
#inlde"Lith//使用了单链表结
点


cus.
"
template<clasT>
clasLinkedStack{ //链式栈类定
义
public:


LinkedStack():top(NULL){} //构造函数,置空栈
~LinkdStack(){makeEmpty();}; //析构函数
voidPsh(T(e) x); //进栈
bolPop(T(u) &x); //退栈boolg(o) etTop(T&x)st; //读取栈顶元素
bolIEmpy()srtrtpNULL)?tuae;}

ostt{(n) (o) (c) eun(o==re:flintgetSie()ost;(n) (o) (c) /(s) /求栈的元素个数
voidmakeEmpt(c) (z) y();(n) //清空栈的内容

fidotam&optr<<(ostream&os,LinkedStack<T>&s);

//(r) 输(e) 出(n) 栈(s) 中(r) 元(e) 素的重载(e) 操(o) 作
private:
}; 
LinkNode<T> *top; //栈顶指针,即链头指
针


template<clasT>
idLikdStk<T>∷makEmpty()
{

//(v) 逐(o) 次删(n) (a) (r) 去(e) 链式(a) 栈中的元素(c) 直至(e) 栈顶指针为
空
LinkNode<T> *p;
whie(oNULL)


ltp!=//逐个结点释
放
{p=top;top=top->link;deletep;
}
}
;


template<clasT>
idLikdStk<T>∷Ph(Tx)
{

//(v) 将(o) 元素(n) 值(e) x插(a) 入链式栈的栈(u) 顶,(s) (c) 即链
头
LinkNode<T>*s=newLinkNode<T>(x); //创建新的含x结
点
if(s==NULL){cer<<"存储分配失败!"<<endl;exit(1);
}
s->link=top;toop=s;


}; 

template<clasT> 

blLikdStk<T>∷Pp(T&x){

//删(o) 除栈(n) 顶(e) 结点(a) ,返回被(c) (o) 删栈(o) 顶元素的值

·86· 


f(y()==e)e; //若栈空则不退栈,返回
LinkNode<T> *p=top;(r) //否则暂存栈顶元素
top=top->link; //栈顶指针退到新的栈顶位置
x=p->data;deletep; //释放结点,返回退出元素的值
returntrue; 

iIsEmpttrueturnfals

}; 

template<claT> 

blLikdStk(s) <T>∷getTop(T&x)const{

//返(o) 回栈(n) (o) 顶(e) 元素(a) 的值(c) 

iIsEmpttrureturnfalsl

f(y()==e)e; //若栈空则返回fx=top->data; //栈不空则返回栈顶(a) 元(e) 素的值
returntrue;

}; 

template<clT> 

intLinkedStack(a) <(s) T>∷getSize()
{
LinkNode<T> *p=top;intk=0;
whitNULL){o=oik;k++;
}


le(op!=tptp->ln
returnk;
}
;


template<clasT>
tam&o(s) ptr<<(stream&os,LinkedStack<T>&s)
{

//(o) 输(s) 出(e) 栈中元素(e) 的(a) 重载操(o) 作(o) os<<"栈中元素个数=<<sgSznl;//输出栈中元素个
数
LikNode<T> =t"
p;in.t0i;
e()<<ed//逐个输出栈中元素的
值


*pS.oti=(e) while(n) (p!=NULL)


{os<<p->data<<"";p=p->link;
}
os<<endl;
returnos;


}; 

如果同时使用
n 
个链式栈,其头指针数组可以用以下方式定义: 

LinkNode<T> *s=newLinkNode<T>[n]; 

在多个链式栈的情形中,k域需要一些附加的空间,但其代价并非很大。

lin

**3.4 
栈的应用之一———括号匹配
1.
举例说明,在一个字符串(b+c)d)中位置1和位置4有左括号“(,(”) 位置8和

位置11有右括号“)”。位置1的左括号匹配位置11的右括号,位置4的左括号匹配位置8 

的右括号。而对于字符串"(,(") 位置7的左

"a*(-" 

括号没有可匹配的右括号。
a+b))(位置6的右括号没有可匹配的左括号, 

我们的目的是建立一个算法,输入一个字符串,输出匹配的括号和没有匹配的括号。
·87· 


可以观察到,如果从左向右扫描一个字符串,那么每个右括号将与最近遇到的那个未匹
配的左括号相匹配。这个观察的结果使我们联想到可以在从左向右的扫描过程中把所遇到
的左括号存放到栈中。每当在后续的扫描过程中遇到一个右括号时,就将它与栈顶的左括
号(如果存在)相匹配,同时在栈顶删除该左括号。程序3.7给出相应的算法,其时间复杂度
为O(n)或Θ(n),其中n 是输入串的长度。 
程序3.7 判断括号匹配的算法
#include<iostream.h> 
#include<string.h> 
#include<stdio.h> 
#include"SeqStack.cpp" 
constintmaxLength=100; //最大字符串长度
voidPrintMatchedPairs(char*expression){ 
SeqStack<int>s(maxLength); //栈s存储
intj,length=strlen(expression); 
for(inti=1;i<=length;i++){ //在表达式中搜索“(”和“)” 
if(expression[i-1]== '(')s.Push(i); //左括号,位置进栈 
elseif(expression[i-1]== ')'){ //右括号 
if(!s.IsEmpty()&&s.Pop(j)) //栈不空,退栈成功 
cout<<j<<"与"<<i<<"匹配"<<endl; 
elsecout<<"没有与第"<<i<<"个右括号匹配的左括号!"<<endl; 
} 
}
while(!s.IsEmpty()){ //栈中还有左括号 
s.Pop(j); 
cout<<"没有与第"<<j<<"个左括号相匹配的右括号!"<<endl; 
} 
}
同时使用3个栈,稍微修改一下程序,就可以同时解决在C和C++程序中的“{”与“}”、
“[”与“]”、“(”与“)”的匹配问题。
**3.1.5 栈的应用之二———表达式的计算
在计算机中执行算术表达式的计算是通过栈来实现的。
1.表达式
如何将表达式翻译成能够正确求值的指令序列,是语言处理程序要解决的基本问题。
作为栈的应用实例,下面讨论表达式的求值过程。
任何一个表达式都是由操作数(亦称运算对象)、操作符(亦称运算符)和分界符组成。
通常,算术表达式有3种表示。
(1)中缀(infix)表示:<操作数> <操作符> <操作数>。例如,A +B。
(2)前缀(prefix)表示:<操作符> <操作数> <操作数>。例如,+AB。
(3)后缀(postfix)表示:<操作数> <操作数> <操作符>。例如,AB+。
我们平时所使用的表达式都是中缀表示。下面就是表达式的中缀表示: 
·88·

A +B*(C-D)-E/
F 
为了正确执行这种中缀表达式的计算,必须明确各个操作符的执行顺序。为此,为每个
操作符都规定了一个优先级,如表3.

1所示。一般表达式的操作符有4种类型:①算术操作
符,如双目操作符(+、-、*、/和%)以及单目操作符(-)。这些操作符主要用于算术操作
数。②关系操作符,包括<、<= 、== 、!=、>= 、>。这些操作符主要用于比较,不但适用
于算术操作数,而且适用于字符型操作数。③逻辑操作符,如与(&& )、或(|| )、非(!)。

④括号“(”和“)”。它们的作用是改变运算顺序。操作数可以是任何合法的变量名和常数。
表3.+中操作符的运算优先级

1C+

优先级1 2 3 4 5 6 7 
操作符-(单目),! *,/,% +,-<,<=,>,>= ==,!= && || 

C++规定一个表达式中相邻的两个操作符的计算次序:优先级高的先计算;如果优先
级相同,则自左向右计算;当使用括号时,从最内层的括号开始计算。

由于中缀表示中有操作符的优先级问题,还有可加括号改变运算顺序的问题,所以对于
编译程序来说,一般不使用中缀表示处理表达式。解决办法是用后缀表示(较常用)和前缀
表示。因为用后缀表示计算表达式的值只用一个栈,而前缀表示和中缀表示同时需要两个
栈,所以编译程序一般使用后缀表示求解表达式的值。

例如,日常使用中缀表达式
A 
+
B 
*(-E/F,5所示, 
R1,R2,R3,R4,R5为中间计算结果。
C-
D 
)计算的执行顺序如图3.

2. 
应用后缀表示计算表达式的值
中缀表示是最普通的一种书写表达式的形式,而且在各种程序设计语言和计算器中都
使用它。用中缀表示计算表达式的值需要利用两个栈来实现:一个暂存操作数;另一个暂
存操作符。利用"stch中定义的模板Stck类,建立两个不同数据类型的Sak对象。

ak." atc

下面讨论的是利用后缀表示计算表达式的值。后缀表示也称RPN 或逆波兰记号,它
是中缀表示的替代形式,参加运算的操作数总在操作符前面。例如,中缀表示
A 
+
B 
* 
(C-D)-E/
F 
所对应的后缀表示为ABCD-*+EF/-。

利用后缀表示计算表达式的值时,从左向右顺序地扫描表达式,并使用一个栈暂存扫描
到的操作数或计算结果。例如,与图3.

5所示的中缀表达式计算等价的后缀表达式计算顺
序如图3.因而括号在

6所示。在后缀表达式的计算顺序中已经隐含了加括号的优先次序, 
后缀表达式中不出现。


图3.5 中缀表达式的计算顺序图3.

6 后缀表达式的计算顺序

本节的讨论只涉及双目操作符,不考虑单目操作符。
通过后缀表示计算表达式值的过程(见图3.:顺序扫描表达式的每项,然后根据它的

7)
·89· 


类型做如下相应操作:如果该项是操作数,则将其压入栈中;如果该项是操作符<op>,则
连续从栈中退出两个操作数
Y 
和
X 
,形成运算指令
X 
<op>Y,并将计算结果重新压入栈
中。当表达式的所有项都扫描并处理完后,栈顶存放的就是最后的计算结果。

步扫描项项类型动作栈中内容

1 置空栈空
2 
A 
操作数进栈
A 
3 
B 
操作数进栈AB 
4 
C 
操作数进栈ABC 
5 
D 
操作数进栈ABCD 
6-操作符D、
C 
退栈,计算C-D,结果R1 进栈ABR1 
7* 操作符R1、
B 
退栈,计算B*R1,结果R2 进栈AR2 
8+ 操作符R2、
A 
退栈,计算A+R2,结果R3 进栈R3 
9 
E 
操作数进栈R3E 

10 
F 
操作数进栈R3EF 
11 / 操作符F、
E 
退栈,计算E/F,结果R4 进栈R3R4 
12 -操作符R4、R3 退栈,计算R3-R4,结果R5 进栈R5 

图3.

7 通过后缀表示计算表达式值的过程

下面通过模拟一个简单的计算器的+,-,*,/等运算,进一步说明后缀表达式的求值
问题。计算器接收浮点数,计算表达式的值。计算数据和操作都包含在类Calculator中,通
过一个简单的主程序来调用类的成员函数进行计算。

程序3.r类的定义

8Calculato
#inldth>


cue<mah.
#inlde<iteh>


cusram.
#inlde"Stk.pp


cuqS(o) cc"
lClltr{(a) (e) //(c) 模(a) 拟一(a) 个(c) 简(a) 单(o) 的计算器。此计算器对从键盘读入的后缀表达式求值(u) (s) 

public:
luaoitsz):z){} //构造函数

Cacltr(ns(sdoubleRun(chare[]); //执行表达式计算
voidClear(); 

private:
SqStck<double>s; //栈对象定
义void(e) Ad(a) dOperand(doublevalue); //进操作数
栈
blGet2Opends(double&left,double&right); //从栈中退出两个操作
数


}; void(o) DoOp(o) erator(c(a) (r) harop); //形成运算指令,进行计算

因为计算器只要开机就一直运行着,所以需要在开始计算表达式之前先调用成员函数
Clear()将栈清空。然后执行成员函数Run()输入一个后缀表达式,输入流以#结束。程序

3.acltr类各私有成员函数的实现。
9给出Cluao

·90· 


程序3.9 Calculator类私有成员函数的实现
voidCalculator∷DoOperator(charop){ 
//私有成员函数:取两个操作数,根据操作符op形成运算指令并计算 
doubleleft,right,vlaue;boolresult; 
result= Get2Operands(left,right); //取两个操作数 
if(result==true) //如果操作数取成功,计算并进栈 
switch(op){ 
case'+':value=left+right;s.Push(value);break; //加
case'-':value=left-right;s.Push(value);break; //减
case'*':value=left*right;s.Push(value);break; //乘
case/' ':if(right==0.0){ //除 
cerr<<"Divideby0!"<<endl; 
Clear(); //若除0,则报错,清栈
} 
else{value=left/right;s.Push(value);} 
break; 
} //没有除0,做除法 
elseClear(); //取操作数出错,清栈
}; 
boolCalculator∷Get2Operands(double&left,double&right){ 
//私有成员函数:从操作数栈中取出两个操作数 
if(s.IsEmpty()==true) //检查栈空否 
{cerr<<"缺少右操作数!"<<endl;returnfalse;} //栈空,报错
s.Pop(right); //取右操作数
if(s.IsEmpty()==true) //检查栈空否 
{cerr<<"缺少左操作数!"<<endl;returnfalse;} //栈空,报错
s.Pop(left); //取左操作数
returntrue; 
}; 
voidCalculator∷AddOperand(doublevalue){ 
//私有成员函数:将操作数的值value进操作数栈 
s.Push(value); 
}; 
所有的内部运算都在DoOperator()的控制下,以调用Get2Operands()开始。如果
Get2Operands()返回false,则表示操作失败,没有取到两个操作数,执行清栈处理;否则
DoOperator()执行字符变量op(+,-,*,/)所指定的操作,并将结果进栈。
计算器的主要工作是通过共有函数Run()完成计算后缀表达式的值。在Run()中,有
一个主循环,从输入流中读取字符,直到读入字符'#'时结束。如果读入的字符是操作符
('+','-','*',/' '),则调用函数DoOperator()完成相关的计算。如果读入的字符不是操作
符,则Run()把它看作一个操作数。
·91·

程序3.10 Calculator的实现
doubleCalculator∷Run(chare[]){ 
//读字符串并求一个后缀表达式的值。以字符'#'结束 
charch;doublenewOperand,result;inti=0; 
ch=e[i++]; 
while(ch!= '#'){ 
switch(ch){ 
case'+':case'-':case'*':case/' ': //是操作符,执行计算 
DoOperator(ch);break; 
default: 
newOperand= (double)ch-0' '; //转换为操作数 
AddOperand(newOperand); //将操作数放入栈中 
} 
ch=e[i++]; 
} 
returnresult; 
}; 
voidCalculator∷Clear(){ //清栈 
s.MakeEmpty(); 
}; 
在主程序中,可以先建立计算器对象CalculatorCALC,再执行计算程序CALC.Run(), 
输入表达式字符流之后,在栈顶就能得到预期的结果。
3.利用栈将中缀表示转换为后缀表示
使用栈可将表达式的中缀表示转换成它的前缀表示和后缀表示。由于篇幅所限,本节
仅讨论比较实用的将中缀表示转换为后缀表示的方法。
在中缀表达式中操作符的优先级和括号使得求值过程复杂化,把它转换成后缀表达式, 
可简化求值过程。为了实现这种转换,需要考虑各个算术操作符的优先级,如表3.2所示。
表3.2 各个算术操作符的优先级
操作符ch # ( *,/,% +,- ) 
isp 0 1 5 3 6 
icp 0 6 4 2 1 
isp为栈内(instackpriority)优先数,icp为栈外(incomingpriority)优先数。从表3.2 
中可以看到,左括号的栈外优先数最高,它一来到立即进栈,但当它进入栈中后,其栈内优先
数变得极低,以便括号内的其他操作符进栈。其他操作符进入栈中后优先数都加1,这样可
体现在中缀表达式中相同优先级的操作符自左向右计算的要求,让位于栈顶的操作符先退
栈并输出。操作符优先数相等的情况只出现在括号配对或栈底的“#”与输入流最后的“#” 
配对时。前者将连续退出位于栈顶的操作符,直到遇到“(”为止,然后将“(”退栈以对消括
号;后者将结束算法。
扫描中缀表达式将它转换为后缀表达式的算法描述如下。
·92·

(1)操作符栈初始化,将结束符#进栈。然后读入中缀表达式字符流的首字符ch。
(2)重复执行以下步骤,直到ch='#',同时栈顶的操作符也是'#',停止循环。
① 若ch是操作数直接输出,读入下一个字符ch。
② 若ch是操作符,判断ch的优先级icp和当前位于栈顶的操作符op的优先
级isp: 
. 若icp(ch)>isp(op),令ch进栈,读入下一个字符ch。
. 若icp(ch)<isp(op),退栈并输出。
. 若icp(ch)==isp(op),退栈但不输出,若退出的是“(”,读入下一字符ch。
(3)算法结束,输出序列即为所需的后缀表达式。
例如,给定中缀表达式为A +B *(C -D )-E/F,应当转换成ABCD -*+EF/-, 
按上述算法应执行的转换过程(包括栈的变化和输出)如图3.8所示。
步扫描项项类型动 作栈的变化输 出
0 '#'进栈# 
1 A 操作数# A 
2 + 操作符isp('#')<icp('+'),进栈#+ A 
3 B 操作数#+ AB 
4 * 操作符isp('+')<icp('*'),进栈#+* AB 
5 ( 操作符isp('*')<icp('('),进栈#+*( AB 
6 C 操作数#+*( ABC 
7 - 操作符isp('(')<icp('-'),进栈#+*(- ABC 
8 D 操作数#+*(- ABCD 
9 ) 操作符isp('-')>icp(')'),退栈
' (' ==' )' ,退栈
#+*( 
#+* 
ABCD - 
ABCD - 
10 - 操作符isp('*')>icp('-'),退栈
isp('+')>icp('-'),退栈
isp('#')<icp('-'),进栈
#+ 
##
- 
ABCD -* 
ABCD -*+ 
ABCD -*+ 
11 E 操作数#- ABCD -*+E 
12 / 操作符isp('-')<icp(/' '),进栈#-/ ABCD -*+E 
13 F 操作数#-/ ABCD -*+EF 
14 # 操作符isp(/' ')>icp('#'),退栈
isp('-')>icp('#'),退栈
结束
#- 
# 
ABCD -*+EF/ 
ABCD -*+EF/- 
图3.8 利用栈的转换过程
3.2 栈与递归
3.2.1 递归的概念 
递归(recurve)在计算机科学和数学中是一个很重要的工具,它在程序设计语言中用来
定义句法,在数据结构中用来解决表或树形结构的搜索和排序等问题。数学家在研究组合
问题时用到递归。递归是一个重要的课题,在计算方法、运筹学模型、行为策略和图论的研
·93·

究中,从理论到实践,都得到了广泛的应用。本节将对递归做简要的说明,并举例说明它的
各种应用。在以后各章中将利用它来研究诸如树、搜索和排序等问题。
例如,在计算浮点数x 的n(自然数)次幂时,一般可以把它看作n 个x 连乘: 
xn =x ×x ×x × … ×x ×x .......................... n个 
而在求前n 个自然数的和时,则可以把它看作是n 个自然数的连加: 
S(n)=Σn 
i=1
i=1+2+3+ … + (n -1)+n 
如果已经求得xn 或S(n),那么在计算xn+1或S(n+1)时,可以直接利用前面计算过的
结果以求得答案:xn+1=xn ×x 或S(n+1)=S(n)+ (n+1)。这样做既简洁又有效。
像这种利用前面运算来求得答案的过程称为递归过程。
在数学及程序设计方法学中为递归下的定义:若一个对象部分地包含它自己,或用它
自己给自己定义,则称这个对象是递归的;而且若一个过程直接地或间接地调用自己,则
称这个过程是递归的过程。
在以下3种情况下,常常要用到递归的方法。
1.定义是递归的
数学上常用的阶乘函数、幂函数、斐波那契数列等,它们的定义和计算都是递归的。例
如阶乘函数,它的定义为
n! = 1, n =0 
n(n -1)!, n >0 { 
对应这个递归的函数,可以使用递归过程来求解。 
程序3.11 计算阶乘的递归函数
longFact(longn){ 
if(n==0)return1; //终止递归的条件
elsereturnn*Fact(n-1); //递归步骤
}
在程序3.11中利用了if…else…语句把递归结束条件与其他表示继续递归的情况区
别开来。if语句块判断递归结束的条件,而else语句块处理递归的情况。在计算n! 时,if 
语句块判断唯一的递归结束条件n = 0,并返回值1;else语句块通过计算表达式n(n- 
1)!,并返回计算结果以完成递归。
图3.9描述了执行Fact(4)的函数调用顺序。假设最初是主程序main()调用了函数。
在函数体中,else语句以参数3,2,1,0执行递归调用。最后一次递归调用的函数因参数n 
=0执行if语句。一旦到达递归结束条件,调用函数的递归链中断,同时在返回的途中计
算1*1,2*1,3*2,4*6,最后将计算结果24返回给主程序。
还可以举出一些函数递归定义的例子。但仅从以上两个例子中已经可以得到以下三点
认识。
(1)对于一个较为复杂的问题,当能够分解成一个或几个相对简单的且解法相同或类
似的子问题时,只要解决了这些子问题,原问题就迎刃而解了。这就是分而治之的递归求解
方法,也称减治法或分治法。参看图3.9,计算4!时先计算3!。只要求出3!,就可以求
·94·

图3.

9 求解阶乘n!的过程

出4!。

(2)当分解后的子问题可以直接解决时,就停止分解。这些可以直接求解的问题称为
递归结束条件。如图3.1。
9中递归结束条件是0!=

(3)递归定义的函数可以用递归过程来编程求解。递归过程直接反映了定义的结构。
2.数据结构是递归的
某些数据结构就是递归的。例如,链表就是一种递归的数据结构。链表结点LinkNode 

的定义由数据域data和指针域link组成;而link则由LinkNode定义。
从概念上讲,可将一个头指针为first的单链表定义为一个递归结构: 
(1)first为NULL,是一个单链表(空表);
(2)first≠NULL,其指针域指向一个单链表,仍是一个单链表。
对于递归的数据结构,采用递归的方法来编写算法特别方便。例如,搜索非空单链表最

后一个结点并返回其地址,就可以使用递归形式的过程。

程序3.

12 搜索单链表最后一个结点的算
法
template<clasT>
LinkNode<T> *FidRer(LinkNode<T> *f)
{


f()(n) L;

if==NULLretrn(a) NUL
sf(ikN(u) r


eleif->ln==ULL)trnf;
elertridRaf->ln


seunFner(ik);(u) (e) }
;


如果f->link==NULL,表明
f 
已到达最后一个结点,此时可返回该结点的地址, 
否则以f->link为头指针继续递归执行该过程。

又例如,在一个非空单链表中搜索其数据域的值等于给定值
x 
的结点,并在首次找到
时返回其结点地址。在此算法中,递归结束条件有两个:①链表已经全部扫描完但没有找
到满足要求的结点,此时f==NULL;②在f!=NULL同时f->data==x时找到要
求的结点。

·95· 


程序3.

13 在以f为头指针的单链表中搜索其值等于给定值x的结
点
template<clasT>
LinkNode<T> *Sch(LinkNode<T> *f,T&x)
{


f()(r) n; //搜索失败

if==NULL(a) (e) retr
sf(aax)(u) e//搜索成
功


eleif->dt==rtrnf;
}; 
elertrerh(ik(u) ,x); //从下一个结点开始继续搜
索


seunSacf->ln

不仅是单链表,第5章介绍的树形结构,是以多重链表作为其存储表示的,它也是递归
的结构。所以关于树的一些算法,也可以用递归过程来实现。

3.问题的解法是递归的
有些问题只能用递归方法来解决。一个典型的例子就是汉诺塔(TowerofHanoi)问
题。问题的提法:“传说婆罗门庙里有一个塔台,台上有3根标号为A,B,
C 
的用钻石做成
的柱子,在
A 
柱上放着64个金盘,每个都比下面的略小一点。把
A 
柱上的金盘全部移到
C 
柱上的那一天就是世界末日。移动的条件是一次只能移动一个金盘,移动过程中大金盘不
能放在小金盘上面。庙里的僧人一直在移个不停。因为全部的移动是263-1次,如果每秒
移动一次,需要500亿年。” 

一位计算机科学家提出了一种快速求解汉诺塔问题的递归解法。用图解来示意4个盘
子的情形。设
A 
柱上最初的盘子总数为n,问题的解法如下。
如果
n 
=1,则将这一个盘子直接从
A 
柱移到
C 
柱上。否则,执行以下3步: 

(1)用
C 
柱做过渡,将
A 
柱上的n-1个盘子移到
B 
柱上;
(2)将
A 
柱上最后一个盘子直接移到
C 
柱上; 
柱上
(
。
3)用
A 
柱做过渡,将
B 
柱上的n-1个盘子移到
C 
移动过程如图3.10所示,图中
n 
=4。利用这个解法, 
将移动
n 
个盘子的汉诺塔问题归结为移动n-1个盘子的
汉诺塔问题。与此类似,移动n-1个盘子的汉诺塔问题又
可归结为移动n-2个盘子的汉诺塔问题……最后总可以
归结到只移动一个盘子的汉诺塔问题,这样问题就解决了。

现在给出根据上述解法而得到的求解
n 
阶汉诺塔问题
图3.的算法。

10 汉诺塔问题的解答

程序3.

14 求解n阶汉诺塔问题的算
法
#inlde<isram.//输入输出流文
件


cuoteh>
vodHaoitn,hrA,hrB,hrC)
{


ini(ncacaca
if(n==1)
cout<<"Movetopdiskfrompeg"<<A<<"topg"
else{
<<C<<endl; //只有一个盘子,(e) 直接移
动


Hanoi(n-1,A,C,B); //将上面n-1个盘子移到B
柱
cout<<"Movetopdiskfrompeg"<<A<<"topeg"
·96
·




<< C <<endl; //最后一个移到C柱
Hanoi(n-1,B,A,C); //将B柱n-1个盘子移到C柱
} 
}; 
上述递归过程执行的顺序可用如图3.11所示n =3的图解描述。
图3.11 汉诺塔问题的递归调用树
上、下层表示程序调用关系,同一模块的各子模块从左向右顺序执行。各个处于递归结
束位置的子模块执行盘片移动功能,最右端子模块执行结束后就实现了上一层模块的功能。
编号①②…给出执行次序。
若设盘子总数为n,在算法中盘子的移动次数moves(n)为
moves(n)= 0, n =0 
2moves(n -1)+1, n >0 { 
注意,递归与递推是两个不同的概念。递推是利用问题本身所具有的递推关系对问题
求解的一种方法。采用递推法建立起来的算法一般具有重要的递推性质,即当求得问题规
模为i-1的解后,由问题的递推性质,能从已求得的规模为1,2,…,i-1的一系列的解, 
构造出问题规模为i 的解。若设这种问题的规模为n,当n =0或n =1时,解或为已知, 
或能很容易地求得。例如,求n!,求等比级数的第n 项等。
递推问题可以用递归方法求解,也可以用迭代(重复)的方法求解。
3.2.2 递归过程与递归工作栈
在图3.9所示的例子中,主程序调用Fact(4)属于外部调用,其他调用都属于内部调用, 
即递归过程在其过程内部又调用了自己。调用方式不同,调用结束时返回的方式也不同。
外部调用结束后,将返回调用递归过程的主程序。内部调用结束后,将返回到递归过程内部
本次调用语句的后继语句处。此外,函数每递归调用一层,必须重新分配一批工作单元,包
括本层使用的局部变量、形式参数(实际是上一层传来的实际参数的副本)等,这样可以防止
使用数据的冲突,还可以在退出本层,返回到上一层后恢复上一层的数据。
1.递归工作栈
为了保证递归过程每次调用和返回的正确执行,必须解决调用时的参数传递和返回地
·97·

址问题。因此,在每次递归过程调用时,必须做参数保存、参数传递等工作。在高级语言的
处理程序中,是利用一个递归工作栈来处理的, 12 所示。

如图3.


图3.

12 函数递归调用时的活动记录

每层递归调用所需保存的信息构成一个工作记录。通常它包括如下内容。

(1)返回地址:即上一层中本次调用自己的语句的后继语句处。
(2)在本次过程调用时,为与形式参数结合的实际参数创建副本。包括传值参数和传
值返回值的副本空间,引用型参数和引用型返回值的地址空间。
(3)本层的局部变量值。
在每进入一层递归时,系统就要建立一个新的工作记录,把上述项目录入,加到递归工
作栈的栈顶。它构成函数可用的活动框架。每退出一层递归,就从递归工作栈退出一个工
作记录。因此,栈顶的工作记录必定是当前正在执行的这一层的工作记录。所以又称为活
动记录。

以图3.9所示的计算Fact(4)为例,介绍递归过程中递归工作栈和活动记录的使用。
参见程序3.at(的调用由主程序执行。当函数运行结束后控制返回到

15 。最初对Fc4)
RetLoc1处,在此处将函数的返回值24(即4!) 赋予整型变量n,RetLoc1在赋值运算符“=” 
处。函数Ft(4)递归调用Ft(3)时,调用返回处在R2。在此处计算n*(1)!, 

acacetLocnRetLoc2在乘法运算符“*”处。

程序3.15 计算阶乘的递归算法Fact(4) 

voidmain()
{
longn; // 调用Fact(4)时记录进
栈
n=Fact(4)
;


RetLoc1 ↑ // 返回地址RetLoc1在赋值语
句
cout<<n<<endl;
}
;


logFt(n

nalgn){ 
intte(c) mp;(o) if(n==0)return1; // 活动记录退栈
elsetemp=n*Fact(n-1);// 调用Fact(n-1)时活动记录进栈

↑ // 返回地址RtLoc2在计算语句
RetLoc2returntemp; // 活动记录退栈(e) }


·98· 


就Fact函数而言,每层调用所创建的活动记录由3个域组成:传递过来的实际参数值
n 的副本、返回上一层调用语句的下一条语句的位置和局部变量temp如图3.13(a)所示。
Fact(4)的执行启动了一连串5个函数调用。图3.13(b)描述了每次函数调用时的活动
记录。主程序外部调用的活动记录在栈的底部,随内部调用一层层地进栈。递归结束条件
出现于函数Fact(0)的内部,从此开始一连串的返回语句。退出栈顶的活动记录,控制按返
回地址转移到上一层调用递归过程处。
图3.13 计算Fact时活动记录的内容
2.用栈实现递归过程的非递归算法
对于递归过程,可以利用栈将它改为非递归过程。此时,可以先通过一个实例了解过程
图3.14 计算斐波那契数列的递归调用树
执行时的情况,直接考虑非递归算法。例如,求斐波那契数列的第n 项Fib(n)的公式为
Fib(n)= 
n, n =0或1 
Fib(n -1)+Fib(n -2), n ≥2 { 
它对应的递归过程如下。 
程序3.16 斐波那契数列的计算
longFib(longn){ 
if(n<=1)returnn; //终止递归的条件
elsereturnFib(n-1)+ Fib(n-2); 
//递归步骤
}; 
其递归计算的次序可用如图3.14所示的递归
调用树来描述。为了计算Fib(4),必须先计算
Fib(3);为了计算Fib(3),必须先计算Fib(2), 
再计算Fib(1)和Fib(0),Fib(1)和Fib(0)可
以直接求值。求出Fib(1)与Fib(0)后,可以得
到Fib(2)的解,求出Fib(2)与Fib(1)后,可以
·99·

得到Fib(的解……求解的顺序在图3.

3) 14上用数字①②③…表示。
为此,可以先计算Fib(1),从Fib(4)一直向左下走下去。为了回退,需要用栈记忆回退
的路径,以便退回计算。另外为了区分是从左侧退回还是从右侧退回,需要在栈结点中增加
ag tag=tag=

一个标志信息t。向左递归,1;向右递归,2。

程序3.

17 用栈帮助求解斐波那契数列的非递归算
法
#inlde"LikdSak.pp


cunetcc"
structNode{ //栈结点的类定
义
longn; //记忆走过的
n
}; 
inttag; //区分左、右递归的标
志


logFbalgn){ //用栈求解Fb(n)的值

ninci(
i
LikedStack(o) <(n) Node>S;Nodew;longsum=0;do{(n) 

whie(n>1){n=n;w.a=Psh(w);n--;}

lw.tg1;S.
u
sum=sum+n;
whie(IEmpy()==ase)
{


lS.stfl
S.ow)
;


Pp(
if(tg==1)


w.a{w.ta=Psh(w);n=w.-2;bek;}
g2;S.unra
}
}whie(IEmpy()==ase)
;


lS.stfl
returnsum;
}
;


该算法执行时栈的变化如图3.图中显示了各

15所示。每次大循环中包含两个小循环, 
小循环执行后栈中的内容以及
n 
的值和sum的计算。最后在sb(的值。

um中得到Fin) 


图3.ib(时栈的变化

15 用栈求解斐波那契数列的第
n 
项Fn) 

3.用迭代法实现递归过程
在图3.计算Fib(需要先计算

14所示的计算斐波那契数列的递归调用树中, 4)时, 
Fib(3),再计算Fib(2);计算Fib(3)时,需要先计算Fib(2),再计算Fib(1)……因此,需重复
·100·