第三章 栈和队列第 1页
,数据结构,
第三章 栈和队列第三章 栈和队列第 2页要求：
对栈和队列的存储方式及基本操作有较 深刻 的理解。理解栈和队列的概念
，存储表示，进栈、退栈和进队、出队操作的算法，初步了解栈的基本应用如表达式的求值,递归 的设计实现等。
重点：
栈和队列的基本操作，栈在实现 递归 中的应用。
第三章 栈和队列第三章 栈和队列第 3页主要内容
1、栈
抽象数据类型栈的定义
栈的表示与实现
2、栈的典型应用 —— 表达式求值
表达式的传统标记法 ——中缀标记法
简单算术表达式求值算法 ——算符优先算法
3、栈与递归过程
递归求解问题
递归过程的实现
递归过程转换成非递归过程第三章 栈和队列第 4页
4、队列
队列的逻辑结构
队列的抽象数据类型
链队列 —— 队列的链式存储结构
循环队列 —— 队列的顺序存储结构
双端队列
队列的应用举例
离散事件模拟主要内容第三章 栈和队列第 5页第三章 栈和队列两种重要的 受限 线性结构,栈 (Stack)和队列 (Queue)。
从 数据结构 角度看，栈和队列也是线性表，其特殊性在于栈和队列的 基本操作是线性表操作的子集 。 它们是 操作受限 的线性表，即可称为限定性的数据结构 。但从 数据类型 角度看，它们又是和线性表大不相同的两类重要 的抽象数据类型。
第三章 栈和队列第 6页第三章 栈和队列三者的操作规则比较：
线性表,可以在表的 任何位置 上插入、删除元素。
栈,对栈 仅 限定 在表的 一端 （表尾）进行插入或删除操作。
队列,限定在表的 一端 进行 插入,而在 另一端 删除 元素。
因此，从 ADT的角度看，栈、队列和线性表是不相同的。
第三章 栈和队列第 7页
栈的定义定义,栈（ Stack） 是限定 仅 在表的 一端 进行插入或删除操作的 线性表 。
在栈中能进行插入和删除的一端称为 栈顶 （ top），相应地另一固定端称为 栈底 （ bottom）。将一个元素放入栈中的操作叫做 进栈或压栈,从栈顶取出一个元素的操作叫做 出栈或弹出 。不含元素的空表称为空栈。
栈的存取操作符合 后进先出 （ Last In First Out,LIFO） 或先进后出 （ First In Last Out,FILO） 故 栈又称为后进先出线性表,简称
LIFO结构 。
1、栈
a n
,
,
,
a 2
a 1
栈底栈顶出栈 进栈第三章 栈和队列第 8页栈的基本性质
1) 集合性,该结构由若干个有限的 同类型元素 集合而成；
2) 线性性,除线底外，栈中任一元素均有唯一的前驱，除线顶外，
栈中任一元素均有唯一的后继；
3) 受限制的运算,仅 允许在栈顶压入、弹出；
4) 数学性质,当 n个编号元素依某种顺序压入，且可任意弹出时，
所能获得的 编号元素排列 的数目为。
)(
!!
)!2(
1
1
1
1
2
nn
n
n
C
n
C n nn
其中 n为输入序列长度即编号元素个数,cn为可能的排列数目。
由公式（ *）产生的数列称为 卡塔南数列 。
1、栈第三章 栈和队列第 9页示例 用铁路调度站表示栈出栈 进栈设有 A,B,C三列车厢，则出栈时可能的编号元素排列为 ABC
,ACB,BAC,BCA,CBA共五种。 (无 CAB)
.5!3 45641!3!3 )!32(13 13C
.14!4 567851!4!4 )!42(14 14C
若 A,B,C,D四列车厢，则应有 14种排列：
第三章 栈和队列第 10页
栈的抽象数据类型定义栈是一种强限制的数据类型。在栈上仅能在 特定的一个位置 上定义 有限几种操作 。
Specification ADT Stack
Elements,所涉及对象的数据类型明显地取决于应用，故数据元素可以是 各种类型 的，只要同 属一个数据对象 即可。
Structure,数据元素之间 呈线性关系 。假设栈中有 n个数据元素
(a1,a2,···,an)，则对每一个元素 ai(i=1,2,··,n-1)，都存在关系
<ai,ai+1>，并且 a1无前驱,an无后继。但是，栈是一种受限的线性结构，该结构使后进栈的元素先出栈。
Operation,栈通常包含下面的基本操作，这些操作中除了 InitStack之外，都要求栈 S已存在。
1、栈第三章 栈和队列第 11页
ADT Stack{
数据对象,D={ai|ai∈ ElemSet,i=1,2,…,n,n>=1}
数据关系,R={<ai,ai+1>|ai,ai+1 ∈ D,i=1,2,…,n}
基本操作：
InitStack( &S )； 初始化操作生成一个空栈 S
DestroyStack( &S ); 释放栈
ClearStack( &S ) ； 清空栈
Push( &S,x )； 入栈操作
Pop( &S,&e )； 出栈操作
GetTop( S,&e ) ； 取栈顶元素函数
EmptyStack( &S )； 置栈空操作
int StackLength( S ); 求当前栈中元素个数
}
栈的抽象数据类型定义第三章 栈和队列第 12页
栈的简单应用示例例 3-1 输入字符串。用‘ # ’表示退格符，即它使前一个字符无效；用‘ @ ’表示退行符，以表示此前整行字符均无效。编写行输入处理过程，内设一个栈来逐行处理从终端输入的字符串。每次从终端接收一个字符后先作如下判别：如果它既不是退格符也不是退行符，则将该字符插入栈顶；如果是一个退格符，则从栈顶删去一个字符；如果它是一个退行符，就把字符域清为空栈。
比如，若键入
BGE##EGIM#N
RAD(A@ READ(A);
则实际有效的是下面两行
BEGIN
READ(A);
第三章 栈和队列第 13页
//设 s为栈。本算法从终端接收一个正文文件并逐行传送至调用过程的数据区
Line_Edit(){
InitStack( S );
ch = getchar()； //从终端接收一个字符
while( ch != EOF )
{ while( ch != EOF && ch !=?\n? )
{ switch(ch){
case?#?,Pop(s,c); break; //若栈非空则退栈
case?@?,ClearStack(s); break; //将栈重新设置为空域
default,Push(s,ch); break; //有效字符入栈
}；
ch = getchar()
} //继续接收下一字符
//将自栈底至栈顶的栈内字符作成一行,并传送至调用过程的数据区,
ClearStack(s);
if( ch != EOF ) ch = getchar()
//继续接收下一行，先接收下一行第一个字符
}
} 算 法 3.1
第三章 栈和队列第 14页顺序栈 —— 栈的顺序存储结构用一维数组 S(1:arrmax)表示栈。
3
2
1
3 ` C`
2 ` B`
1 ` A `
S(1:arrmax) S(1:arrmax)
arrmaxarrmax
Top=0
Top=
非空栈空 栈栈顶栈底
栈的表示和实现第三章 栈和队列第 15页
const int MAX_STACK = 1000;
struct SqStkTp{
ElemType Element[MAX_STACK];
int Top;
};
InitStack( SqStkTp &S);
//设定一个空的栈 S
Status isStackEmpty( SqStkTp S );
//若 S为空栈，则返回 true，否则返回 false
Status Push( SqStkTp &s,ElemTp x );
//若栈 S不满，则在栈顶插入 x，并返回函数值 true，否则栈的状态不变且返回函数值 false
栈的 ADT表示
栈的表示和实现第三章 栈和队列第 16页
ElemTp Pop( SqStkTp &s );
//若栈不空，则删去栈顶元素并返回元素值，否则返回空元素
NULL
ElemTp GetTop(SqStkTp s );
//若栈不空，则返回栈顶元素，但 s.top
//保持不变，否则返回空元素 NULL
ClearStack(SqStkTp &s );
//若 S为空栈，即 s.top=0
int CurrentSize(SqStkTp s );
//返回当前栈中元素个数，即 s.top
栈的 ADT表示第三章 栈和队列第 17页部分实现
InitStack( SqStkTp &s)
{ s.top = 0
}//init_stack
Status isStackEmpty(SqStkTp s)
{
return ( s.top == 0 )? True,False;
} //empty_stack
Status Push( SqStkTp &s,ElemTp x )
{ if( s.top == MAX_STACK )
return false;
s.top++;
s.elem[s.top] = x;
return True;
} //push_stack
栈的 ADT实现第三章 栈和队列第 18页
ElemTp Pop( SqStkTp &s )
{
if( s.top == 0 ) return;
s.top--;
return s.elem[s.top+1]
} //pop_stack
ElemTp GetTop( SqStkTp s )
{
if( s.top == 0 ) return;
return s.elem[s.top]
} //gettop_stack
ClearStack( SqStkTp &s )
{
s.top = 0
} //clear_stack
栈的 ADT实现第三章 栈和队列第 19页
int CurrentSize (SqStkTp s )
{
return s.top;
} //currend_size_stack
注 1,函数 isStackEmpty的体亦可写为
return ( s.top == 0 );
注 2,亦可在接口节定义判栈满函数
Status isStackFull (SqStkTp s)
{
reutrn ( s.top == MAX_STACK )
} //full_stack
栈的 ADT实现第三章 栈和队列第 20页栈空,ls == NULL;
栈满,当内存分配无法实现时（堆区满） ;
进栈,在表头插入 ;
出栈,从表头删除 ;
即进栈、出栈操作均限制在单链表的表头端进行。
数据结构的描述
elemtype … … //任何一种数据类型
typedef struct tlkstktp{
ElemType elem;
tlkstktp *Next
} *lkstktp;
^…Ls
栈顶 栈底链式栈 —— 栈的链式存储结构设不带头结点
栈的表示和实现第三章 栈和队列第 21页一个链栈由其栈顶指针 ls唯一确定。
多个链栈可共享内存中的堆 (heap)区域。
链栈为满的条件：堆区满。 new(p)过程无法实现内存分配。
^
ls
data next
栈顶栈底
多栈共享存储区的链接分配 —— 链栈第三章 栈和队列第 22页
PushStack(lkstktp &ls; elemtp x)
{ //算法中 p为 结点 类型指针变量
p = new(ElemType); p->elem = x;
p->next = ls;
ls = p
} //push_stack
elemtp PopStack(lkstktp &ls)
{ //算法中 p为 结点 类型指针变量
if( ls == NULL )
return NULL // pop为 elemtp类型变量
p = ls; ls = p->next;
pop = p->elem;
free(p);
return pop;
} //pop_stack
栈的表示和实现第三章 栈和队列第 23页目的,提高存储空间的使用效率，并减少发生栈上溢的可能性。
示例 两个栈共享一维数组空间栈可利用的最大空间,有可能大于整个数组的一半。
上溢情况,两个栈顶相遇。
双栈的类 C描述
#define m = maxsize; // 两个栈的容量之和
Elemtp = 任何一种数据类型
struct dustktp{
elemtp elem[m];
int top[2];
};
空闲区栈 1底 栈 1顶 栈 2底栈 2顶
两个栈共享一个存储区第三章 栈和队列第 24页
init_stack( dustktp &s,int sno)
{
if( sno == 1 ) s.top[0] = 0;
else s.top[1] = m + 1
} //init_stack
push_stack( dustktp &s,elemtp x,int sno )
{ if( s.top[0]+1 == s.top[1] )
return stack_over_flow;
switch( sno ){
case 1,s.top[0]++; break;
case 2,s.top[1]--; break;
}
s.elem[s.top[sno-1]] = x
} //push_stack
两个栈共享一个存储区第三章 栈和队列第 25页
Status pop_stack( dustktp &s,elemyp &x,int sno )
{ if( empty( s,sno ))
return stack_under_flow;
x = s.elem[s.top[sno-1]];
switch( sno ){
case 1:s.top[0]--; break;
case 2:s.top[1]++; break;
}
} //pop_stack
Status gettop_stack(dustktp s,elemyp &x,int sno)
{ if( empty(s,sno))
return stack_empty;
s.elem[s.top[sno-1]]
} // top_stack
两个栈共享一个存储区第三章 栈和队列第 26页
Status empty( dustktp s,int sno)
{ switch( sno ){
case 1,return(s.top[0] = 0); break;
case 2,return(s.top[1] = m+1); break;
}
} //empty
Status full(dustktp s)
{ return (s.top[0]+1 >= s.top[1]);
}
注,过程 push_stack中
if( s.top[0]+1 = s.top[1] )…;
亦可改写成
if( full(s)) ···;
两个栈共享一个存储区第三章 栈和队列第 27页表达式的成分操作数 (Operand),常数或常数标识符、变量标识符、函数等运算符 (Operator),算术运算符、关系运算符、逻辑运算符等界限符 (Delimiter),左括号、右括号、表达式结束符等表达式的分类算术表达式,如 b*b - 4*a*c
关系表达式,如 b*b - 4*a*c >=0
布尔表达式,如 (a<>0) AND (b*b - 4*a*c>=0)
传统标记法 —— 中缀标记法特点,运算符出现在操作数之间
表达式的传统标记法 —— 中缀标记法
2、栈的典型应用示例 —— 表达式求值第三章 栈和队列第 28页示例 计算 8-(3+2× 6)/5+4
8-(3+2× 6)/5+4
= 8-(3+12)/5+4
=8-15/5+4
=8-3+4
=5+4
=9
表达式的传统标记法 —— 中缀标记法
2、栈的典型应用示例 —— 表达式求值第三章 栈和队列第 29页简单算术表达式求值算法 —— 算符优先算法讨论简单算术表达式的求值问题。
op算符界限符运算符
#),(,:
/,,,:
算符优先法,根据算术四则运算的规则亦即运算优先关系的规定，实现对表达式的编译或解释执行。
使用 栈 实现简单算术表达式的求值运算。
依据算术四则运算的规则，在运算的每一步中。任何两个相继出现的算符 θ1和 θ2之间的优先关系，可能是
θ1<θ2 θ1的优先数低于 θ2
θ1=θ2 θ1的优先数等于 θ2
θ1>θ2 θ1的优先数高于 θ2
第三章 栈和队列第 30页算符间的优先关系表说明：
1）‘ + ’,‘ - ’,' * '和 ' / '为 θ1时的优先性均低于 '(',但高于 ' ) ' ；
2）当 θ1=θ2 时，令 θ1>θ2 ;
3） '(' = ') '表示当左、右括号相遇时，括号内的运算已经完成；
4） ' # '是表达式的结束符。设表达式的最左边也虚设一个 #符，以构成整个表达式的一对“括号”，
5） ‘ (’与‘ # ’,') '与 '('以及 ' # '与 ') '之间无优先关系，若出现此类情况，应是语法错误。下面的讨论中，假定不会出现语法错误；
6） ' # ' = ' # '表示整个表达式求值完毕。
简单算术表达式求值算法 —— 算符优先算法
θ
2
θ
1
+ - * / ( ) #
+ > > < < < > >
- > > < < < > >
* > > > > < > >
/ > > > > < > >
( < < < < < =
) > > > > > >
# < < < < < =
第三章 栈和队列第 31页
operandtype exp_reduced() //返回结果值
/*算术表达式求值的算符优先算法。假定从终端输入的表达式无语法错误，以‘ #’作结束符。设 OPTR和 OPND分别为运算符栈和操作数栈,OP为运算符的集合 */
{
InitStack(OPTR)；
Push(OPTR,'#?)；
InitStack(OPND)；
//栈初始化，并在运算符栈的栈底压入表达式左端的虚设字符 #
w = getchar()； {从终端接收一个字符 }
中缀简单算术表达式的求值算法接下页第三章 栈和队列第 32页
while(!((w==?#?) && (GetTop(OPTR) == '#')))
{ if( !IN(w,op )){Push(OPND,w); w=getchar()}
else
switch(precede(GetTop(OPTR),w)){ //比较优先级
case?<?,Push(OPTR,w);w=getchar(); break;
//栈顶元素优先权低，运算符入栈
case?=?,x =pop(OPTR);w=getchar(); break;
//左括号遇右括号,脱括号并接收下一字符
case?>?,theta = Pop(OPTR);
b=Pop(OPND);a =pop(OPND);
Push(OPND,operate(a,theta,b))
/*运算符及两个操作数分别退栈，
并将运算结果入操作数栈 */
}} //CASE WHILE
return(GetTop(OPND)) {返回最终结果值 }
} //exp_reduced
承上页第三章 栈和队列第 33页例 3-2 利用算法 exp_reduced对算术表达式 3*(7-2)求值
，其操作过程如下
#
OPTR栈 OPND栈
# 3
#* 3
3*#
(
3*#
(
7
3*(7-2)# 初始化步骤 1 w='3'
步骤 2 w='*'
步骤 3 w=' ('
步骤 4 w='7'
转下一幻灯片
中缀简单算术表达式的求值算法优先级：‘ #‘ <?*‘ –?*‘进栈优先级：‘ *’ <?)‘ –?(‘进栈第三章 栈和队列第 34页对算术表达式 3*(7-2)求值
#
3*#
15#
步骤 6 w='2'
步骤 7 w=')'
步骤 8?(?遇 ’ )‘
步骤 9 w='#'
步骤 10 退出循环步骤 5 w='-' *（
-
37
5
#*
（-
37
2
返回 15
OPTR栈 OPND栈
中缀简单算术表达式的求值算法优先级：‘ (‘ <?-‘ –?-‘进栈第三章 栈和队列第 35页为了 计算机 处理的方便，常把中缀表达式首先转换成等价的、
严格从左向右计算的形式 —— 后缀表达式,然后实现对后缀表达式的求值运算。
示例（以对比形式写出）
中缀表达式 后缀表达式
3*(7-2) 3 7 2 - *
8-(3+2*6)/5+4 8 3 2 6 * + 5 / - 4 +
后缀表达式的计算步骤
3 7 2 - * 8 3 2 6 * +5 /- 4+
3 5 * 8 3 12 + 5 /- 4+
15 8 15 5 / - 4+
8 3 - 4+
5 4 +
9
表达式的后缀标记法 —— 逆波兰标记法
2、栈的典型应用 —— 表达式求值第三章 栈和队列第 36页后缀表达式的求值运算步骤
1）使用一个栈，从左到右扫描表达式；
2）每遇到一个 操作数 就送入栈中保存；
3）每遇到一个 运算符 就从栈中取出栈顶的两个操作数进行计算，然后将计算结果送入栈中；
4）重复 2),3)直到表达式最后一个字符处理完毕 。
后缀表达式的求值算法
2、栈的典型应用 —— 表达式求值假定表达式合乎文法,且以 @为结束标志。以数组 A存储后缀表达式。数字允许多位数，以句点结尾，如
8,3,2,6,*+5.1- 4.+@ 或 24,6,- @
第三章 栈和队列第 37页
ExpValue( ArrayType A )
{i = 1;
while( A[i] ≠ '@? )
{ switch( A[i] )
{ case?0?.,?9?,//表示 0到 9之间
k =; va = 0; //k为字符串变量
while( A[i] ≠ '.? )
{ k += A[i]; i++ }; //求数字串
va = atoi(k); //串转换成数字值
Push(s,va)； //数字值进栈
case '+',va=pop(s); va+=pop(s); Push(s,va);break;
case '-',va=pop(s); va=pop(s)-va; Push(s,va);break;
case '*',va=pop(s); va*=pop(s); Push(s,va);break;
case '/',va=pop(s); va/=pop(s); Push(s,va);break;
}; //Switch
i++;
}; //While
va = pop(s); printf(,The value is %d.”,va);
}; //expvalue 时间复杂度 O(n),n为后缀表达式的字符个数。
第三章 栈和队列第 38页中缀表达式 后缀表达式
3.*(7.-2.) 3,7,2,- *
8.-(3.+2.*6.)/5.+4,8,3,2,6.*+5./-4.+
1）操作数出现的次序都是相同的；
2）运算符出现的次序不同。
如果把中缀表达式中所有的计算顺序都按运算规则用 嵌套括号 的形式表示出来，例如，将
8.-(3.+2.*6.)/5.+4.
改写成 ((8.-((3.+(2.*6.))/5.))+4.)
则只要将 每对括号中的运算符移到相应括号的后面，再删去所有括号,便能得到与之等价的后缀表达式。
中缀表达式到后缀表达式的转换算法第三章 栈和队列第 39页
((8.-((3.+(2.*6.))/5.))+4.)
((8.-((3.+2.6.*)/5.))+4.)
((8.-(3.2.6.*+/5.))+4.)
((8.-3.2.6.*+5./)+4.)
(8.3.2.6.*+5./-+4.)
8.3.2.6.*+5./-4.+
为了将中缀表达式转换成等价的后缀表达式，需要从左到右扫描中缀表达式，并使用一个栈来存放‘ (‘和暂时不能确定计算次序的运算符。针对‘ (‘作有关处理。
中缀表达式到后缀表达式的转换算法第三章 栈和队列第 40页算法思想，可归结为,
用数组 E存 放 中缀表达式,用数组 A存 放 转换结果 ——后缀表达式；
栈 S,初始时设为空栈；依次读取数组 E中的字符，进行下列处理
，直到表达式结束符 ‘ @‘为止。
1）读到数字直接送到 A；
2） 读到运算符 t时，
a) 将栈中 优先级 高于或等于 t的运算符弹出，送到 A，
直至遇到优先级低的运算符为止；
b) t进栈；
3）读到左括号时，将它压入栈中；
4） 读到右括号时，将靠近栈顶的第一个左括号上面的运算符 全部依次 弹出，送到 A中，再丢弃左右括号。
5）读到‘ @‘时，将栈中运算符全部依次弹出，送到 A中
中缀表达式到后缀表达式的转换算法转换,8.-(3.+2.*6.)/5.+4.”
第三章 栈和队列第 41页假定数组 E中是中缀表达式,数组 A存放后缀表达式结果,S为工作栈,
Trans(E,A,S) //假定 E中的中缀表达式 合乎文法
{ i=j=1; //i指向 E,j指向 A
while( E[i]≠'@' )
{ switch( E[i] )
{ //① 处理操作数
//② 处理 '('
//③ 处理 ')'
//④ 处理 '+','-'
//⑤ 处理 '*','/'
}; //switch
i++;
}
收尾工作
} //trans
中缀表达式到后缀表达式的转换算法第三章 栈和队列第 42页
① 处理操作数
case E[i]=?0?..?9?,//标是从 0到 9的字符
while( E[i]≠'.? )
{ A[j] = E[i]; i++; j++ };
A[j] = '.'; j++;
break;
中缀表达式到后缀表达式的转换算法
② 处理‘ (’
case E[i]='(',Push(S,'('); break; // '('肯定进栈
③ 处理‘ )’：
//把与之成对的‘ (’去掉，故肯定要退栈。先将栈顶元素取出，
//然后退栈，若退栈元素是运算符，则放入 A，若是‘ (’，则
//不管。下次读入字符时自然消去‘ (’。
case E[i]=')',w=POP(S);
while( w≠ '(' )
{ A[j] = w; j++; w = POP(S) }
break;
第三章 栈和队列第 43页
④ 处理‘ +’,‘-’,必须进栈，若栈空，则直接进栈；若栈不空，则首先把栈顶元素读出，只要不是‘ (’，则都要退栈，放到 A中。然后‘ +’或‘ -’进栈。
case E[i]='+','-',
if( !isStackEmpty(S))
{ w = Top( S );
while( w≠?(? )
{ A[j] = w; j++; w = Pop(S);
if( isStackEmpty(S)) return;
else w = Top( S );
};
};
Push(S,E[i]);
break;
中缀表达式到后缀表达式的转换算法第三章 栈和队列第 44页
⑤ 处理‘ *’,‘/’,必须进栈，若栈空，则直接进栈；若栈不空，则首先把栈顶元素读出，若是‘ +’，‘ -’,‘ (’则‘ +’，‘ -’,' ('不需退栈。
case E[i] = '*','/',
if( !isStackEmpty(S))
{ w = Top(S);
while((w≠?+?) && (w≠?-?) && (w≠'(?))
{ A[j] = w; j++; w = POP(S);
if( isStackEmpty(S) return;
else w= Top( S );
}
};
Push(S,E[i])
break;
中缀表达式到后缀表达式的转换算法收尾工作,
while( !isStackEmpty(S))
{ A[j] = POP(S); j++ };
A[j] = '@';
注,关于收尾，例如,3.*5.+2./3.→3.5.*2.3./+@,当 E读到 '@'，栈中还有 '/','+'，应相继进入 A。
第三章 栈和队列第 45页表达式的后缀标记法又称为 逆波兰标记法,这个名字来源于波兰数学家 Jan Lukasiewicz，他在 1951年首先发表了有关论文。
术语“逆”或“后缀”是指 运算符紧跟在操作数后面,而不是象中缀标记法那样出现在它们之间。还有：前波兰“或”前缀“标记法，在这种表示法中，运算符出现在操作数之前。
表达式的波兰标记法已被发展为一个方便的 无括号方法来表示逻辑表达式。现在波兰标记法在计算机科学方面具有广泛的用途。在解释程序和编译程序中，波兰标记法用于一个语句转变为中间表示形式。
2、栈的典型应用第三章 栈和队列第 46页递归是计算机科学中极为重要的概念，对递归的研究是计算机科学领域中的重要课题。
递归是程序设计中最有力的方法之一。许多计算机都支持递归，允许子系统的递归调用。用递归形式编写过程或函数，其形式清晰、直观。
递归过程,一个直接或间接地调用自身的过程 (Pascal)
递归函数,一个使用函数自身给出定义的函数递归算法,用递归过程或递归函数的形式描述的算法
递归的概念
3、栈与递归第三章 栈和队列第 47页
3、栈与递归注 1,递归函数必须有递归 终结分支 ！！！
递归函数的 2个示例例 1 阶乘函数
)1)0(,0(
)1(321)(
F a c tn
nnnF a c t
定义非递归形式
0),1(.
0,1)(
nnF a c tn
nnF a c t
递归形式例 2 斐波那契 (Fibonacci)数列
nn
nF i b
2
51
2
51
5
1)(
非递归形式
2),2()1(
1,1
0,0
)(
nnF i bnF i b
n
n
nF i b
递归形式第三章 栈和队列第 48页递归算法示例用类 C写求阶乘函数
int fact( int n )
{ if( n == 0 ) return 1;
return( n * fact(n-1));
} //fact
3、栈与递归当 n= -1时，会怎样？
第三章 栈和队列第 49页递归算法示例写出 Fibonacci数列递归函数
int fib( int n )
{ switch( n ){
case n<0,ERROR(?n应大于 0?)； break;
case n=0,return(0)； break;
case n=1,return(1)； break;
default:
return(fib(n-1)+fib(n-2));
}; //case
} //fib
3、栈与递归第三章 栈和队列第 50页递归求解问题例 3-3 n阶 Hanoi塔问题 (p55)
圆盘移动规则
1）每次只能移动一个圆盘；
2）圆盘可以插在 X,Y和 Z中的任一塔座上；
3）任何时刻都不能将一个较大的圆盘压在较小的圆盘上。
X Y Z
初 始
X Y Z
结 果
3、栈与递归第三章 栈和队列第 51页递归求解问题例 3-3 n阶 Hanoi塔问题 (p55)
3、栈与递归
X Y Z
1~n
X Y Z
1~n-1
n(1)从 X移动 1~n-1号圆盘至 Y,Z作辅助； (递归 )
X Y Z
1~n-1
n
(2)从 X移动 n号圆盘至 Z；
(一次搬运 )
(3)从 Y移动 1~n-1号圆盘至 Z，
X作辅助。 (递归 )
X Y Z
1~n-1
n
[分析 ] 此问题可归之于三个子问题第三章 栈和队列第 52页求解 n阶 Hanoi塔问题的递归,算法过程
hanoi( int n,char x,char y,char z)
//将塔座 x上编号从 1至 n、直径依小至大的 n个圆盘移到塔座 Z上，
y可用作辅助塔座
1 {
2 if( n==1 )
3 move(x,1,z); //将编号为 1的圆盘从 x移到 z
4 else if( n>1 )
{
5 hanoi(n-1,x,z,y);
//将 x上编号从 1至 n-1的圆盘移到 y上,z为辅助塔座
6 move(x,n,z); //将编号为 n的圆盘从 x移到 z
7 hanoi(n-1,y,x,z)
//将 y上编号从 1至 n-1的圆盘移到 z上,x为辅助塔座
8 }
9 } //hanoi
3、栈与递归第三章 栈和队列第 53页设有一个函数 A要调用函数 B(x)；我们称 A为,调用函数”,B
为,被调函数,。 A调用 B时，使用语句 B(b)来引起 B过程的执行。
一般来说，函数调用可以分解成下列三步实现：
(1)保存调用信息：将 参数、返回地址等 传递给被调函数，保存现场
(2)分配被调函数所需数据区：为被调函数 局部变量 分配内存 ;
(3)控制转移到被调函数的入口。
在被调函数执行结束，返回到调用函数时，也是三步,
(1)保存返回信息：被调函数要传递给调用函数的信息，如计算结果 ;
(2)释放被调函数的数据区；
(3)把控制按返回地址转移回调用函数中。
注：当有多个过程构成嵌套调用时，按照,后进先返回 (LIFO)‖原则
。
3、栈与递归
递归的实现联想到“栈”
第三章 栈和队列第 54页一个递归函数的运行过程 类似于多个函数的嵌套调用,只是调用函数与被调函数是同一函数 。
“层次”概念,一般设调用该递归函数的主程序为 0层过程，从主程序调用递归函数为进入第一层函数；从第 N层递归调用本函数为进入第 N+1 层。
函数之间的信息传递和控制转移须用,栈” 来实现。
具体做法为：
系统将整个程序运行时所需的局部变量安排在一个栈中，每执行一次调用，就为被调过程在栈顶分配一个存储区 （压栈）,用以保存,返回地址、调用参数、局部变量,；每当被调函数返回时，
就释放它的存储区 （弹出） 。
3、栈与递归
递归的实现第三章 栈和队列第 55页递归函数的实现也是通过一个“栈”来完成。
“工作记录”,每一层递归所需记录的信息。
“活动记录”,当前执行层的“工作记录”肯定在栈顶，称之为 ~
―当前环境指针”,指示“活动记录”的栈顶指针。
3、栈与递归
递归的实现示例,在 hanoi塔问题中，每个工作记录包含五个数据项：返回地址（以语句行号表示）和四个实在参数。假设主过程的返回地址为 0。以 n=3来模拟执行 hanoi递归过程。
（示意图见下页）
第三章 栈和队列第 56页递归运行的层次层内运行语句的行号塔与圆盘的状态
0,3,a,b,c
0,3,a,b,c
6,2,a,c,b
0,3,a,b,c
6,2,a,c,b
6,1,a,b,c
1
2
2
3
1,2,4,
5
1,2,4,
5
1,2,3,
9
6,7
递归工作栈状 态
0,3,a,b,c
6,2,a,c,b
3
2
1
a b c
3
2
a b c
3 1
a b c
1
2
说明
a→b
a→c
1
2
地址,n,x,y,z
第三章 栈和队列第 57页递归运行的层次运行语句行号 塔与圆盘 的状态
0,3,a,b,c
0,3,a,b,c
6,2,a,c,b
0,3,a,b,c
6,2,a,c,b
8,1,c,a,b3
2
3
1
1,2,3,
9
8,9
6,7
递归工作栈状 态
0,3,a,b,c
8,2,b,a,c
3 2
1
a b c
32
a b c
31
a b c
1
2
说明
b→a
a→c
3
1
0,3,a,b,c
8,2,b,a,c
6,1,b,c,a
c→b
1
2 1,2,4,5
1,2,3,
9
地址,n,x,y,z
第三章 栈和队列第 58页递归运行的层次运行语句行号塔与圆盘的状态
0,3,a,b,c
0,3,a,b,c
8,2,b,a,c2
3
0
2
6,7
1,2,3,
9
8,9
递归工作栈状 态
0,3,a,b,c
8,2,b,a,c
3
2
1
a b c
说明
a→c
1
0,3,a,b,c
8,2,b,a,c
8,1,a,b,c
b→c
2
1 8,9
3
2
1
a b c
同上同上同上栈空第三章 栈和队列第 59页示例 简化的背包问题设有一个背包可以放入的物品重量为 S，现有 n件物品，
重量分别为 w1,w2,…,w n.问能否从这 n件物品中选择若干件放入背包，使得放入的重量之和正好为 S。 如果存在一种符合上述要求的选择，则称此背包问题有解（或称解为“真”），否则此问题无解（或称解为“假”）。
[分析 ] 用 Knap(S,n)表示上述背包问题的解，它是一个布尔函数，其参数应满足 S>0,n≥1.
当 S=0时,背包问题总有解，即 Knap(0,n)=true，只要不选择任何物品放入背包即可：
当 S<0时,背包问题总无解，即 Knap(s,n)=false，因为无论怎样选择总不能使重量之和为负值；
当 S>0但 n<1时,背包问题也无解，即 Knap(S,n)=false，因为不取任何东西就要使重量为正值总是办不到的；
3、栈与递归第三章 栈和队列第 60页当 S>0且 n≥1时,分两种情况：
1) 所选择的一组物品中不包含 wn,这样 Knap(s,n)的解就是 Knap(s,n-1) 的解；
2) 所选择的一组物品中包含 wn,这时 Knap(s,n)的解就是
Knap(s-wn,n-1) 的解；
背包问题的递归定义
.10,)1,(
)1,(;10,
0,;0,
),(
nsnWSK n a p
nSk n a p
nSfa ls e
Sfa ls e
Str u e
nSK n a p
n
且当或且当当当由上述定义不难编写出背包问题的递归算法。今写成递归函数的形式。
3、栈与递归第三章 栈和队列第 61页
Status Knap( int S,int n )
{ if( S == 0 ) return true;
if((S<0) || (S>0 && n<1)) return false;
if( Knap( S - W[n],n-1) == true )
{ printf(“%d,,W[n]); return true }
return (Knap(S,n-1));
} //Knap
注,算法中假设 Wi(i=1,2,···,n)均为正整数，并已经存放在一维整型数组 W之中。
3、栈与递归第三章 栈和队列第 62页递归函数的 优点,
(1) 结构清晰，易于理解；
(2) 正确性容易证明；
(3) 易调试，易实现。
递归函数的 缺点,
(1) 实现效率较低，无论是时间还是空间都较非递归算法为差；
(2) 有些计算机高级语言不具有递归的功能，不支持递归。
递归与非递归的 取舍,① 若问题存在着明显的 迭代解法,则宜 避免使用递归 。 ② 倘若问题的 本质是递归 的，则宁可牺牲一些效率也应该使用递归，以便算法简洁易读。 ③ 对于 不允许递归的语言,或者是 特别强调算法的效率 时，可以先设计出递归算法,然后再将它转换成非递归算法。由于由系统实现递归时隐含着栈的处理，因此，用非递归算法来描述递归算法时，一般都包含着对栈的显式处理。
3、栈与递归
递归函数转换成非递归函数第三章 栈和队列第 63页递归函数转换成非递归函数的实质是：将原由系统进行管理的递归工作栈改为由程序员负责管理。
转换成非递归的算法的一般结构
//BEGIN
初始化栈；第一次进栈；
do
while（非递归终止条件） {入栈处理 }
if( top>1 )
{出栈处理 }
while(( top == 1 )&&(递归终止条件 ))
结束处理 ;
//END;
注,第一次进栈
top=1; S[top]=（参数表）；
若无初始进栈，则可将 1改成 0。
递归函数转换成非递归函数第三章 栈和队列第 64页示例 求阶乘函数的非递归算法递归算法,
int fact( int n )
{
if( n<=0 ) return 1;
return( n * fact(n-1));
} //fact
递归过程转换成非递归过程第三章 栈和队列第 65页非递归算法
int fact( int n )
{ int x; //存放结果
x = 1; InitStack(st);
do
while( n > 0 )
{
Push(st,n); n--; //入栈处理
}
if( st.top > 0 )
{
x *= Pop(st); //出栈处理
}
while( Empty(st));
return x;
} //fact
递归过程转换成非递归过程
int fact( int n )
{
if( n<=0 ) return 1;
return( n * fact(n-1));
} //fact
第三章 栈和队列第 66页示例 n阶 hanoi塔问题的 非递归算法 (用 While)
struct snode{
int np;
char xp,yp,zp;
};
hanoi2(int n,char x,char y,char z)
{
snode s[arrmax]; int top;
top=1; S[top]=(n,x,y,z); //栈初始化
while( !((top==1) && (S[top].np==1)))
{ while( S[top].np > 1 )
{ S[top+1] = (S[top].np-1,S[top].xp,S[top].zp,S[top].yp);
top++ };
move(S[top].xp,S[top].np,S[top].zp);
if( top>1 )
{ top--; move(S[top].xp,S[top].np,S[top].zp);
S[top].np--; S[top].xp? S[top].yp}
};
move(S[top].xp,1,S[top].zp); top--;
} //hanoi2 算 法 3.8
第三章 栈和队列第 67页示例 n阶 hanoi塔问题的 非递归算法 (用 do-while)
hanoi2(posint n,char x,char y,char z)
{
snode s [arrmax]; int top;
top=1; S[top]=(n,x,y,z); //栈初始化
do
while( S[top].np>1 )
{S[top+1]=(S[top].np-1,S[top].xp,S[top].zp,S[top].yp);
top++ };
move(S[top].xp,S[top].np,S[top].zp);
if( top>1 )
{ top--; move(S[top].xp,S[top].np,S[top].zp);
S[top].np--; S[top].xp? S[top].yp}
while((top==1) && (S[top].np==1))
top--;
} //hanoi2
有什么差别？
第三章 栈和队列第 68页示例 双递归阿克 Ackermann函数
递归过程转换成非递归过程
0,)),1,(,1(
0,)1,1(
0,1
),(
nmnmA c kmA c k
nmA c k
mn
nmA c k
Ackermann函数 递归函数 说明
int ack( int m,int n )
{
if( m==0 ) return n+1;
if( n==0 ) return ack(m-1,1)
return ack(m-1,ack(m,n-1))
} //ack
第三章 栈和队列第 69页
struct snode{
int m,n;
};
snode s[arrmax]; int top;
int Ack( int m,int n )
{ top=1; S[1]=(m,n); //栈初始化
do
while( S[top].m≠0 )
{ while( S[top].n ≠ 0 )
{ top++； S[top]=(S[top-1].m,s[top-1].n-1) };
s[top]=(s[top].m-1,1);
};
if( top>1 )
{top--; S[top]=(s[top].m-1,s[top+1].n+1)}
while((top==1) && (S[top].m==0));
top--; return (s[top+1].n+1)
} //Ack
Ackermann函数 非递归算法第三章 栈和队列第 70页定义 队列是限定仅能在表的一端进行插入，在表的另一端进行删除的线性表。 在队列中可以插入的一端称为 队尾 (rear)，可以删除的一端称为队头或 队首 (front)。
将一个元素插到队列中的操作叫做 入队列或进队,从队列中删除一个元素的操作叫做 出队列或出队 。队列是一种 先进先出 (First In
First Out,FIFO)的线性表，或简称队列是一种 FIFO结构。
队列的基本性质
(1) 均匀性,元素具有相同类型（属于同一个数据对象）；
(2) 有序性,线性有序；
(3) 受限的运算,一端插入，另一端删除。
出队列（出队） 入队列（进队）
队尾队头
a1 a2 a3 ··· ··· an
队列的逻辑结构
4、队 列第三章 栈和队列第 71页
Specification ADT Queue
Elements：所涉及对象的类型明显地取决于应用，可以是各种类型 的，只要 同属于一个数据对象 即可。
Structure,队列亦是一种线性结构，其数据元素之间呈线性关系。设 Q=(a1,a2,··,an)，则对每一个数据元素 ai(i=1,2,··,n-1)，都存在关系 <ai,ai+1>，并且 a1
无前趋,an无后继；队列又是一种受限的线性结构,该结构使先进队的元素先出队 。
Operations,可定义下列七种有关队列的基本操作
队列的抽象数据类型
4、队 列第三章 栈和队列第 72页
InitQueue ( queue &Q ); //初始化操作,生成空的队列
Status Empty( queue Q); //判队列空函数
//若队列为空，则返回函数值 true,否则返回 false
EnQueue( queue &Q; elemtp x ); //入队列操作
//若 队列不满,将一个新的元素 x插入到队列 Q的尾部位置上
elemtp DlQueue( queue &Q ) //出队列函数
/*队列不空,返回队头元素的值并删除该队头元素； 若队列为空，
则返回空元素值 NULL*/
elemtp GetHead( queue Q ); //取队头元素函数
/*队列不空,返回队头元素的值，但队列本身没有改变； 若队列为空，则返回空元素值 NULL*/
elemtp Clear( queue &Q ); //队列置空操作
//不论队列 Q是否为空队列，本操作结果将 Q置为空队列
int CurrentSize ( queue Q); //求队列长度函数
//返回队列中当前数据元素的个数
队列的抽象数据类型第三章 栈和队列第 73页用链表表示的队列称为链接队列，或简称为链对列。
链队列 —— 队列的链式存储结构
^···
q.front q.rear
附加头节点 队头 队尾
^q.frontq.rear空链队列：
队头指针 队尾指针链队列应包含两个指针,队头指针,队尾指针为了操作方便，给链队列 附加一个头节点 。
第三章 栈和队列第 74页
链队列 —— 队列的链式存储结构
^···
q.front q.rear
附加头节点 队头 队尾队头指针 队尾指针
struct queuenode{
elemtp data;
queuenode *next;
};
struct linkedquetp{
queuenode *front,*rear;
};
链队列的表示：
第三章 栈和队列第 75页队列操作指针变化状况,
^
x ^
q.front
元素入队列,enqueue(q,x)
enqueue(q,y)
q.rear
q.front
q.rear
初始化队列,InitQueue(q)
y ^q.frontq.rear x
y ^q.frontq.rear x
链队列 —— 队列的链式存储结构定义 linkedquetp q
元素出队列,dlqueue(q)
设 queuenode *p p
第三章 栈和队列第 76页实现部分的语句编码
init_linkedque(linkedquetp &q )
{
q.front = new( queuenode ); //建链队列结点
q.rear = q.front;
q.front->next = NULL;
} //init_linkedque
en_linkedque(linkedquetp &q,elemtp x )
{
queueptr p;
p = new(queuenode );
p->data = x; p->next = NULL; //建新尾结点
q.rear->next = p; q.rear = p; //插入队尾
} //en_linkedque
链队列 —— 队列的链式存储结构下续第三章 栈和队列第 77页
Status dl_linkedque( linkedquetp &q,elemtp &e )
{
queueptr s; elemtp x;
if( q.front == q.rear ) //队列为空
return false;
s = q.front->next;
q.front->next = s->next; //删除链队列的队头元素
if ( !s->next )
q.rear = q.front; //若删除后队列为空则修改尾指针
x = s->data;
delete(s); //回收无用结点
e = x;
return OK; //返回该元素
} //dl_linkedque
承上
链队列 —— 队列的链式存储结构下续第三章 栈和队列第 78页
elemtp gethead_linkedque( linkedquetp q )
{
queueptr s;
if( q.front !=q.rear ) //队列为空
{
s = q.front->next; return s->data;
}
} //gethead_linkedque
Status empty_linkedque( linkedquetp q )
{
return (q.front == q.rear);
} //empty_linkedque
clear_linkedque( linkedquetp &q)
{
q.rear=q.front; q.front->next =NULL //还应考虑释放空间
} //clear_linkedque
承上
链队列 —— 队列的链式存储结构第三章 栈和队列第 79页队列的顺序存储结构用数组实现队列,定义一个数组和分别指向队头元素和队尾元素的游标。
约定,尾指针指示队尾元素在队列中的 下一个 位置，头指针指示队列中队头元素的 当前 位置。
数据结构描述
struct sequeuetp{
elemtp elem[maxsize];
int front,rear;
}
sequeuetp sq;
循环队列 —— 队列的顺序存储结构第三章 栈和队列第 80页顺序存储结构的队列的入队列、出队列操作示意
J4
sq.rear
sq.front
J6
J5
sq.rear
sq.front
J4
J3
J2
J1
sq.rear
sq.front
5
4
3
2
1
0sq.rearsq.front
(a) (b) (c) (d)
(a) 空队列； (b) J1,J2,J3,J4相继入队列；
(c) J1,J2,J3,J4相继出队列； (d) J4出队 J5,J6入队列 (加满 )。
队空,sq.front==sq.rear
队满,sq.rear==maxsize（可能是假溢出）
入队,sq.elem[sq.rear]=x； //x入队列
sq.rear++； //修改尾指针出队,sq.front++； //修改头指针队列的顺序存储结构第三章 栈和队列第 81页
Q.front
Q.rear
循环队列 —— 队列的顺序存储结构入队,cq.elem[cq.rear]=x；
cq.rear=(cq.rear+1) % maxsize；
出队,cq.front=(cq.front+1) % maxsize；
cq.front=cq.rear cq.front=cq.rear
J5
J6J4 5
0
12
4
3
cq.front
cq.rear
(a) 一般情况
J5
J6J4 5
0
12
4
3 J7
J8
J9
cq.front
cq.rear
(b) 队列满时
5 0
12
4
3
cq.front
cq.rear
(c) 空队列第三章 栈和队列第 82页
(d) 队列满时 (e) 空队列区分队满与队空的解决方法：
（ 1）设一标志位记录队列的状态
（ 2）少用一个元素的空间
5 0
12
4
3
J5
J6J4 5
0
12
4
3 J7
J8
cq.front
cq.rear
cq.front
cq.rear
循环队列 —— 队列的顺序存储结构
(cq.rear+1) % maxsize==cq.front cq.front==cq.rear
第三章 栈和队列第 83页
const int maxsize = maxarrlen； //队列的最大容量
struct cyclicquetp{elemtp elem[maxsize];
int rear,front;
};
init_cycque( cyclicquetp &cq );
Status en_cycque( cyclicquetp &cq,elemtp x);
Status dl_cycque( cyclicquetp &cq,elemtp x);
elemtp en_cycque( cyclicquetp cq,elemtp x );
elemtp gethead_cycque( cyclicquetp cq );
Status full_cycque( cyclicquetp cq );
Status empty_cycque( cyclicquetp cq );
clear_cycque( cyclicquetp &cq );
int size_cycque( cyclicquetp cq);
… …
循环队列抽象数据类型的模块说明第三章 栈和队列第 84页实现部分的语句编码
init_cycque( cyclicquetp &cq )
{
cq.front = 0; cq.rear = 0;
} //init_cycque
Status en_cycque( cyclicquetp &cq,elemtp x )
{
if(((cq.rear+1) % maxsize ) == cq.front )
return false; //队列已满
else
{ cq.elem[cq.rear] = x;
cq.rear = (cq.rear+1) % maxsize;
return true;
}
} //en_cycque
循环队列 —— 队列的顺序存储结构第三章 栈和队列第 85页
Status dl_cycque( cyclicquetp &cq,elemtp &e )
{
if( cq.front==cq.rear ) //队列为空
return false;
dl_cycque = cq.elem[cq.front];
cq.front = (cq.front+1) % maxsize;
} //dl_cycque
elemtp gethead_cycque( cyclicquetp cq )
{
if( cq.front==cq.rear ) //队列为空
return null;
else
return cq.elem[cq.front];
} //gethead_cycque
循环队列 —— 队列的顺序存储结构第三章 栈和队列第 86页
clear_cycque ( cycliquetp &cq )
{
cq.rear = cq.front;
} //clean_cycque
int size_cycque( cyclicqetp cq )
{
return
(cq.rear+maxsize -cq.front) % maxsize;
} //size_cycque
循环队列 —— 队列的顺序存储结构第三章 栈和队列第 87页双端队列又称双向队列。它是限定插入和删除操作在表的两端进行的线性表。这两端分别记为 end1,end2，上限、下限均可增、
减。
插入 a1 a2 a3··· an 插入删除 删除end1 end2
输入受限的双端队列（超栈）
end2end1
双端队列
end1 end2
输出受限的双端队列（超队列）
双向队列输入 输出铁路转轨图第三章 栈和队列第 88页示例 1 模拟客观世界的一些排队过程。如售票窗外、服务台前、食堂窗口等。顾客按先后次序排队。
先排者先服务，然后离队；新来者排队尾，依次等候
。
示例 2 多道作业请求通过打印机通道输出。可按请求输出的先后次序，将这些作业排成一个队列。每当通道输出完毕可以接受新的输出任务时，将队头的作业出队，作输出操作。凡是申请输出的作业都是从队尾进入队列。
示例 3 键盘输入的输入字符队列。
示例 4 没有优先级的作业等待队列。
队列的应用举例第三章 栈和队列第 89页所谓 离散事件模拟 （ Discrete Event Simulation）指的是模拟一个这样的系统，其中系统状态的所有变化可以假定是在某些离散的时间瞬间中发生的。正被模拟的“系统
”通常是一个个别的活动体的集合，这些活动体是基本上独立的，虽然它们彼此交互作用。其例子如：商店里的顾客、港口中的船只、一个团体中的人们等等。 在一个离散事件的模拟中，在某个模拟时间进行着有待完成的事件（
事件驱动），然后把模拟时钟推进到某个动作预定要出现的下个时刻 。
离散事件模拟第三章 栈和队列第 90页示例 银行业务的模拟程序。模拟银行的业务活动，并计算一天中客户在银行逗留的平均时间。假定银行在 4个窗口提供服务。
[分析 ] 考虑以下三个方面：
1,顾客到达银行和离开银行为两个事件。由于模拟是按事件发生的先后次序进行，因此建立一个有序的事件表来存储各个事件（
到达、离开。
2,程序中模拟顾客的到来约定为：当一个顾客在到达后，要为下一个顾客的到来产生一个时间间隔；同时产生本次顾客的事务处理时间。这可由产生两个随机数来确定,(durtime,intertime)：
durtime：本次顾客办理事务所需时间
intertime：下一顾客到来的时间间隔
3,每个顾客来后，总是到 4个窗口中有最短队长的窗口排队；
每个队的队头顾客就是正在办理事务的顾客，离开队列就是顾客离开事件时刻。
离散事件模拟第三章 栈和队列第 91页银行客户的离散事件驱动模拟程序框架（算法 3.9）
Func Bank_Simulation;
{ //统计一天内客户在银行逗留的平均时间
Open_For_Day; //初始化
while( More_Event )
{Event_Drived (Occurtime,Event_Type); //事件驱动
switch( Event_Type ){
case `A`,Customer_Arrived;
//处理客户到达事件
case `D`,Customer_Departure;
//处理客户离开事件
default,Invalid
};
};
Close_For_Day; //计算逗留平均时间
} //Bank_Simulation
离散事件模拟第三章 栈和队列第 92页设立一个事件表，用于存储两类事件，由于到达、离开频繁，
因此采用链表作为存储结构。
事件链表类型 说明,
#define maxsize 2000;
struct Event_node{
int occurtime; //事件发生时刻
int ntype; /*事件类型,0表示到达事件,1至 4分别表示四个窗口的离开事件 */
}；
typedef LinkList Event_List //事件的链表类型，定义为有序链表。
init_Eventlist ( Event_List &ev );
ins_Eventlist ( Event_List &ev; Event_node en );
Event_node del_Eventlist ( Event_List &ev);
Status empty_Eventlist ( Event_List ev);
离散事件模拟第三章 栈和队列第 93页设立四个队列，分别表示四个窗口的排队情况。队列也采用链表结构
struct elemtp{
int arrivaltime; //到达时间
int duration; //办理事务所需时间
};
struct queuenode{
elemtp data;
queuenode *next;
};
typedef queueptr *queuenode;
struct Linkedquetp{
queueptr front,rear;
};
下续
离散事件模拟第三章 栈和队列第 94页
init_linkedque ( linkedquetp &q );
en_linkedque ( linkedquetp &q,elemtp x );
elemtp dl_linkedque (linkedquetp &q);
elemtp gethead_linkedque (linkedquetp q);
Status empty_linkedque ( linkedquetp q );
clean_linkedque (linkedquetp &q);
int size_linkedque ( linkedquetp q );
承上
离散事件模拟第三章 栈和队列第 95页算法 3.10
CONST int closetime= … ; // 银行关门时刻
Event_List ev; //事件链表
Event_Node en;
linkedquetp q[4]; //4个窗口队列
elemtp customer;
int totaltime,customernum; //计时，计数
离散事件模拟下续第三章 栈和队列第 96页
Open_For_Day() //初始化操作
{ totaltime=0;
customernum=0; //客户人数计数器
init_Eventlist(ev); //初始化事件链表为空表，即 ev.first=0
en.occurtime=0; en.ntype=0; //设定第一个客户到达事件
ins_Eventlist(ev,en); //插入事件表
for( i =1; i <= 4; i++ )
init_linkedque (q[i]); {置空队列 }
} //Open_For_Day
执行 Open_For_Day,将产生如下结构 front
rear
front
rear
front
rear
front
rear
∧
∧
∧
∧
q 队列状态事 件 表
0 0 ^
ev.first=1
1
en.ntype
en.occurtime
离散事件模拟承上下续第三章 栈和队列第 97页
Customer_Arrived ( Event_node en)
{ //处理客户到达事件,en.ntype=0
customernum++; //增加一名客户
Random(durtime,intertime);
/*产生随机数：
durtime：此时刻到达的客户办理事务所需时间
intertime：下一客户将到达的时间间隔 */
t = en.occurtime + intertime; //下一客户到达时刻
if( t<closetime ) //若银行尚未关门，则插入事件表
ins_Eventlist (ev,(t,0));
i =Minimum(q); //求最短队列
en_linkedque(q[i],(en.occurtime,durtime)); //加入最短队列
if( size_linkedque(q[i])==1 ) //是排头
ins_Eventlist(ev,(en.occurtime+durtime,i))
//设定一个第 i个队列客户离开事件插入事件表
} //Customer_Arrived
离散事件模拟承上下续第三章 栈和队列第 98页
Customer_Departure ( Event_node en)
{ //处理客户离开事件,en.ntype>0
i=en.ntype; //那个窗口
customer=dl_linkedque(q[i]);
//从第 i个队列中删除排头客户
totaltime+= (en.occurtime -customer.arrivaltime);
//累计客户逗留时间
if( !empty_linkedque(q[i]))
{customer=gethead_linkedque (q[i]);
ins_Eventlist (ev,(en.occurtime+
customer.duration i))
} //设定一个新的第 i个队列客户离开事件插入事件表
} //Customer_Departure
离散事件模拟承上第三章 栈和队列第 99页
void Bank_Simulation()
{
OpenForDay(); //初始化
while( !EmptyEventList( ev )){
DelFirst( GetHead( ev ),p );
en = GetCurElem( p );
if( en.ntype == 0 )
CustomArrived( en );
else
CustomDeparture( en );
} //while
printf( ―Average Time,%f‖,TotalTime/CustomNum );
}
离散事件模拟第三章 栈和队列第 100页例 3 - 5：假设每个客户办理业务的时间不超过 30分钟；两个相邻到达银行的客户的时间间隔不超过 5分钟，模拟程序从第一个客户到达时间为,0‖开始运行。
离散事件模拟
front
rear
front
rear
front
rear
front
rear
∧
∧
∧
∧
q 队列状态事 件 表
0 0 ^
ev.first
1
en.ntype
en.occurtime
下续初始化状态第三章 栈和队列第 101页
离散事件模拟
front
rear
front
rear
front
rear
front
rear
q 队列状态事 件 表
4 0
ev.first
en.ntypeen.occurtime
下续
0时刻：第一个客户到达
∧
∧
∧
0 23∧
(23,4)
23 1 ^
第三章 栈和队列第 102页
离散事件模拟
front
rear
front
rear
front
rear
front
rear
q 队列状态事 件 表
ev.first
en.ntypeen.occurtime
下略
4时刻：第二个客户到达
23 1 ^
∧
∧
0 23∧
(3,1) 5 0
4 3∧
7 2
第三章 栈和队列第 103页第三章 栈和队列 小结内容栈和队列的逻辑结构定义,各自的特点,ADT定义，在两种存储结构上如何实现栈和队列的基本运算,递归及其内部实现，
在递归算法中怎样使用栈，栈和队列在程序中的典型应用（如表达式求值，离散事件模拟）。
要点
掌握栈和队列这两种数据结构的特点，了解它们的使用场合
熟悉栈、队列与线性表的关系；顺序栈、顺序队列与顺序表的关系；链栈、链队列与链表的关系
掌握在顺序栈、链栈（循环队列、链队列）上实现的栈（队列）
的几种基本运算，特别注意栈（队）满和栈（队）空的条件及它们的描述
理解递归算法执行过程中栈的状态变化过程
掌握栈与队列的典型应用
,数据结构,
第三章 栈和队列第三章 栈和队列第 2页要求：
对栈和队列的存储方式及基本操作有较 深刻 的理解。理解栈和队列的概念
，存储表示，进栈、退栈和进队、出队操作的算法，初步了解栈的基本应用如表达式的求值,递归 的设计实现等。
重点：
栈和队列的基本操作，栈在实现 递归 中的应用。
第三章 栈和队列第三章 栈和队列第 3页主要内容
1、栈
抽象数据类型栈的定义
栈的表示与实现
2、栈的典型应用 —— 表达式求值
表达式的传统标记法 ——中缀标记法
简单算术表达式求值算法 ——算符优先算法
3、栈与递归过程
递归求解问题
递归过程的实现
递归过程转换成非递归过程第三章 栈和队列第 4页
4、队列
队列的逻辑结构
队列的抽象数据类型
链队列 —— 队列的链式存储结构
循环队列 —— 队列的顺序存储结构
双端队列
队列的应用举例
离散事件模拟主要内容第三章 栈和队列第 5页第三章 栈和队列两种重要的 受限 线性结构,栈 (Stack)和队列 (Queue)。
从 数据结构 角度看，栈和队列也是线性表，其特殊性在于栈和队列的 基本操作是线性表操作的子集 。 它们是 操作受限 的线性表，即可称为限定性的数据结构 。但从 数据类型 角度看，它们又是和线性表大不相同的两类重要 的抽象数据类型。
第三章 栈和队列第 6页第三章 栈和队列三者的操作规则比较：
线性表,可以在表的 任何位置 上插入、删除元素。
栈,对栈 仅 限定 在表的 一端 （表尾）进行插入或删除操作。
队列,限定在表的 一端 进行 插入,而在 另一端 删除 元素。
因此，从 ADT的角度看，栈、队列和线性表是不相同的。
第三章 栈和队列第 7页
栈的定义定义,栈（ Stack） 是限定 仅 在表的 一端 进行插入或删除操作的 线性表 。
在栈中能进行插入和删除的一端称为 栈顶 （ top），相应地另一固定端称为 栈底 （ bottom）。将一个元素放入栈中的操作叫做 进栈或压栈,从栈顶取出一个元素的操作叫做 出栈或弹出 。不含元素的空表称为空栈。
栈的存取操作符合 后进先出 （ Last In First Out,LIFO） 或先进后出 （ First In Last Out,FILO） 故 栈又称为后进先出线性表,简称
LIFO结构 。
1、栈
a n
,
,
,
a 2
a 1
栈底栈顶出栈 进栈第三章 栈和队列第 8页栈的基本性质
1) 集合性,该结构由若干个有限的 同类型元素 集合而成；
2) 线性性,除线底外，栈中任一元素均有唯一的前驱，除线顶外，
栈中任一元素均有唯一的后继；
3) 受限制的运算,仅 允许在栈顶压入、弹出；
4) 数学性质,当 n个编号元素依某种顺序压入，且可任意弹出时，
所能获得的 编号元素排列 的数目为。
)(
!!
)!2(
1
1
1
1
2
nn
n
n
C
n
C n nn
其中 n为输入序列长度即编号元素个数,cn为可能的排列数目。
由公式（ *）产生的数列称为 卡塔南数列 。
1、栈第三章 栈和队列第 9页示例 用铁路调度站表示栈出栈 进栈设有 A,B,C三列车厢，则出栈时可能的编号元素排列为 ABC
,ACB,BAC,BCA,CBA共五种。 (无 CAB)
.5!3 45641!3!3 )!32(13 13C
.14!4 567851!4!4 )!42(14 14C
若 A,B,C,D四列车厢，则应有 14种排列：
第三章 栈和队列第 10页
栈的抽象数据类型定义栈是一种强限制的数据类型。在栈上仅能在 特定的一个位置 上定义 有限几种操作 。
Specification ADT Stack
Elements,所涉及对象的数据类型明显地取决于应用，故数据元素可以是 各种类型 的，只要同 属一个数据对象 即可。
Structure,数据元素之间 呈线性关系 。假设栈中有 n个数据元素
(a1,a2,···,an)，则对每一个元素 ai(i=1,2,··,n-1)，都存在关系
<ai,ai+1>，并且 a1无前驱,an无后继。但是，栈是一种受限的线性结构，该结构使后进栈的元素先出栈。
Operation,栈通常包含下面的基本操作，这些操作中除了 InitStack之外，都要求栈 S已存在。
1、栈第三章 栈和队列第 11页
ADT Stack{
数据对象,D={ai|ai∈ ElemSet,i=1,2,…,n,n>=1}
数据关系,R={<ai,ai+1>|ai,ai+1 ∈ D,i=1,2,…,n}
基本操作：
InitStack( &S )； 初始化操作生成一个空栈 S
DestroyStack( &S ); 释放栈
ClearStack( &S ) ； 清空栈
Push( &S,x )； 入栈操作
Pop( &S,&e )； 出栈操作
GetTop( S,&e ) ； 取栈顶元素函数
EmptyStack( &S )； 置栈空操作
int StackLength( S ); 求当前栈中元素个数
}
栈的抽象数据类型定义第三章 栈和队列第 12页
栈的简单应用示例例 3-1 输入字符串。用‘ # ’表示退格符，即它使前一个字符无效；用‘ @ ’表示退行符，以表示此前整行字符均无效。编写行输入处理过程，内设一个栈来逐行处理从终端输入的字符串。每次从终端接收一个字符后先作如下判别：如果它既不是退格符也不是退行符，则将该字符插入栈顶；如果是一个退格符，则从栈顶删去一个字符；如果它是一个退行符，就把字符域清为空栈。
比如，若键入
BGE##EGIM#N
RAD(A@ READ(A);
则实际有效的是下面两行
BEGIN
READ(A);
第三章 栈和队列第 13页
//设 s为栈。本算法从终端接收一个正文文件并逐行传送至调用过程的数据区
Line_Edit(){
InitStack( S );
ch = getchar()； //从终端接收一个字符
while( ch != EOF )
{ while( ch != EOF && ch !=?\n? )
{ switch(ch){
case?#?,Pop(s,c); break; //若栈非空则退栈
case?@?,ClearStack(s); break; //将栈重新设置为空域
default,Push(s,ch); break; //有效字符入栈
}；
ch = getchar()
} //继续接收下一字符
//将自栈底至栈顶的栈内字符作成一行,并传送至调用过程的数据区,
ClearStack(s);
if( ch != EOF ) ch = getchar()
//继续接收下一行，先接收下一行第一个字符
}
} 算 法 3.1
第三章 栈和队列第 14页顺序栈 —— 栈的顺序存储结构用一维数组 S(1:arrmax)表示栈。
3
2
1
3 ` C`
2 ` B`
1 ` A `
S(1:arrmax) S(1:arrmax)
arrmaxarrmax
Top=0
Top=
非空栈空 栈栈顶栈底
栈的表示和实现第三章 栈和队列第 15页
const int MAX_STACK = 1000;
struct SqStkTp{
ElemType Element[MAX_STACK];
int Top;
};
InitStack( SqStkTp &S);
//设定一个空的栈 S
Status isStackEmpty( SqStkTp S );
//若 S为空栈，则返回 true，否则返回 false
Status Push( SqStkTp &s,ElemTp x );
//若栈 S不满，则在栈顶插入 x，并返回函数值 true，否则栈的状态不变且返回函数值 false
栈的 ADT表示
栈的表示和实现第三章 栈和队列第 16页
ElemTp Pop( SqStkTp &s );
//若栈不空，则删去栈顶元素并返回元素值，否则返回空元素
NULL
ElemTp GetTop(SqStkTp s );
//若栈不空，则返回栈顶元素，但 s.top
//保持不变，否则返回空元素 NULL
ClearStack(SqStkTp &s );
//若 S为空栈，即 s.top=0
int CurrentSize(SqStkTp s );
//返回当前栈中元素个数，即 s.top
栈的 ADT表示第三章 栈和队列第 17页部分实现
InitStack( SqStkTp &s)
{ s.top = 0
}//init_stack
Status isStackEmpty(SqStkTp s)
{
return ( s.top == 0 )? True,False;
} //empty_stack
Status Push( SqStkTp &s,ElemTp x )
{ if( s.top == MAX_STACK )
return false;
s.top++;
s.elem[s.top] = x;
return True;
} //push_stack
栈的 ADT实现第三章 栈和队列第 18页
ElemTp Pop( SqStkTp &s )
{
if( s.top == 0 ) return;
s.top--;
return s.elem[s.top+1]
} //pop_stack
ElemTp GetTop( SqStkTp s )
{
if( s.top == 0 ) return;
return s.elem[s.top]
} //gettop_stack
ClearStack( SqStkTp &s )
{
s.top = 0
} //clear_stack
栈的 ADT实现第三章 栈和队列第 19页
int CurrentSize (SqStkTp s )
{
return s.top;
} //currend_size_stack
注 1,函数 isStackEmpty的体亦可写为
return ( s.top == 0 );
注 2,亦可在接口节定义判栈满函数
Status isStackFull (SqStkTp s)
{
reutrn ( s.top == MAX_STACK )
} //full_stack
栈的 ADT实现第三章 栈和队列第 20页栈空,ls == NULL;
栈满,当内存分配无法实现时（堆区满） ;
进栈,在表头插入 ;
出栈,从表头删除 ;
即进栈、出栈操作均限制在单链表的表头端进行。
数据结构的描述
elemtype … … //任何一种数据类型
typedef struct tlkstktp{
ElemType elem;
tlkstktp *Next
} *lkstktp;
^…Ls
栈顶 栈底链式栈 —— 栈的链式存储结构设不带头结点
栈的表示和实现第三章 栈和队列第 21页一个链栈由其栈顶指针 ls唯一确定。
多个链栈可共享内存中的堆 (heap)区域。
链栈为满的条件：堆区满。 new(p)过程无法实现内存分配。
^
ls
data next
栈顶栈底
多栈共享存储区的链接分配 —— 链栈第三章 栈和队列第 22页
PushStack(lkstktp &ls; elemtp x)
{ //算法中 p为 结点 类型指针变量
p = new(ElemType); p->elem = x;
p->next = ls;
ls = p
} //push_stack
elemtp PopStack(lkstktp &ls)
{ //算法中 p为 结点 类型指针变量
if( ls == NULL )
return NULL // pop为 elemtp类型变量
p = ls; ls = p->next;
pop = p->elem;
free(p);
return pop;
} //pop_stack
栈的表示和实现第三章 栈和队列第 23页目的,提高存储空间的使用效率，并减少发生栈上溢的可能性。
示例 两个栈共享一维数组空间栈可利用的最大空间,有可能大于整个数组的一半。
上溢情况,两个栈顶相遇。
双栈的类 C描述
#define m = maxsize; // 两个栈的容量之和
Elemtp = 任何一种数据类型
struct dustktp{
elemtp elem[m];
int top[2];
};
空闲区栈 1底 栈 1顶 栈 2底栈 2顶
两个栈共享一个存储区第三章 栈和队列第 24页
init_stack( dustktp &s,int sno)
{
if( sno == 1 ) s.top[0] = 0;
else s.top[1] = m + 1
} //init_stack
push_stack( dustktp &s,elemtp x,int sno )
{ if( s.top[0]+1 == s.top[1] )
return stack_over_flow;
switch( sno ){
case 1,s.top[0]++; break;
case 2,s.top[1]--; break;
}
s.elem[s.top[sno-1]] = x
} //push_stack
两个栈共享一个存储区第三章 栈和队列第 25页
Status pop_stack( dustktp &s,elemyp &x,int sno )
{ if( empty( s,sno ))
return stack_under_flow;
x = s.elem[s.top[sno-1]];
switch( sno ){
case 1:s.top[0]--; break;
case 2:s.top[1]++; break;
}
} //pop_stack
Status gettop_stack(dustktp s,elemyp &x,int sno)
{ if( empty(s,sno))
return stack_empty;
s.elem[s.top[sno-1]]
} // top_stack
两个栈共享一个存储区第三章 栈和队列第 26页
Status empty( dustktp s,int sno)
{ switch( sno ){
case 1,return(s.top[0] = 0); break;
case 2,return(s.top[1] = m+1); break;
}
} //empty
Status full(dustktp s)
{ return (s.top[0]+1 >= s.top[1]);
}
注,过程 push_stack中
if( s.top[0]+1 = s.top[1] )…;
亦可改写成
if( full(s)) ···;
两个栈共享一个存储区第三章 栈和队列第 27页表达式的成分操作数 (Operand),常数或常数标识符、变量标识符、函数等运算符 (Operator),算术运算符、关系运算符、逻辑运算符等界限符 (Delimiter),左括号、右括号、表达式结束符等表达式的分类算术表达式,如 b*b - 4*a*c
关系表达式,如 b*b - 4*a*c >=0
布尔表达式,如 (a<>0) AND (b*b - 4*a*c>=0)
传统标记法 —— 中缀标记法特点,运算符出现在操作数之间
表达式的传统标记法 —— 中缀标记法
2、栈的典型应用示例 —— 表达式求值第三章 栈和队列第 28页示例 计算 8-(3+2× 6)/5+4
8-(3+2× 6)/5+4
= 8-(3+12)/5+4
=8-15/5+4
=8-3+4
=5+4
=9
表达式的传统标记法 —— 中缀标记法
2、栈的典型应用示例 —— 表达式求值第三章 栈和队列第 29页简单算术表达式求值算法 —— 算符优先算法讨论简单算术表达式的求值问题。
op算符界限符运算符
#),(,:
/,,,:
算符优先法,根据算术四则运算的规则亦即运算优先关系的规定，实现对表达式的编译或解释执行。
使用 栈 实现简单算术表达式的求值运算。
依据算术四则运算的规则，在运算的每一步中。任何两个相继出现的算符 θ1和 θ2之间的优先关系，可能是
θ1<θ2 θ1的优先数低于 θ2
θ1=θ2 θ1的优先数等于 θ2
θ1>θ2 θ1的优先数高于 θ2
第三章 栈和队列第 30页算符间的优先关系表说明：
1）‘ + ’,‘ - ’,' * '和 ' / '为 θ1时的优先性均低于 '(',但高于 ' ) ' ；
2）当 θ1=θ2 时，令 θ1>θ2 ;
3） '(' = ') '表示当左、右括号相遇时，括号内的运算已经完成；
4） ' # '是表达式的结束符。设表达式的最左边也虚设一个 #符，以构成整个表达式的一对“括号”，
5） ‘ (’与‘ # ’,') '与 '('以及 ' # '与 ') '之间无优先关系，若出现此类情况，应是语法错误。下面的讨论中，假定不会出现语法错误；
6） ' # ' = ' # '表示整个表达式求值完毕。
简单算术表达式求值算法 —— 算符优先算法
θ
2
θ
1
+ - * / ( ) #
+ > > < < < > >
- > > < < < > >
* > > > > < > >
/ > > > > < > >
( < < < < < =
) > > > > > >
# < < < < < =
第三章 栈和队列第 31页
operandtype exp_reduced() //返回结果值
/*算术表达式求值的算符优先算法。假定从终端输入的表达式无语法错误，以‘ #’作结束符。设 OPTR和 OPND分别为运算符栈和操作数栈,OP为运算符的集合 */
{
InitStack(OPTR)；
Push(OPTR,'#?)；
InitStack(OPND)；
//栈初始化，并在运算符栈的栈底压入表达式左端的虚设字符 #
w = getchar()； {从终端接收一个字符 }
中缀简单算术表达式的求值算法接下页第三章 栈和队列第 32页
while(!((w==?#?) && (GetTop(OPTR) == '#')))
{ if( !IN(w,op )){Push(OPND,w); w=getchar()}
else
switch(precede(GetTop(OPTR),w)){ //比较优先级
case?<?,Push(OPTR,w);w=getchar(); break;
//栈顶元素优先权低，运算符入栈
case?=?,x =pop(OPTR);w=getchar(); break;
//左括号遇右括号,脱括号并接收下一字符
case?>?,theta = Pop(OPTR);
b=Pop(OPND);a =pop(OPND);
Push(OPND,operate(a,theta,b))
/*运算符及两个操作数分别退栈，
并将运算结果入操作数栈 */
}} //CASE WHILE
return(GetTop(OPND)) {返回最终结果值 }
} //exp_reduced
承上页第三章 栈和队列第 33页例 3-2 利用算法 exp_reduced对算术表达式 3*(7-2)求值
，其操作过程如下
#
OPTR栈 OPND栈
# 3
#* 3
3*#
(
3*#
(
7
3*(7-2)# 初始化步骤 1 w='3'
步骤 2 w='*'
步骤 3 w=' ('
步骤 4 w='7'
转下一幻灯片
中缀简单算术表达式的求值算法优先级：‘ #‘ <?*‘ –?*‘进栈优先级：‘ *’ <?)‘ –?(‘进栈第三章 栈和队列第 34页对算术表达式 3*(7-2)求值
#
3*#
15#
步骤 6 w='2'
步骤 7 w=')'
步骤 8?(?遇 ’ )‘
步骤 9 w='#'
步骤 10 退出循环步骤 5 w='-' *（
-
37
5
#*
（-
37
2
返回 15
OPTR栈 OPND栈
中缀简单算术表达式的求值算法优先级：‘ (‘ <?-‘ –?-‘进栈第三章 栈和队列第 35页为了 计算机 处理的方便，常把中缀表达式首先转换成等价的、
严格从左向右计算的形式 —— 后缀表达式,然后实现对后缀表达式的求值运算。
示例（以对比形式写出）
中缀表达式 后缀表达式
3*(7-2) 3 7 2 - *
8-(3+2*6)/5+4 8 3 2 6 * + 5 / - 4 +
后缀表达式的计算步骤
3 7 2 - * 8 3 2 6 * +5 /- 4+
3 5 * 8 3 12 + 5 /- 4+
15 8 15 5 / - 4+
8 3 - 4+
5 4 +
9
表达式的后缀标记法 —— 逆波兰标记法
2、栈的典型应用 —— 表达式求值第三章 栈和队列第 36页后缀表达式的求值运算步骤
1）使用一个栈，从左到右扫描表达式；
2）每遇到一个 操作数 就送入栈中保存；
3）每遇到一个 运算符 就从栈中取出栈顶的两个操作数进行计算，然后将计算结果送入栈中；
4）重复 2),3)直到表达式最后一个字符处理完毕 。
后缀表达式的求值算法
2、栈的典型应用 —— 表达式求值假定表达式合乎文法,且以 @为结束标志。以数组 A存储后缀表达式。数字允许多位数，以句点结尾，如
8,3,2,6,*+5.1- 4.+@ 或 24,6,- @
第三章 栈和队列第 37页
ExpValue( ArrayType A )
{i = 1;
while( A[i] ≠ '@? )
{ switch( A[i] )
{ case?0?.,?9?,//表示 0到 9之间
k =; va = 0; //k为字符串变量
while( A[i] ≠ '.? )
{ k += A[i]; i++ }; //求数字串
va = atoi(k); //串转换成数字值
Push(s,va)； //数字值进栈
case '+',va=pop(s); va+=pop(s); Push(s,va);break;
case '-',va=pop(s); va=pop(s)-va; Push(s,va);break;
case '*',va=pop(s); va*=pop(s); Push(s,va);break;
case '/',va=pop(s); va/=pop(s); Push(s,va);break;
}; //Switch
i++;
}; //While
va = pop(s); printf(,The value is %d.”,va);
}; //expvalue 时间复杂度 O(n),n为后缀表达式的字符个数。
第三章 栈和队列第 38页中缀表达式 后缀表达式
3.*(7.-2.) 3,7,2,- *
8.-(3.+2.*6.)/5.+4,8,3,2,6.*+5./-4.+
1）操作数出现的次序都是相同的；
2）运算符出现的次序不同。
如果把中缀表达式中所有的计算顺序都按运算规则用 嵌套括号 的形式表示出来，例如，将
8.-(3.+2.*6.)/5.+4.
改写成 ((8.-((3.+(2.*6.))/5.))+4.)
则只要将 每对括号中的运算符移到相应括号的后面，再删去所有括号,便能得到与之等价的后缀表达式。
中缀表达式到后缀表达式的转换算法第三章 栈和队列第 39页
((8.-((3.+(2.*6.))/5.))+4.)
((8.-((3.+2.6.*)/5.))+4.)
((8.-(3.2.6.*+/5.))+4.)
((8.-3.2.6.*+5./)+4.)
(8.3.2.6.*+5./-+4.)
8.3.2.6.*+5./-4.+
为了将中缀表达式转换成等价的后缀表达式，需要从左到右扫描中缀表达式，并使用一个栈来存放‘ (‘和暂时不能确定计算次序的运算符。针对‘ (‘作有关处理。
中缀表达式到后缀表达式的转换算法第三章 栈和队列第 40页算法思想，可归结为,
用数组 E存 放 中缀表达式,用数组 A存 放 转换结果 ——后缀表达式；
栈 S,初始时设为空栈；依次读取数组 E中的字符，进行下列处理
，直到表达式结束符 ‘ @‘为止。
1）读到数字直接送到 A；
2） 读到运算符 t时，
a) 将栈中 优先级 高于或等于 t的运算符弹出，送到 A，
直至遇到优先级低的运算符为止；
b) t进栈；
3）读到左括号时，将它压入栈中；
4） 读到右括号时，将靠近栈顶的第一个左括号上面的运算符 全部依次 弹出，送到 A中，再丢弃左右括号。
5）读到‘ @‘时，将栈中运算符全部依次弹出，送到 A中
中缀表达式到后缀表达式的转换算法转换,8.-(3.+2.*6.)/5.+4.”
第三章 栈和队列第 41页假定数组 E中是中缀表达式,数组 A存放后缀表达式结果,S为工作栈,
Trans(E,A,S) //假定 E中的中缀表达式 合乎文法
{ i=j=1; //i指向 E,j指向 A
while( E[i]≠'@' )
{ switch( E[i] )
{ //① 处理操作数
//② 处理 '('
//③ 处理 ')'
//④ 处理 '+','-'
//⑤ 处理 '*','/'
}; //switch
i++;
}
收尾工作
} //trans
中缀表达式到后缀表达式的转换算法第三章 栈和队列第 42页
① 处理操作数
case E[i]=?0?..?9?,//标是从 0到 9的字符
while( E[i]≠'.? )
{ A[j] = E[i]; i++; j++ };
A[j] = '.'; j++;
break;
中缀表达式到后缀表达式的转换算法
② 处理‘ (’
case E[i]='(',Push(S,'('); break; // '('肯定进栈
③ 处理‘ )’：
//把与之成对的‘ (’去掉，故肯定要退栈。先将栈顶元素取出，
//然后退栈，若退栈元素是运算符，则放入 A，若是‘ (’，则
//不管。下次读入字符时自然消去‘ (’。
case E[i]=')',w=POP(S);
while( w≠ '(' )
{ A[j] = w; j++; w = POP(S) }
break;
第三章 栈和队列第 43页
④ 处理‘ +’,‘-’,必须进栈，若栈空，则直接进栈；若栈不空，则首先把栈顶元素读出，只要不是‘ (’，则都要退栈，放到 A中。然后‘ +’或‘ -’进栈。
case E[i]='+','-',
if( !isStackEmpty(S))
{ w = Top( S );
while( w≠?(? )
{ A[j] = w; j++; w = Pop(S);
if( isStackEmpty(S)) return;
else w = Top( S );
};
};
Push(S,E[i]);
break;
中缀表达式到后缀表达式的转换算法第三章 栈和队列第 44页
⑤ 处理‘ *’,‘/’,必须进栈，若栈空，则直接进栈；若栈不空，则首先把栈顶元素读出，若是‘ +’，‘ -’,‘ (’则‘ +’，‘ -’,' ('不需退栈。
case E[i] = '*','/',
if( !isStackEmpty(S))
{ w = Top(S);
while((w≠?+?) && (w≠?-?) && (w≠'(?))
{ A[j] = w; j++; w = POP(S);
if( isStackEmpty(S) return;
else w= Top( S );
}
};
Push(S,E[i])
break;
中缀表达式到后缀表达式的转换算法收尾工作,
while( !isStackEmpty(S))
{ A[j] = POP(S); j++ };
A[j] = '@';
注,关于收尾，例如,3.*5.+2./3.→3.5.*2.3./+@,当 E读到 '@'，栈中还有 '/','+'，应相继进入 A。
第三章 栈和队列第 45页表达式的后缀标记法又称为 逆波兰标记法,这个名字来源于波兰数学家 Jan Lukasiewicz，他在 1951年首先发表了有关论文。
术语“逆”或“后缀”是指 运算符紧跟在操作数后面,而不是象中缀标记法那样出现在它们之间。还有：前波兰“或”前缀“标记法，在这种表示法中，运算符出现在操作数之前。
表达式的波兰标记法已被发展为一个方便的 无括号方法来表示逻辑表达式。现在波兰标记法在计算机科学方面具有广泛的用途。在解释程序和编译程序中，波兰标记法用于一个语句转变为中间表示形式。
2、栈的典型应用第三章 栈和队列第 46页递归是计算机科学中极为重要的概念，对递归的研究是计算机科学领域中的重要课题。
递归是程序设计中最有力的方法之一。许多计算机都支持递归，允许子系统的递归调用。用递归形式编写过程或函数，其形式清晰、直观。
递归过程,一个直接或间接地调用自身的过程 (Pascal)
递归函数,一个使用函数自身给出定义的函数递归算法,用递归过程或递归函数的形式描述的算法
递归的概念
3、栈与递归第三章 栈和队列第 47页
3、栈与递归注 1,递归函数必须有递归 终结分支 ！！！
递归函数的 2个示例例 1 阶乘函数
)1)0(,0(
)1(321)(
F a c tn
nnnF a c t
定义非递归形式
0),1(.
0,1)(
nnF a c tn
nnF a c t
递归形式例 2 斐波那契 (Fibonacci)数列
nn
nF i b
2
51
2
51
5
1)(
非递归形式
2),2()1(
1,1
0,0
)(
nnF i bnF i b
n
n
nF i b
递归形式第三章 栈和队列第 48页递归算法示例用类 C写求阶乘函数
int fact( int n )
{ if( n == 0 ) return 1;
return( n * fact(n-1));
} //fact
3、栈与递归当 n= -1时，会怎样？
第三章 栈和队列第 49页递归算法示例写出 Fibonacci数列递归函数
int fib( int n )
{ switch( n ){
case n<0,ERROR(?n应大于 0?)； break;
case n=0,return(0)； break;
case n=1,return(1)； break;
default:
return(fib(n-1)+fib(n-2));
}; //case
} //fib
3、栈与递归第三章 栈和队列第 50页递归求解问题例 3-3 n阶 Hanoi塔问题 (p55)
圆盘移动规则
1）每次只能移动一个圆盘；
2）圆盘可以插在 X,Y和 Z中的任一塔座上；
3）任何时刻都不能将一个较大的圆盘压在较小的圆盘上。
X Y Z
初 始
X Y Z
结 果
3、栈与递归第三章 栈和队列第 51页递归求解问题例 3-3 n阶 Hanoi塔问题 (p55)
3、栈与递归
X Y Z
1~n
X Y Z
1~n-1
n(1)从 X移动 1~n-1号圆盘至 Y,Z作辅助； (递归 )
X Y Z
1~n-1
n
(2)从 X移动 n号圆盘至 Z；
(一次搬运 )
(3)从 Y移动 1~n-1号圆盘至 Z，
X作辅助。 (递归 )
X Y Z
1~n-1
n
[分析 ] 此问题可归之于三个子问题第三章 栈和队列第 52页求解 n阶 Hanoi塔问题的递归,算法过程
hanoi( int n,char x,char y,char z)
//将塔座 x上编号从 1至 n、直径依小至大的 n个圆盘移到塔座 Z上，
y可用作辅助塔座
1 {
2 if( n==1 )
3 move(x,1,z); //将编号为 1的圆盘从 x移到 z
4 else if( n>1 )
{
5 hanoi(n-1,x,z,y);
//将 x上编号从 1至 n-1的圆盘移到 y上,z为辅助塔座
6 move(x,n,z); //将编号为 n的圆盘从 x移到 z
7 hanoi(n-1,y,x,z)
//将 y上编号从 1至 n-1的圆盘移到 z上,x为辅助塔座
8 }
9 } //hanoi
3、栈与递归第三章 栈和队列第 53页设有一个函数 A要调用函数 B(x)；我们称 A为,调用函数”,B
为,被调函数,。 A调用 B时，使用语句 B(b)来引起 B过程的执行。
一般来说，函数调用可以分解成下列三步实现：
(1)保存调用信息：将 参数、返回地址等 传递给被调函数，保存现场
(2)分配被调函数所需数据区：为被调函数 局部变量 分配内存 ;
(3)控制转移到被调函数的入口。
在被调函数执行结束，返回到调用函数时，也是三步,
(1)保存返回信息：被调函数要传递给调用函数的信息，如计算结果 ;
(2)释放被调函数的数据区；
(3)把控制按返回地址转移回调用函数中。
注：当有多个过程构成嵌套调用时，按照,后进先返回 (LIFO)‖原则
。
3、栈与递归
递归的实现联想到“栈”
第三章 栈和队列第 54页一个递归函数的运行过程 类似于多个函数的嵌套调用,只是调用函数与被调函数是同一函数 。
“层次”概念,一般设调用该递归函数的主程序为 0层过程，从主程序调用递归函数为进入第一层函数；从第 N层递归调用本函数为进入第 N+1 层。
函数之间的信息传递和控制转移须用,栈” 来实现。
具体做法为：
系统将整个程序运行时所需的局部变量安排在一个栈中，每执行一次调用，就为被调过程在栈顶分配一个存储区 （压栈）,用以保存,返回地址、调用参数、局部变量,；每当被调函数返回时，
就释放它的存储区 （弹出） 。
3、栈与递归
递归的实现第三章 栈和队列第 55页递归函数的实现也是通过一个“栈”来完成。
“工作记录”,每一层递归所需记录的信息。
“活动记录”,当前执行层的“工作记录”肯定在栈顶，称之为 ~
―当前环境指针”,指示“活动记录”的栈顶指针。
3、栈与递归
递归的实现示例,在 hanoi塔问题中，每个工作记录包含五个数据项：返回地址（以语句行号表示）和四个实在参数。假设主过程的返回地址为 0。以 n=3来模拟执行 hanoi递归过程。
（示意图见下页）
第三章 栈和队列第 56页递归运行的层次层内运行语句的行号塔与圆盘的状态
0,3,a,b,c
0,3,a,b,c
6,2,a,c,b
0,3,a,b,c
6,2,a,c,b
6,1,a,b,c
1
2
2
3
1,2,4,
5
1,2,4,
5
1,2,3,
9
6,7
递归工作栈状 态
0,3,a,b,c
6,2,a,c,b
3
2
1
a b c
3
2
a b c
3 1
a b c
1
2
说明
a→b
a→c
1
2
地址,n,x,y,z
第三章 栈和队列第 57页递归运行的层次运行语句行号 塔与圆盘 的状态
0,3,a,b,c
0,3,a,b,c
6,2,a,c,b
0,3,a,b,c
6,2,a,c,b
8,1,c,a,b3
2
3
1
1,2,3,
9
8,9
6,7
递归工作栈状 态
0,3,a,b,c
8,2,b,a,c
3 2
1
a b c
32
a b c
31
a b c
1
2
说明
b→a
a→c
3
1
0,3,a,b,c
8,2,b,a,c
6,1,b,c,a
c→b
1
2 1,2,4,5
1,2,3,
9
地址,n,x,y,z
第三章 栈和队列第 58页递归运行的层次运行语句行号塔与圆盘的状态
0,3,a,b,c
0,3,a,b,c
8,2,b,a,c2
3
0
2
6,7
1,2,3,
9
8,9
递归工作栈状 态
0,3,a,b,c
8,2,b,a,c
3
2
1
a b c
说明
a→c
1
0,3,a,b,c
8,2,b,a,c
8,1,a,b,c
b→c
2
1 8,9
3
2
1
a b c
同上同上同上栈空第三章 栈和队列第 59页示例 简化的背包问题设有一个背包可以放入的物品重量为 S，现有 n件物品，
重量分别为 w1,w2,…,w n.问能否从这 n件物品中选择若干件放入背包，使得放入的重量之和正好为 S。 如果存在一种符合上述要求的选择，则称此背包问题有解（或称解为“真”），否则此问题无解（或称解为“假”）。
[分析 ] 用 Knap(S,n)表示上述背包问题的解，它是一个布尔函数，其参数应满足 S>0,n≥1.
当 S=0时,背包问题总有解，即 Knap(0,n)=true，只要不选择任何物品放入背包即可：
当 S<0时,背包问题总无解，即 Knap(s,n)=false，因为无论怎样选择总不能使重量之和为负值；
当 S>0但 n<1时,背包问题也无解，即 Knap(S,n)=false，因为不取任何东西就要使重量为正值总是办不到的；
3、栈与递归第三章 栈和队列第 60页当 S>0且 n≥1时,分两种情况：
1) 所选择的一组物品中不包含 wn,这样 Knap(s,n)的解就是 Knap(s,n-1) 的解；
2) 所选择的一组物品中包含 wn,这时 Knap(s,n)的解就是
Knap(s-wn,n-1) 的解；
背包问题的递归定义
.10,)1,(
)1,(;10,
0,;0,
),(
nsnWSK n a p
nSk n a p
nSfa ls e
Sfa ls e
Str u e
nSK n a p
n
且当或且当当当由上述定义不难编写出背包问题的递归算法。今写成递归函数的形式。
3、栈与递归第三章 栈和队列第 61页
Status Knap( int S,int n )
{ if( S == 0 ) return true;
if((S<0) || (S>0 && n<1)) return false;
if( Knap( S - W[n],n-1) == true )
{ printf(“%d,,W[n]); return true }
return (Knap(S,n-1));
} //Knap
注,算法中假设 Wi(i=1,2,···,n)均为正整数，并已经存放在一维整型数组 W之中。
3、栈与递归第三章 栈和队列第 62页递归函数的 优点,
(1) 结构清晰，易于理解；
(2) 正确性容易证明；
(3) 易调试，易实现。
递归函数的 缺点,
(1) 实现效率较低，无论是时间还是空间都较非递归算法为差；
(2) 有些计算机高级语言不具有递归的功能，不支持递归。
递归与非递归的 取舍,① 若问题存在着明显的 迭代解法,则宜 避免使用递归 。 ② 倘若问题的 本质是递归 的，则宁可牺牲一些效率也应该使用递归，以便算法简洁易读。 ③ 对于 不允许递归的语言,或者是 特别强调算法的效率 时，可以先设计出递归算法,然后再将它转换成非递归算法。由于由系统实现递归时隐含着栈的处理，因此，用非递归算法来描述递归算法时，一般都包含着对栈的显式处理。
3、栈与递归
递归函数转换成非递归函数第三章 栈和队列第 63页递归函数转换成非递归函数的实质是：将原由系统进行管理的递归工作栈改为由程序员负责管理。
转换成非递归的算法的一般结构
//BEGIN
初始化栈；第一次进栈；
do
while（非递归终止条件） {入栈处理 }
if( top>1 )
{出栈处理 }
while(( top == 1 )&&(递归终止条件 ))
结束处理 ;
//END;
注,第一次进栈
top=1; S[top]=（参数表）；
若无初始进栈，则可将 1改成 0。
递归函数转换成非递归函数第三章 栈和队列第 64页示例 求阶乘函数的非递归算法递归算法,
int fact( int n )
{
if( n<=0 ) return 1;
return( n * fact(n-1));
} //fact
递归过程转换成非递归过程第三章 栈和队列第 65页非递归算法
int fact( int n )
{ int x; //存放结果
x = 1; InitStack(st);
do
while( n > 0 )
{
Push(st,n); n--; //入栈处理
}
if( st.top > 0 )
{
x *= Pop(st); //出栈处理
}
while( Empty(st));
return x;
} //fact
递归过程转换成非递归过程
int fact( int n )
{
if( n<=0 ) return 1;
return( n * fact(n-1));
} //fact
第三章 栈和队列第 66页示例 n阶 hanoi塔问题的 非递归算法 (用 While)
struct snode{
int np;
char xp,yp,zp;
};
hanoi2(int n,char x,char y,char z)
{
snode s[arrmax]; int top;
top=1; S[top]=(n,x,y,z); //栈初始化
while( !((top==1) && (S[top].np==1)))
{ while( S[top].np > 1 )
{ S[top+1] = (S[top].np-1,S[top].xp,S[top].zp,S[top].yp);
top++ };
move(S[top].xp,S[top].np,S[top].zp);
if( top>1 )
{ top--; move(S[top].xp,S[top].np,S[top].zp);
S[top].np--; S[top].xp? S[top].yp}
};
move(S[top].xp,1,S[top].zp); top--;
} //hanoi2 算 法 3.8
第三章 栈和队列第 67页示例 n阶 hanoi塔问题的 非递归算法 (用 do-while)
hanoi2(posint n,char x,char y,char z)
{
snode s [arrmax]; int top;
top=1; S[top]=(n,x,y,z); //栈初始化
do
while( S[top].np>1 )
{S[top+1]=(S[top].np-1,S[top].xp,S[top].zp,S[top].yp);
top++ };
move(S[top].xp,S[top].np,S[top].zp);
if( top>1 )
{ top--; move(S[top].xp,S[top].np,S[top].zp);
S[top].np--; S[top].xp? S[top].yp}
while((top==1) && (S[top].np==1))
top--;
} //hanoi2
有什么差别？
第三章 栈和队列第 68页示例 双递归阿克 Ackermann函数
递归过程转换成非递归过程
0,)),1,(,1(
0,)1,1(
0,1
),(
nmnmA c kmA c k
nmA c k
mn
nmA c k
Ackermann函数 递归函数 说明
int ack( int m,int n )
{
if( m==0 ) return n+1;
if( n==0 ) return ack(m-1,1)
return ack(m-1,ack(m,n-1))
} //ack
第三章 栈和队列第 69页
struct snode{
int m,n;
};
snode s[arrmax]; int top;
int Ack( int m,int n )
{ top=1; S[1]=(m,n); //栈初始化
do
while( S[top].m≠0 )
{ while( S[top].n ≠ 0 )
{ top++； S[top]=(S[top-1].m,s[top-1].n-1) };
s[top]=(s[top].m-1,1);
};
if( top>1 )
{top--; S[top]=(s[top].m-1,s[top+1].n+1)}
while((top==1) && (S[top].m==0));
top--; return (s[top+1].n+1)
} //Ack
Ackermann函数 非递归算法第三章 栈和队列第 70页定义 队列是限定仅能在表的一端进行插入，在表的另一端进行删除的线性表。 在队列中可以插入的一端称为 队尾 (rear)，可以删除的一端称为队头或 队首 (front)。
将一个元素插到队列中的操作叫做 入队列或进队,从队列中删除一个元素的操作叫做 出队列或出队 。队列是一种 先进先出 (First In
First Out,FIFO)的线性表，或简称队列是一种 FIFO结构。
队列的基本性质
(1) 均匀性,元素具有相同类型（属于同一个数据对象）；
(2) 有序性,线性有序；
(3) 受限的运算,一端插入，另一端删除。
出队列（出队） 入队列（进队）
队尾队头
a1 a2 a3 ··· ··· an
队列的逻辑结构
4、队 列第三章 栈和队列第 71页
Specification ADT Queue
Elements：所涉及对象的类型明显地取决于应用，可以是各种类型 的，只要 同属于一个数据对象 即可。
Structure,队列亦是一种线性结构，其数据元素之间呈线性关系。设 Q=(a1,a2,··,an)，则对每一个数据元素 ai(i=1,2,··,n-1)，都存在关系 <ai,ai+1>，并且 a1
无前趋,an无后继；队列又是一种受限的线性结构,该结构使先进队的元素先出队 。
Operations,可定义下列七种有关队列的基本操作
队列的抽象数据类型
4、队 列第三章 栈和队列第 72页
InitQueue ( queue &Q ); //初始化操作,生成空的队列
Status Empty( queue Q); //判队列空函数
//若队列为空，则返回函数值 true,否则返回 false
EnQueue( queue &Q; elemtp x ); //入队列操作
//若 队列不满,将一个新的元素 x插入到队列 Q的尾部位置上
elemtp DlQueue( queue &Q ) //出队列函数
/*队列不空,返回队头元素的值并删除该队头元素； 若队列为空，
则返回空元素值 NULL*/
elemtp GetHead( queue Q ); //取队头元素函数
/*队列不空,返回队头元素的值，但队列本身没有改变； 若队列为空，则返回空元素值 NULL*/
elemtp Clear( queue &Q ); //队列置空操作
//不论队列 Q是否为空队列，本操作结果将 Q置为空队列
int CurrentSize ( queue Q); //求队列长度函数
//返回队列中当前数据元素的个数
队列的抽象数据类型第三章 栈和队列第 73页用链表表示的队列称为链接队列，或简称为链对列。
链队列 —— 队列的链式存储结构
^···
q.front q.rear
附加头节点 队头 队尾
^q.frontq.rear空链队列：
队头指针 队尾指针链队列应包含两个指针,队头指针,队尾指针为了操作方便，给链队列 附加一个头节点 。
第三章 栈和队列第 74页
链队列 —— 队列的链式存储结构
^···
q.front q.rear
附加头节点 队头 队尾队头指针 队尾指针
struct queuenode{
elemtp data;
queuenode *next;
};
struct linkedquetp{
queuenode *front,*rear;
};
链队列的表示：
第三章 栈和队列第 75页队列操作指针变化状况,
^
x ^
q.front
元素入队列,enqueue(q,x)
enqueue(q,y)
q.rear
q.front
q.rear
初始化队列,InitQueue(q)
y ^q.frontq.rear x
y ^q.frontq.rear x
链队列 —— 队列的链式存储结构定义 linkedquetp q
元素出队列,dlqueue(q)
设 queuenode *p p
第三章 栈和队列第 76页实现部分的语句编码
init_linkedque(linkedquetp &q )
{
q.front = new( queuenode ); //建链队列结点
q.rear = q.front;
q.front->next = NULL;
} //init_linkedque
en_linkedque(linkedquetp &q,elemtp x )
{
queueptr p;
p = new(queuenode );
p->data = x; p->next = NULL; //建新尾结点
q.rear->next = p; q.rear = p; //插入队尾
} //en_linkedque
链队列 —— 队列的链式存储结构下续第三章 栈和队列第 77页
Status dl_linkedque( linkedquetp &q,elemtp &e )
{
queueptr s; elemtp x;
if( q.front == q.rear ) //队列为空
return false;
s = q.front->next;
q.front->next = s->next; //删除链队列的队头元素
if ( !s->next )
q.rear = q.front; //若删除后队列为空则修改尾指针
x = s->data;
delete(s); //回收无用结点
e = x;
return OK; //返回该元素
} //dl_linkedque
承上
链队列 —— 队列的链式存储结构下续第三章 栈和队列第 78页
elemtp gethead_linkedque( linkedquetp q )
{
queueptr s;
if( q.front !=q.rear ) //队列为空
{
s = q.front->next; return s->data;
}
} //gethead_linkedque
Status empty_linkedque( linkedquetp q )
{
return (q.front == q.rear);
} //empty_linkedque
clear_linkedque( linkedquetp &q)
{
q.rear=q.front; q.front->next =NULL //还应考虑释放空间
} //clear_linkedque
承上
链队列 —— 队列的链式存储结构第三章 栈和队列第 79页队列的顺序存储结构用数组实现队列,定义一个数组和分别指向队头元素和队尾元素的游标。
约定,尾指针指示队尾元素在队列中的 下一个 位置，头指针指示队列中队头元素的 当前 位置。
数据结构描述
struct sequeuetp{
elemtp elem[maxsize];
int front,rear;
}
sequeuetp sq;
循环队列 —— 队列的顺序存储结构第三章 栈和队列第 80页顺序存储结构的队列的入队列、出队列操作示意
J4
sq.rear
sq.front
J6
J5
sq.rear
sq.front
J4
J3
J2
J1
sq.rear
sq.front
5
4
3
2
1
0sq.rearsq.front
(a) (b) (c) (d)
(a) 空队列； (b) J1,J2,J3,J4相继入队列；
(c) J1,J2,J3,J4相继出队列； (d) J4出队 J5,J6入队列 (加满 )。
队空,sq.front==sq.rear
队满,sq.rear==maxsize（可能是假溢出）
入队,sq.elem[sq.rear]=x； //x入队列
sq.rear++； //修改尾指针出队,sq.front++； //修改头指针队列的顺序存储结构第三章 栈和队列第 81页
Q.front
Q.rear
循环队列 —— 队列的顺序存储结构入队,cq.elem[cq.rear]=x；
cq.rear=(cq.rear+1) % maxsize；
出队,cq.front=(cq.front+1) % maxsize；
cq.front=cq.rear cq.front=cq.rear
J5
J6J4 5
0
12
4
3
cq.front
cq.rear
(a) 一般情况
J5
J6J4 5
0
12
4
3 J7
J8
J9
cq.front
cq.rear
(b) 队列满时
5 0
12
4
3
cq.front
cq.rear
(c) 空队列第三章 栈和队列第 82页
(d) 队列满时 (e) 空队列区分队满与队空的解决方法：
（ 1）设一标志位记录队列的状态
（ 2）少用一个元素的空间
5 0
12
4
3
J5
J6J4 5
0
12
4
3 J7
J8
cq.front
cq.rear
cq.front
cq.rear
循环队列 —— 队列的顺序存储结构
(cq.rear+1) % maxsize==cq.front cq.front==cq.rear
第三章 栈和队列第 83页
const int maxsize = maxarrlen； //队列的最大容量
struct cyclicquetp{elemtp elem[maxsize];
int rear,front;
};
init_cycque( cyclicquetp &cq );
Status en_cycque( cyclicquetp &cq,elemtp x);
Status dl_cycque( cyclicquetp &cq,elemtp x);
elemtp en_cycque( cyclicquetp cq,elemtp x );
elemtp gethead_cycque( cyclicquetp cq );
Status full_cycque( cyclicquetp cq );
Status empty_cycque( cyclicquetp cq );
clear_cycque( cyclicquetp &cq );
int size_cycque( cyclicquetp cq);
… …
循环队列抽象数据类型的模块说明第三章 栈和队列第 84页实现部分的语句编码
init_cycque( cyclicquetp &cq )
{
cq.front = 0; cq.rear = 0;
} //init_cycque
Status en_cycque( cyclicquetp &cq,elemtp x )
{
if(((cq.rear+1) % maxsize ) == cq.front )
return false; //队列已满
else
{ cq.elem[cq.rear] = x;
cq.rear = (cq.rear+1) % maxsize;
return true;
}
} //en_cycque
循环队列 —— 队列的顺序存储结构第三章 栈和队列第 85页
Status dl_cycque( cyclicquetp &cq,elemtp &e )
{
if( cq.front==cq.rear ) //队列为空
return false;
dl_cycque = cq.elem[cq.front];
cq.front = (cq.front+1) % maxsize;
} //dl_cycque
elemtp gethead_cycque( cyclicquetp cq )
{
if( cq.front==cq.rear ) //队列为空
return null;
else
return cq.elem[cq.front];
} //gethead_cycque
循环队列 —— 队列的顺序存储结构第三章 栈和队列第 86页
clear_cycque ( cycliquetp &cq )
{
cq.rear = cq.front;
} //clean_cycque
int size_cycque( cyclicqetp cq )
{
return
(cq.rear+maxsize -cq.front) % maxsize;
} //size_cycque
循环队列 —— 队列的顺序存储结构第三章 栈和队列第 87页双端队列又称双向队列。它是限定插入和删除操作在表的两端进行的线性表。这两端分别记为 end1,end2，上限、下限均可增、
减。
插入 a1 a2 a3··· an 插入删除 删除end1 end2
输入受限的双端队列（超栈）
end2end1
双端队列
end1 end2
输出受限的双端队列（超队列）
双向队列输入 输出铁路转轨图第三章 栈和队列第 88页示例 1 模拟客观世界的一些排队过程。如售票窗外、服务台前、食堂窗口等。顾客按先后次序排队。
先排者先服务，然后离队；新来者排队尾，依次等候
。
示例 2 多道作业请求通过打印机通道输出。可按请求输出的先后次序，将这些作业排成一个队列。每当通道输出完毕可以接受新的输出任务时，将队头的作业出队，作输出操作。凡是申请输出的作业都是从队尾进入队列。
示例 3 键盘输入的输入字符队列。
示例 4 没有优先级的作业等待队列。
队列的应用举例第三章 栈和队列第 89页所谓 离散事件模拟 （ Discrete Event Simulation）指的是模拟一个这样的系统，其中系统状态的所有变化可以假定是在某些离散的时间瞬间中发生的。正被模拟的“系统
”通常是一个个别的活动体的集合，这些活动体是基本上独立的，虽然它们彼此交互作用。其例子如：商店里的顾客、港口中的船只、一个团体中的人们等等。 在一个离散事件的模拟中，在某个模拟时间进行着有待完成的事件（
事件驱动），然后把模拟时钟推进到某个动作预定要出现的下个时刻 。
离散事件模拟第三章 栈和队列第 90页示例 银行业务的模拟程序。模拟银行的业务活动，并计算一天中客户在银行逗留的平均时间。假定银行在 4个窗口提供服务。
[分析 ] 考虑以下三个方面：
1,顾客到达银行和离开银行为两个事件。由于模拟是按事件发生的先后次序进行，因此建立一个有序的事件表来存储各个事件（
到达、离开。
2,程序中模拟顾客的到来约定为：当一个顾客在到达后，要为下一个顾客的到来产生一个时间间隔；同时产生本次顾客的事务处理时间。这可由产生两个随机数来确定,(durtime,intertime)：
durtime：本次顾客办理事务所需时间
intertime：下一顾客到来的时间间隔
3,每个顾客来后，总是到 4个窗口中有最短队长的窗口排队；
每个队的队头顾客就是正在办理事务的顾客，离开队列就是顾客离开事件时刻。
离散事件模拟第三章 栈和队列第 91页银行客户的离散事件驱动模拟程序框架（算法 3.9）
Func Bank_Simulation;
{ //统计一天内客户在银行逗留的平均时间
Open_For_Day; //初始化
while( More_Event )
{Event_Drived (Occurtime,Event_Type); //事件驱动
switch( Event_Type ){
case `A`,Customer_Arrived;
//处理客户到达事件
case `D`,Customer_Departure;
//处理客户离开事件
default,Invalid
};
};
Close_For_Day; //计算逗留平均时间
} //Bank_Simulation
离散事件模拟第三章 栈和队列第 92页设立一个事件表，用于存储两类事件，由于到达、离开频繁，
因此采用链表作为存储结构。
事件链表类型 说明,
#define maxsize 2000;
struct Event_node{
int occurtime; //事件发生时刻
int ntype; /*事件类型,0表示到达事件,1至 4分别表示四个窗口的离开事件 */
}；
typedef LinkList Event_List //事件的链表类型，定义为有序链表。
init_Eventlist ( Event_List &ev );
ins_Eventlist ( Event_List &ev; Event_node en );
Event_node del_Eventlist ( Event_List &ev);
Status empty_Eventlist ( Event_List ev);
离散事件模拟第三章 栈和队列第 93页设立四个队列，分别表示四个窗口的排队情况。队列也采用链表结构
struct elemtp{
int arrivaltime; //到达时间
int duration; //办理事务所需时间
};
struct queuenode{
elemtp data;
queuenode *next;
};
typedef queueptr *queuenode;
struct Linkedquetp{
queueptr front,rear;
};
下续
离散事件模拟第三章 栈和队列第 94页
init_linkedque ( linkedquetp &q );
en_linkedque ( linkedquetp &q,elemtp x );
elemtp dl_linkedque (linkedquetp &q);
elemtp gethead_linkedque (linkedquetp q);
Status empty_linkedque ( linkedquetp q );
clean_linkedque (linkedquetp &q);
int size_linkedque ( linkedquetp q );
承上
离散事件模拟第三章 栈和队列第 95页算法 3.10
CONST int closetime= … ; // 银行关门时刻
Event_List ev; //事件链表
Event_Node en;
linkedquetp q[4]; //4个窗口队列
elemtp customer;
int totaltime,customernum; //计时，计数
离散事件模拟下续第三章 栈和队列第 96页
Open_For_Day() //初始化操作
{ totaltime=0;
customernum=0; //客户人数计数器
init_Eventlist(ev); //初始化事件链表为空表，即 ev.first=0
en.occurtime=0; en.ntype=0; //设定第一个客户到达事件
ins_Eventlist(ev,en); //插入事件表
for( i =1; i <= 4; i++ )
init_linkedque (q[i]); {置空队列 }
} //Open_For_Day
执行 Open_For_Day,将产生如下结构 front
rear
front
rear
front
rear
front
rear
∧
∧
∧
∧
q 队列状态事 件 表
0 0 ^
ev.first=1
1
en.ntype
en.occurtime
离散事件模拟承上下续第三章 栈和队列第 97页
Customer_Arrived ( Event_node en)
{ //处理客户到达事件,en.ntype=0
customernum++; //增加一名客户
Random(durtime,intertime);
/*产生随机数：
durtime：此时刻到达的客户办理事务所需时间
intertime：下一客户将到达的时间间隔 */
t = en.occurtime + intertime; //下一客户到达时刻
if( t<closetime ) //若银行尚未关门，则插入事件表
ins_Eventlist (ev,(t,0));
i =Minimum(q); //求最短队列
en_linkedque(q[i],(en.occurtime,durtime)); //加入最短队列
if( size_linkedque(q[i])==1 ) //是排头
ins_Eventlist(ev,(en.occurtime+durtime,i))
//设定一个第 i个队列客户离开事件插入事件表
} //Customer_Arrived
离散事件模拟承上下续第三章 栈和队列第 98页
Customer_Departure ( Event_node en)
{ //处理客户离开事件,en.ntype>0
i=en.ntype; //那个窗口
customer=dl_linkedque(q[i]);
//从第 i个队列中删除排头客户
totaltime+= (en.occurtime -customer.arrivaltime);
//累计客户逗留时间
if( !empty_linkedque(q[i]))
{customer=gethead_linkedque (q[i]);
ins_Eventlist (ev,(en.occurtime+
customer.duration i))
} //设定一个新的第 i个队列客户离开事件插入事件表
} //Customer_Departure
离散事件模拟承上第三章 栈和队列第 99页
void Bank_Simulation()
{
OpenForDay(); //初始化
while( !EmptyEventList( ev )){
DelFirst( GetHead( ev ),p );
en = GetCurElem( p );
if( en.ntype == 0 )
CustomArrived( en );
else
CustomDeparture( en );
} //while
printf( ―Average Time,%f‖,TotalTime/CustomNum );
}
离散事件模拟第三章 栈和队列第 100页例 3 - 5：假设每个客户办理业务的时间不超过 30分钟；两个相邻到达银行的客户的时间间隔不超过 5分钟，模拟程序从第一个客户到达时间为,0‖开始运行。
离散事件模拟
front
rear
front
rear
front
rear
front
rear
∧
∧
∧
∧
q 队列状态事 件 表
0 0 ^
ev.first
1
en.ntype
en.occurtime
下续初始化状态第三章 栈和队列第 101页
离散事件模拟
front
rear
front
rear
front
rear
front
rear
q 队列状态事 件 表
4 0
ev.first
en.ntypeen.occurtime
下续
0时刻：第一个客户到达
∧
∧
∧
0 23∧
(23,4)
23 1 ^
第三章 栈和队列第 102页
离散事件模拟
front
rear
front
rear
front
rear
front
rear
q 队列状态事 件 表
ev.first
en.ntypeen.occurtime
下略
4时刻：第二个客户到达
23 1 ^
∧
∧
0 23∧
(3,1) 5 0
4 3∧
7 2
第三章 栈和队列第 103页第三章 栈和队列 小结内容栈和队列的逻辑结构定义,各自的特点,ADT定义，在两种存储结构上如何实现栈和队列的基本运算,递归及其内部实现，
在递归算法中怎样使用栈，栈和队列在程序中的典型应用（如表达式求值，离散事件模拟）。
要点
掌握栈和队列这两种数据结构的特点，了解它们的使用场合
熟悉栈、队列与线性表的关系；顺序栈、顺序队列与顺序表的关系；链栈、链队列与链表的关系
掌握在顺序栈、链栈（循环队列、链队列）上实现的栈（队列）
的几种基本运算，特别注意栈（队）满和栈（队）空的条件及它们的描述
理解递归算法执行过程中栈的状态变化过程
掌握栈与队列的典型应用
