1北京邮电大学自动化学院
第三章 栈和队列
?3.1 栈
?3.2 栈的应用举例
?3.3 队列
2北京邮电大学自动化学院
?1 栈的定义
?栈 (Stack)是限制在表的
一端进行插入和删除运
算的线性表。
a1
a2
a n-1
a n
……
top
base
出栈 进栈
?通常称插入、删除的这
一端为 栈顶 (Top),另一
端为 栈底 (Base)。
?当表中没有元素时称为
空栈。
3.1.1抽象数据类型栈的定义
3北京邮电大学自动化学院
图 3.1栈的示意图
1,栈的定义
a1
a2
a n-1
a n
……
top
base
出栈 进栈?假设栈 S=(a1,a2，
a3,…a n)，则 a1称为栈底
元素,an为栈顶元素。栈中
元素按 a1,a2,a3,…a n的
次序进栈，退栈的第一个元
素应为栈顶元素。
?栈的特点：栈的修改是按
后进先出的原则进行的。
因此，栈称为后进先出表
（ LIFO）。
4北京邮电大学自动化学院
? （ 1）初始化
2、栈的基本操作
? （ 2）进栈
? （ 3）退栈
? （ 4）取栈顶元素
? （ 5）判栈是否非空
? （ 6）置栈空
5北京邮电大学自动化学院
? ADT stack{
? 数据对象,D={ai|ai?ElemSet,i=1,2,…,n,n>=0)}
? 数据关系,R1={<ai-1,ai>|ai-1,ai?D} 约定 an为栈顶,a1端为栈
底
3、栈的抽象数据类型的定义
? 基本操作：
? Initstack(&s)
? 操作结果,构造一个
空栈 s
? Destroystack(&s)
? 初始条件,栈已经存在
? 操作结果,栈 s被销毁
? Clearstack(&S)
? 初始条件,栈已经存在
? 操作结果,将 s清空为零
6北京邮电大学自动化学院
? StackEmpty(&s)
? 初始条件,栈已经存在
? 操作结果,若栈 S为空,则返回
TRUE,否则 FALSE.
3、栈的抽象数据类型的定义
? Push (&s,e)
? 初始条件,栈 S已经存在
? 操作结果,插入元素 e为新
的栈顶元素,
? StackLength(&s)
? 初始条件,栈 S已经存在
? 操作结果,返回栈 S的元素个
数,即栈的长度,
? GetTop(S,&e)
? 初始条件,栈已经存在
? 操作结果,用 e返回 S的栈
顶元素,
7北京邮电大学自动化学院
3、栈的抽象数据类型的定义
? Pop(&s,&e)
? 初始条件,栈已经存在且非空
? 操作结果,删除 S的栈顶元素,并用 e返回其值,
? }ADT Stack
8北京邮电大学自动化学院
和线性表类似，栈也有两种存储表示方法。 顺序栈、链栈。
3.1.2 栈的表示和实现
顺序栈,即栈的顺序存储结构是利用一组地址连续的存储单
元依次存放自栈底到栈顶的数据元素。同时附设指针 top指
示栈顶元素在顺序表中的位置。
通常的习惯做法是以 top=0表示空栈,鉴于 C语言中数组的下
标约定从 0开始，则当以 C语言作描述语言时，如此设定会
带来很大不方便 ;
一个合理的做法是：先为栈分配一个基本容量，然后在应用
过程中，当栈的空间不够使用时再逐段扩大。
另一方面,由于栈在使用过程中所需要最大空间的大小很难估
计,因此,一般来说,在初始化设计空栈时不应限定栈的最大容量,
9北京邮电大学自动化学院
为此设定两个常量,STACK_INIT_SIZE(存储空间初始分配量 )
和 STACKINCREMENT(存储空间分配增量 ),并以下述类型说明
作为顺序栈的定义,
其中,stacksize指示栈的当前可使用的最大容量。
typedef Struct{
SElemType *base;
SElemType *top;
int stacksize; }SqStack;
1,顺序栈
栈的初始化操作为, 按设定的初始分配量进行第一次存储分配，
base称为栈底指针,在顺序标中,它始终指向栈底的位置,若 base
的值为 NULL,则表明栈结构不存在,
10北京邮电大学自动化学院
例、一叠书或一叠盘子。
a n
a n-1
a2
a1
……
top
base
1,顺序栈
? 称 top为 栈顶指针,其初始值指
向栈底,即 top=base可作为 栈
空的标记,
? 每当插入新的栈顶元素时,
指针 top增 1;
? 删除栈顶元素时,指针 top减 1,
? 因此，非空栈中的栈顶指针始
终在栈顶元素的下一位置上。
左图展示了顺序栈中数据元素
和栈顶指针之间的对应关系。
11北京邮电大学自动化学院
进栈示例
退栈示例
12北京邮电大学自动化学院
栈的顺序存储表示
?#define STACK_INIT_SIZE 100;
?#define STACKINCREMENT 10;
?typedef Struct{
?SElemType *base;//在栈构造之前和销毁之后，
base的值为 NULL。
?SElemType *top;
?int stacksize; }SqStack;
13北京邮电大学自动化学院
?Status InitStack (SqStack &s);//构造一个空栈
基本操作的函数原型说明
?Status DestroyStack (SqStack &s);//销毁栈
?Status ClearStack (SqStack &s);//把 S置为空栈
?Status StackEmpty (SqStack s);//
?Status StackLengh (SqStack s);//
?Status GetTop (SqStack s,SElemType &e);//
?Status push (SqStack &s,SElemType e);//
?Status Pop (SqStack &s,SElemType &e);//
14北京邮电大学自动化学院
基本操作的算法描述
?Status InitStack (SqStack &s){//构造一个空栈
?S.base=（ SElemType *） malloc
（ Stack_init_size *sizeof（ ELlemType）） ;
? if (!S.base) exit (OVERFLOW);//存储分配失败
?S.top=S.base;
?S.stacksize=STACK_INIT_SIZE;
?return OK;
?}InitStack
15北京邮电大学自动化学院
基本操作的算法描述
?Status GetTop (SqStack &s,SElemtype &e){
?若栈不空，则用 e 返回 S的栈顶元素，并返回 OK；
否则返回 ERROR
?If (S.top==S.base) return ERROR;
?e=*(S.top-1);
?return OK;
?}GetTop
16北京邮电大学自动化学院
基本操作的算法描述
? Status Push (SqStack &s,SElemType e){/插入元素 e为新
的栈顶元素
? If (S.top-S.base>=S.stacksize){栈满，追加存储空间
? S.base=(SElemType*)remalloc(S.stacksize+STACKINCR
EMENT) *sizeof（ ELlemType）） ;
? if (!S.base) exit (OVERFLOW);//存储分配失败
? S.top=S.base+S.stacksize;
? S.stacksize+=STACKINCREMENT;}
? *S.top++=e; return OK;} //PUSH
17北京邮电大学自动化学院
基本操作的算法描述
?Status Pop (SqStack &s,SElemType e){//
?若栈不空，则删除 S的栈顶元素，用 e返回其值，
并返回 OK；否则返回 ERROR
?If (S.top==S.base ） return ERROR;
?e=*--S.top;
?return OK;} //Pop
18北京邮电大学自动化学院
? 栈的链式存储结构称为链栈,它是运算受限的单链表，插
入和删除操作仅限制在表头位置上进行。由于只能在链表
头部进行操作，故链表没有必要像单链表那样附加头结
点。栈顶指针就是链表的头指针。
2,链栈
? 链栈的类型说明如下：
? typedef struct stacknode {
?datatype data
?struct stacknode *next
?}stacknode;
19北京邮电大学自动化学院
? 链式栈的特点：
栈的链接表示 — 链式栈
? 链式栈无栈满问题
? 空间可扩充
? 插入与删除仅在栈顶处执行
? 链式栈的栈顶在链头
? 适合于多栈操作
20北京邮电大学自动化学院
计
算
顺
序
输
出
顺
序
? 例 1,数制转换 十进制数 N和其他 d进制数的转换是计算机实
现计算的基本问题。其中一个简单算法基于下列原理,
3.2 栈的应用举例
? 例如,（ 1348)10 = (2504)8,其运算过程如下：
? N=(N div d)?d+N mod d
? N N div 8 N mod
? 1348 168 4
? 168 21 0
? 21 2 5
? 2 0 2
21北京邮电大学自动化学院
? void conversion () {//对于输入的任意一个非负十进制整
数，打印输出与其等值的八进制数 。
例 1、数制转换
? InitStack(S); //构造空栈
? scanf ("%d",N); ? while (!StackEmpty(S))
{
? Pop(S,e);
? printf ( "%d",e );}
? }
? // conversion
? while (N)
? {
? Push(S,N % 8);
? N = N/8;
? }
22北京邮电大学自动化学院
? 假设在表达式中允许包含两种括号,园括号和方括号,其嵌套是随
意,并假定 （［］（））或［（［ ］［ ］）］等为正确的格式,
? 分析可能出现的不匹配的情况,
例 2,括号匹配的检验
? 例如：考虑下列括号序列,[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
? ［（ ］）或（［（ ））或 (( )])均为不正确的格式。
? 检验括号是否匹配的方法,可用,期待的急迫程度,这个概
念来描述。
?到来的右括弧非是所“期待”的 ;
?到来的是“不速之客” ;
?直到结束，也没有到来所“期待”的括弧 ;。
23北京邮电大学自动化学院
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
? 当计算机接受了第 1个括号后，它期待着与其匹配的第 8个括
号的出现，然而等来的却是第 2个括号，此时 第 1个括号,[‖
只能暂时靠边,“期待的急迫程度”最高 是 第 2个括号
“（” 。? 而迫切等待与第 2个括号“（”相匹配的第 7个扩号“）”的
出现，类似地，因等来的是第 3个括号,[‖,其期待匹配的程
度较第 2个括号更急迫,则第 2个括号也只能靠边，让位于第 3
个括号,[‖,显然第 2个括号,(‖的期待急迫性高于第 1个括号
,[‖;? 在接受了第四个括号,]‖之后,第 3个括号的期待得到满足,消
解之后，第 2个括号的期待匹配就成为当前最急迫的任务
了,……,依次类推；
? 可见这个处理过程恰好与栈的特点相吻合。
24北京邮电大学自动化学院
括号匹配的检验 算法的设计思想
? 1）凡出现左括弧，则进栈； 自然使原有的在栈中的所有
未消解的期待的急迫性都降了一级。
? 2）凡出现右括弧，首先检查栈是否空
? 3）表达式检验结束时，
? 否则和栈顶元素比较
? 否则表明不匹配
? 若相匹配，则“左括
弧出栈”
?若栈空，则表明该“右括弧”多余
? 若栈空，则表明表达式中匹配正确
? 否则表明“左括弧”有余
25北京邮电大学自动化学院
? Status matching(string& exp) { int state = 1;
? while (i<=Length(exp) && state) {
? switch of exp[i] {case ―(‖:{Push(S,exp[i]); i++; break;}
? case ―)‖,{
? if(NOT StackEmpty(S) && GetTop(S)=― (‖) {Pop(S,e); i++;}
? else {state = 0;}
? break; } … … }
? if (StackEmpty(S) && state) return OK; …...
括号匹配的检验 算法
26北京邮电大学自动化学院
如何实现？
“每接受一个字符即存入存储器”?
并不恰当！
例 3、行编辑程序问题
? 合理的作法是,设立一个输入缓冲区，用以接受用户输入
的一行字符，然后逐行存入用户数据区 ; 并假设,#‖为退格
符，,@‖为退行符。
? 在用户输入一行的过程中，允许用户输入出差错，并在发
现有误时可以及时更正。
? 一个简单的行编辑程序的功能是,接受用户从终端输入
的程序或数据,并存入用户的数据区,
27北京邮电大学自动化学院
? 例如,当用户发现刚刚输入的一个字符是错的时候,可以补进
一个,#‖,以表示前一个字符无效 ;
? 如果发现当前输入的行内差错太多或难以补救,则可以键入
一个退行符,@‖,以表示当前行中的字符均无效。
? 假设从终端接受了这样两行字符：
? whli# #ilr#e（ s#*s)
? outcha@putchar(*s=#++);
? 则实际有效的是下列两行：
? while (*s)
? putchar(*s++);
例 3、行编辑程序问题
28北京邮电大学自动化学院
while (ch != EOF && ch != '\n') {
switch (ch) {
?case ?#?, Pop(S,c); break;//仅当栈非空时退栈
?case '@',ClearStack (S); break;// 重置 S为空栈
? default, Push(S,ch); break; //有效字符进栈 }
? ch = getchar(); // 从终端接收下一个字符 }
ClearStack (S); // 重置 S为空栈
if (ch != EOF) ch = getchar();}
while (ch != EOF) { //EOF为全文结束符
将从栈底到栈顶的字符传送至调用过程的数据区；
29北京邮电大学自动化学院
? 求迷宫中从入口到出口的所有路径是一个经典的程序设计问
题。计算机解迷宫问题，通常用的是“穷举求解”的方法。
# # # # # # # # # #
# ? ? # $ $ $ # #
# ? # $ $ $ # #
# ? ? $ $ # # #
# ? # # # # #
# ? ? ? # # #
# # ? ? ? # #
# # # # # ? # # #
# ? ? ? ? #
# # # # # # # # # #
例 4,迷宫求解
30北京邮电大学自动化学院
? 即从入口出发，顺某一方向向前探索，若能走通，则继续往
前走；否则沿原路退回，换一个方向再继续探索，直到所有
可能的通路都探索到为止。
例 4,迷宫求解
? 为了保证在任何位置上都能沿原路退回，显然需要用一个后
进先出的结构来保存从入口到当前位置的路径。因此，在求
迷宫通路的算法中应用“栈”也就是自然而然的事了。
? 首先，在计算机可以用图所示的方块表示迷宫。 途中的每个
方块或为通道（以白方块表示），或为墙（以带阴影的方块
表示）。 所求路径必须是 简单路径,即在求得的路径上不能
重复出现同一通道块。
31北京邮电大学自动化学院
? 假设“当前位置”指的是“在搜索过程中某一时刻所在图中某
个方块的位置”，则求迷宫中一条路径的算法的基本思想是：
? 若当前位置“不可通”，则应顺着“来向”退回到“前一通道
块”，然后朝着除“来向”之外的其它方向继续探索；
? 若当前位置“可通”，则纳入路径，并继续朝“下一个位置”
探索，即切换“下一位置”为“当前位置”,如此重复直至到达
出口；
?若该通道块的四周 4个方块均“不可通”，则应从“当前路
径”上删除该通道块。所谓“下一位置”指的是“当前位
置”四周四个方向（东、南、西、北）上相邻的方块。
? 假设以栈 S记录“当前路径”，则栈顶中存放的是“当前路径
上最后一个通道块”。由此，“纳入路径”的操作即为“当前
位置入栈”；,从当前路径上删除前一通道块”的操作即为
“出栈”。
32北京邮电大学自动化学院
? 求迷宫中一条从入口到出口的路径的算法：
? 设定当前位置的初值为入口位置；
? do｛
? 若当前位置可通，
? 则｛ 将当前位置插入栈顶； //纳入路径
? 若该位置是出口位置，则算法结束； //求得路径
? 否则切换当前位置的东邻方块为新的当前位置；｝
? 否则 { 见下一页 }
? ｝ while (栈不空） ；
例 4,迷宫求解
( i,j ) 东
南
西
北
33北京邮电大学自动化学院
? do｛ 若当前位置可通，则｛ 见上一页｝ ;
? 否则
? 若栈不空且栈顶位置尚有其他方向未被探索，则设定新的
当前位置为, 沿顺时针方向旋转找到的栈顶位置的下一相
邻块；
? 若栈不空但栈顶位置的四周均不可通，则｛
? 删去栈顶位置； // 从路径中删去该通道块
? 若栈不空，则重新测试新的栈顶位置,直至找到一个
可通的相邻块或出栈至栈空； }
? ｝｝ while (栈不空）；
? 若栈空，则表明迷宫没有通路。 ( i,j ) 东
南
西
北
34北京邮电大学自动化学院
? 在此，尚需要说明一点的是，所谓当前位置可通，指的是未曾
走到过的通道块，即要求该方块的位置不仅是通道块，而且既
不在当前路径上（否则所求路径就不是简单路径），也不是曾
经纳入过路径的通道块（否则只能在死胡同内转圈）。
例 4,迷宫求解
? Typedef struct{
? Int ord; // 通道块在路径上的“序号”
? PosType seat; // 通道块在迷宫中的“坐标位置”
? Int di; // 从此通道块走向下一通道块的“方
向”
? }SElemType; / / 栈的元素类型
35北京邮电大学自动化学院
? Status Mazepath(MazeType maze,PosType
start,PosType end){
? //若迷宫中存在从入口到出口的通道,则求得一
条存放在栈中 (从 //栈底到栈顶 ),并返回 TRUE;否
则返回 FLASE;
? InitStack(S);
? curpos=start; //设定“当前位置”为“入口位
置”
? Curstep=1;//探索第一步
例 4,迷宫求解
36北京邮电大学自动化学院
? Do {If ( pass(curpos )) { //当前位置可以通过，即是未曾
走过的通道块
例 4,迷宫求解
? FootPrint ( curpos ); //留下足迹
? e=(curstep,curpos,1);
? Push(S,e);//加入路径
? If( curpos==end) return (TRUE); //到达终点（出口）
? curpos=NextPos(curpos,1);//下一位置是当前位置的东邻
? Curstep++;} //探索下一步
? }// if
37北京邮电大学自动化学院
? Else{//当前位置不通 If (!StackEmpty(S)) {
? Pop(S,e);
? While(e.di==4&&!StackEmpty(S)){
? MarkPrint(e.seat)； Pop(S,e);//留下不能通过的标记，并退
回一步 }//while
? If(e.di<4){ e.di++; Push(S,e);//换下一个方向探索
? Curpos=NextPos(e.seat,e.di);//设定当前位置是该新方向上
的相邻块 }//if }// if }//else
? } while (!StackEmpty(S ));
? Return(FALSE); }//MazePath
38北京邮电大学自动化学院
# # # # # # # # # #
# # # #
# # # #
# # # #
# # # # # #
# # # #
# # # #
# # # # # # # #
# ? #
# # # # # # # # # #
?
? ?
??
?
?
?
?
???
?
1 1 1
1 2 2
2 2 2
3 2 1
3 3 1
3 4 4
2 4 1
2 5 1
2 6 4
1 6 3
1 5 3
1 4 4
3
$ $ $
$$$
$$
例 4,迷宫求解
39北京邮电大学自动化学院
?例如 要对下面的表达式求值,4+2*3-10/5
例 5,表达式求值
?首先要了解算术四则运算的规则。即是：
? （ 1）先乘除，后加减；（ 2）从左到右；（ 3） 先括
号内，后括号外
?由此，这个算术表达式的计算顺序应为：
?4+2*3-10/5
?=4+6-10/5
?=10-10/5
?=10-2=8
40北京邮电大学自动化学院
? 任何一个表达式都是有 操作数、运算符和界限符 组成的。一
般,操作数 可以是常数也可以是被说明伟变量或常量的标注
符； 运算符 可以分算术运算符、关系运算符和逻辑运算符；
基本界限符有左右括号和表达式结束符等。
例 5,表达式求值
? 我们把运算符和界限符统称为 算符,它们构成的集合命名为
OP。
? 根据上述三条运算规则，在运算的每一步中，任意两个相继出现
的算符 Q1和 Q2之间的优先关系至多是下面的三种关系之一：
Q1<Q2 Q1的优先权低于 Q2
Q1=Q2 Q1的优先权等于 Q2
Q1>Q2 Q1的优先权高于 Q2
41北京邮电大学自动化学院
＋ － × ／ ( ) #
＋ > > < < < > >
－ > > < < < > >
× > > > > < > >
／ > > > > < > >
( < < < < < =
) > > > > > >
# < < < < < =
Q2
Q1
例 5,表达式求值
? 由规则 3，＋－
× 和 /为 Q1时的
优先性均低于
“（”但高于
“）”，当
Q1=Q2时，令
Q1>Q2，
“＃”是表达式
的结束符。在表
达式的最左边也
虚设一个“＃”
构成整个表达式
的一对括号。
? 表中的“（”＝“）”表示当左右
括号相遇时，括号内的运算结束。
同理，“＃”＝“＃”整个表达式
结束。
42北京邮电大学自动化学院
为了实现算符优先算法，可以使用两个工作栈。一个称做
OPTR，用以寄存运算符；另一个称做 OPND，用以寄存操
作数或运算结果。
例 5,表达式求值
算法的基本思想是：
首先置操作数栈为空栈，表达式起始符,#‖为运算符栈的栈
底元素；
依次读入表达式中每个字符，若是操作数则进 OPND栈，若
是运算符，则和 OPTR栈的栈顶运算符比较优先权后作相应
操作，直至整个表达式求值完毕（即 OPTR栈顶元素和当前
读入的字符均为,#‖）。
43北京邮电大学自动化学院
OperandType EvaluateExpression(){
//算术表达式求值的算符优先算法，设 OPTR和 OPND分别
为 运算符 栈和 运算数 栈, OP为运算符集合。
While(c!=‘#‘||GetTop(OPTR)!=―#‘){
InitStack(OPTR);Push(OPTR,‘#‘);
InitStack(OPND);c=getchar();
If(!In(c,OP)）
{Push((OPND,c);c=getchar();}//不是运算符则进栈
Else
例 5表达式求值的算法
44北京邮电大学自动化学院
If(!In(c,OP)） {Push((OPND,c);c=getchar();}//
Else
Switch Precede(GetTop(OPTR),c)){
Case ―<?:Push(OPTR,c);c=getchar();break;
Case ―=?:Pop(OPTR,x);c=getchar();break
Case ―>?,//退栈并将运算结果入栈
Pop(OPTR,theta);
Pop(OPND,b); Pop(OPND,a);
Push(OPND,Operate(a,theta,b));break; }
}//while
Return GetTop(OPND);
}//EvaluateExpression
45北京邮电大学自动化学院
步骤 OPTR栈 OPND栈 输入字符 主要操作
RETURN(GETTOP(OPND))
1 # 3*(7-2)# PUSH(OPND,?3?)
2 # 3 *(7-2)# PUSH(OPTR,?*?)
3 #* 3 (7-2)# PUSH(OPTR,?(?)
4 #*( 3 7-2)# PUSH(OPND,?7?)
5 #*( 37 -2)# PUSH(OPTR,?-?)
6 #*(- 37 2)# PUSH(OPND,?2?)
7 #*(- 372 )# operate(?7?,?-?,?2?)
8 #*( 35 )# Pop(OPTR)
9 #* 35 # operate(?3?,?*?,?5?)
10 # 15 #
46北京邮电大学自动化学院
例 6 栈与递归的实现
? 当在一个函数的运行期间调用另一个函数时，在运行该被调用
函数之前，需先完成三项任务：
?为被调用函数的局部变量分配存储区 ;
?将所有的实在参数、返回地址等信息传递给被调用函数保存 ;
?将控制转移到被调用函数的入口保存被调函数的计算结果 ;
? 从被调用函数返回调用函数之前，应该完成下列三项任务：
?保存被调函数的计算结果 ;
? 释放被调函数的数据区 ;
? 依照被调函数保存的返回地址将控制转移到调用函数。
47北京邮电大学自动化学院
?栈的应用
?过程的嵌套调用
r
主
程
序
s
rr
r
s
子
过
程
1 r
s
t
子
过
程
2 rs
t 子过
程
3
48北京邮电大学自动化学院
例 递归的执行情况分析
递归过程及其实现
void print(int w)
{ int i;
if ( w!=0)
{ print(w-1);
for(i=1;i<=w;++i)
printf(“%3d,”,w);
printf(“/n”);
}
}
运行结果：
1，
2,2，
3,3,3，
递归：函数直接或间接的调用自身叫 ~
实现：建立递归工作栈
49北京邮电大学自动化学院
递归调用执行情况如下：
主程序
(1)
print(w)
w=3;
3
print(2);
（ 1） w=3
top
(2) 输出,3,3,3
w
2
print(1);
（ 2） w=2
（ 1） w=3
top
(3) 输出,2,2
w 1
print(0);
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
(4)输出,1
w
0
（ 4） w=0
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
w
(2) 2
(1) 3
输出：
(3) 1
(2) 2
(1) 3
top
(1 ) 3
返回
(3)
(2)
(1) 3
top (4)
结束
50北京邮电大学自动化学院
Tower of Hanoi问题
? 问题描述,有 A,B,C三个塔座,A上套有 n个直径不同的圆
盘，按直径从小到大叠放，形如宝塔,编号 1,2,3…… n。 要
求将 n个圆盘从 A移到 C,叠放顺序不变，移动过程中遵循
下列原则：
A B C
12
3
? 每次只能移一个圆盘
? 圆盘可在三个塔座上任意移动
? 任何时刻，每个塔座上不能将大
盘压到小盘上
51北京邮电大学自动化学院
? 解决方法：
? 执行情况：递归工作栈保存内容：形参 n,x,y,z和返回地
址,返回地址用行编号表示
n x y z 返回地址
A B C
12
3
Tower of Hanoi问题
?n=1时，直接把圆盘从 A移到 C
?n>1时，先把上面 n-1个圆盘从 A移到 B,然后将 n号盘从
A移到 C,再将 n-1个盘从 B移到 C。
?即把求解 n个圆盘的 Hanoi问题转化为求解 n-1个圆盘的
Hanoi问题，依次类推，直至转化成只有一个圆盘的
Hanoi问题 。
52北京邮电大学自动化学院
? void hanoi (int n,char x,char y,char z) {
? 1 if (n==1)
? 2 move(x,1 z); // 将编号为１的圆盘从 x移到 z
? 3 else {
? 4 hanoi(n-1,x,z,y); // 将 x上编号为１至 n-1的圆盘移到
y,z作辅助塔
? 5 move(x,n,z); // 将编号为 n的圆盘从 x移到 z
? 6 hanoi(n-1,y,x,z); // 将 y上编号为１至 n-1的圆盘移到
z,x作辅助塔
? 7 }
? 8
53北京邮电大学自动化学院
main()
{ int m;
printf("Input number of disks”);
scanf("%d",&m);
printf(”Steps, %3d disks”,m);
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
12
3
3 A B C 0
3 A B C 0
2 A C B 6
3 A B C 0
2 A C B 6
1 A B C 6
A B C
3 A B C 0
2 A C B 6
54北京邮电大学自动化学院
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 A C B 6
1 C A B 8
A B C
3 A B C 0
2 A C B 6
3 A B C 0
3 A B C 0
2 A C B 6
55北京邮电大学自动化学院
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 B A C 8
3 A B C 0
2 B A C 8
1 B C A 6
A B C
3 A B C 0
2 B A C 8
3 A B C 0
56北京邮电大学自动化学院
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 B A C 8
1 A B C 8
A B C
3 A B C 0
2 B A C 8
3 A B C 0
栈空
3 A B C 0
2 B A C 8
57北京邮电大学自动化学院
3.3队列
? 3.3.1 抽象数据类型队列的定义
? 队列 (Queue)也是一种运算受限的线性表。它只允许在表的
一端进行插入，而在另一端进行删除。允许删除的一端称为
队头 (front)，允许插入的一端称为 队尾 (rear)。
? 例如：排队购物。操作系统中的作业排队。 先进入队列的成
员总是先离开队列 。因此队列亦称作先进先出 (First In First
Out)的线性表，简称 FIFO表。
? 当队列中没有元素时称为 空队列 。在空队列中依次加入元素
a1,a2,…a n之后,a1是队头元素,an是队尾元素。显然退出队
列的次序也只能是 a1,a2,…a n,也就是说队列的修改是依 先
进先出的原则进行的。
58北京邮电大学自动化学院
出队 入队
队头 队尾
下图是队列的示意图：
a1 a2 a3 an
? 队列的抽象数据定义见书Ｐ 59
? 双端队列,就是限定插入和删除操作在表的两端进行的线性
表。
? 尽管双端队列看起来似乎比栈和队列更灵活，但实际上在应
用程序中远不及栈和队列有用，故在此不作详细讨论。
59北京邮电大学自动化学院
设队首、队尾指针 front和 rear,
front指向头结点,rear指向队尾
? 队列的链式存储结构简称为 链队列,它是限制仅在表头删
除和表尾插入的单链表。显然仅有单链表的头指针不便于
在表尾做插入操作，为此再增加一个尾指针，指向链表的
最后一个结点。
3.3.2 链队列
头结点
…...front
队头 队尾
rear
60北京邮电大学自动化学院
front rear
x入 队 ^x
front rear
y入 队 x ^y
front rear
x出 队 x ^y
front rear
空队 ^
front rear
y出 队 ^
61北京邮电大学自动化学院
? 我们也是将这两个指针封装在一起，将链队列的类型
LinkQueue定义为一个结构类型：
? 链队列结点定义
? typedef struct Qnode
? { QElemType data;
? struct QNode *next;
? } QNode,*QueuPtr;
? Typedef struct{
? QueuPtr front;//对头指针
? QueuPtr rear;//对尾指针
? } LinkQueue
? 基本操作的函数原型说明见书本 P61。
62北京邮电大学自动化学院
基本操作的算法描述（部分）
?Status initQueue(linkqueue &Q)
?{//构造一个空队列 Q
?Q.front=Q.rear=(QueuePtr)malloc(sizeof QNode));
?If(!Q.front)exit (OVERFLOW);//存储分配失败
?Q–>front=Q–>rear=NULL;
?Return OK; }
63北京邮电大学自动化学院
基本操作的算法描述（部分）
?Status DestroyQueue(linkqueue &Q){
?//销毁队列 Q
?While(Q.front){
?Q.rear=Q.front->next;
?free(Q.front);
?Q.front=Q.rear;
?return OK;}
64北京邮电大学自动化学院
? Status EnQueue( LinkQueue &Q,QElemType e)
? //插入元素 e为 Q的新的队尾元素； {
? p=(QueuePtr * )malloc ( sizeof(QNode));
? if (!p) exit (OVERFLOW);//存储分配失败
? p–>data=e;
? p–>next=NULL;
? Q.rear->next=p;
? Q.rear=p;
? return OK;}
65北京邮电大学自动化学院
Status DeQueue(LinkQueue &Q,QElemType &e)
? 注意,在出队算法中，一般只需修改队头指针。但当原队中
只有一个结点时，该结点既是队头也是队尾，故删去此结点
时亦需修改尾指针，且删去此结点后队列变空。
? //若队列不空，则删除 Q的队头元素，用 e返回其值，并返回
OK；否则返回 ERROR {
? if( Q.front==Q.rear) return ERROR;
? p=Q.front->next; e=p–>data;
? Q–>front->next=p–>next;
? if(Q.rear==p) Q.rear=Q.front;
? free(p); return OK;}
66北京邮电大学自动化学院
3.3.2 循环队列－队列的顺序表示和实现
?队列的顺序存储结构称为 顺序队列,在队列的顺序存储
结构中，除了用一组地址连续的储存单元依次存放从对
头到对尾的元素之外，尚需要附设两个指针 front和 rear
分别指示队列头元素和队列尾元素的位置。
?为了在 C语言中描述方便起见，在此我们约定：初始化
建空队列时，令 front＝ rear＝ 0。每当插入新的队列尾
元素时“尾指针增 1‖；每当删除队列头元素时“头指针
增 1‖。
?因此，在非空队列中,头指针始终指向队头元素，而尾
指针始终指向队尾元素的下一位置。
67北京邮电大学自动化学院
J1
J2
J3
rear
? 设两个指针 front,rear,约定,在非
空队列中,front始终 指 向对头元
素； Rear始终 指 向队列 尾元素 的下
一位置 ；初值 front=rear=0
? 空队列条件,front==rear
? 入队列,sq[++rear]=x;
? 出队列,x=sq[++front];
rear
rear
fron
t
front
front
front
队列的顺序存储结构
1
2
3
4
5
0front
J1,J1,J3入队
rear
1
2
3
4
5
0
J1,J2,J3出队
J1
J2
J3
rear
1
2
3
4
5
0
J4,J5,J6入队
J4
J5
J6
fron
t
front=0
rear=0
1
2
3
4
5
0
队空
? 实现：用一维数组实现 sq[M]
68北京邮电大学自动化学院
? 存在问题 rear
1
2
3
4
5
0
J4,J5,J6入队
J4
J5
J6
front
0
M-1
1
front
rear
? 设数组维数为 M,则,当 front=0,rear=M-1时，
再有元素入队发生溢出 ——真溢出
? 解决方案 ? 队首固定，每次出队剩余元素向下移动 ——浪费时间
? 循环队列
? 基本思想,把队列设想成环形，让 sq[0]接
在 sq[M-1]之后，若 rear+1==M,则令
rear=0;
? 当 front?0,rear=M-1时，再有元素入队发生溢
出 ——假溢出
69北京邮电大学自动化学院
0
M-1
1
front
rear
?实现：利用“模”运算
队列的序存储结构
?入队,rear=(rear+1)%M;
? sq[rear]=x;
?出队,front=(front+1)%M
? x=sq[front];
? 队满、队空判定条件
70北京邮电大学自动化学院
? 队满,front==rear?
? 解决方案：
J4
J5
J60
123
4 5
rear
front
初始状态
1
234
5 0
rear
front
? 1.另外设一个标志以区别队空、队满
? 2.少用一个元素空间，约定以“队列
头指针在队列尾指针的下一位置
上”，作为队列呈“满”状态的标
志。
? 队空,front==rear ? 队满,(rear+1)%M==front
J4
J5
J60
123
4 5
rear
front
J9
J8
J7
71北京邮电大学自动化学院
?1,掌握栈和队列类型的特点，并能在相应的应用
问题中正确选用它们。
?2,熟练掌握栈类型的两种实现方法，特别应注意
栈满和栈空的条件以及它们的描述方法。
?3,熟练掌握循环队列和链队列的基本操作实现算
法，特别注意队满和队空的描述方法。
?4,理解递归算法执行过程中栈的状态变化过程。
第 3章学习要点
72北京邮电大学自动化学院
第 3章 作业
? 一、单项选择题
? 1、栈的特点是 B,队列的特点是 A 。
? （ A）先进先出 （ B）先进后出
? 2、栈和队列的共同特点是 C 。
? （ A）都是先进后出 （ B）都是先进先出
? （ C）只允许在端点处插入和删除元素 （ D）没有共同点
? 3、一个栈的进栈序列是 a,b,c,d,e，则栈的不可能的
输出序列是 C 。
? （ A） edcba （ B） decba （ C） dceab （ D） abcde
73北京邮电大学自动化学院
? 4、若已知一个栈的进栈序列是 p1,p2,p3,…, pn 。其输
出序列为 1,2,3,…, n,若 p3=1，则 p1为 C 。
（ A）可能是 2（ B）一定是 2（ C）不可能是 2 （ D）不可能是 3
第 3章 习题
? 5、设有一个空栈，栈顶指针为 1000H（十六进制，下
同），现有输入序列为 1,2,3,4,5，经过 PUSH，
PUSH,POP,PUSH,POP,PUSH,PUSH后，输出
序列是 3,栈顶指针是 8 。
? ① 5,4,3,2,1 ② 2,1 ③ 2,3
? ④ 3,4 ⑤ 1002H ⑥ 1004H
? ⑦ 1005H ⑧ 1003H
74北京邮电大学自动化学院
? 6、一个队列的入对序列是若 1,2,3,4，则队列的输出序
列是 B 。
（ A） 4,3,2,1 （ B） 1,2,3,4
（ C） 1,4,3,2 （ D） 3,2,4,1
第 3章 习题
? 7、若用一个大小为 6的一维数组来实现循环队列，且当前
rear和 front的值分别为 0和 3。当从队列中删除一个元素，再
加入两个元素后,rear和 front的值分别是 B 。
（ A） 1和 5 （ B） 2和 4 （ C） 4和 2 （ D） 5和 1
75北京邮电大学自动化学院
第 3章 思考题
? 1、有 5个元素，其入栈次序为 A,B,C,D,E，在各种可
能的出栈次序中，以元素 C,D最先出栈（即 C第一个且 D
第二个出栈）的次序有哪几个？
? 2、设计算法判断一个算术表达式的圆括号是否正确配对。
（提示：对表达式进行扫描，凡遇到“（”就进栈，遇到
“）”就退掉栈顶的“（”，表达式被扫描完毕，栈应为
空。）
第三章 栈和队列
?3.1 栈
?3.2 栈的应用举例
?3.3 队列
2北京邮电大学自动化学院
?1 栈的定义
?栈 (Stack)是限制在表的
一端进行插入和删除运
算的线性表。
a1
a2
a n-1
a n
……
top
base
出栈 进栈
?通常称插入、删除的这
一端为 栈顶 (Top),另一
端为 栈底 (Base)。
?当表中没有元素时称为
空栈。
3.1.1抽象数据类型栈的定义
3北京邮电大学自动化学院
图 3.1栈的示意图
1,栈的定义
a1
a2
a n-1
a n
……
top
base
出栈 进栈?假设栈 S=(a1,a2，
a3,…a n)，则 a1称为栈底
元素,an为栈顶元素。栈中
元素按 a1,a2,a3,…a n的
次序进栈，退栈的第一个元
素应为栈顶元素。
?栈的特点：栈的修改是按
后进先出的原则进行的。
因此，栈称为后进先出表
（ LIFO）。
4北京邮电大学自动化学院
? （ 1）初始化
2、栈的基本操作
? （ 2）进栈
? （ 3）退栈
? （ 4）取栈顶元素
? （ 5）判栈是否非空
? （ 6）置栈空
5北京邮电大学自动化学院
? ADT stack{
? 数据对象,D={ai|ai?ElemSet,i=1,2,…,n,n>=0)}
? 数据关系,R1={<ai-1,ai>|ai-1,ai?D} 约定 an为栈顶,a1端为栈
底
3、栈的抽象数据类型的定义
? 基本操作：
? Initstack(&s)
? 操作结果,构造一个
空栈 s
? Destroystack(&s)
? 初始条件,栈已经存在
? 操作结果,栈 s被销毁
? Clearstack(&S)
? 初始条件,栈已经存在
? 操作结果,将 s清空为零
6北京邮电大学自动化学院
? StackEmpty(&s)
? 初始条件,栈已经存在
? 操作结果,若栈 S为空,则返回
TRUE,否则 FALSE.
3、栈的抽象数据类型的定义
? Push (&s,e)
? 初始条件,栈 S已经存在
? 操作结果,插入元素 e为新
的栈顶元素,
? StackLength(&s)
? 初始条件,栈 S已经存在
? 操作结果,返回栈 S的元素个
数,即栈的长度,
? GetTop(S,&e)
? 初始条件,栈已经存在
? 操作结果,用 e返回 S的栈
顶元素,
7北京邮电大学自动化学院
3、栈的抽象数据类型的定义
? Pop(&s,&e)
? 初始条件,栈已经存在且非空
? 操作结果,删除 S的栈顶元素,并用 e返回其值,
? }ADT Stack
8北京邮电大学自动化学院
和线性表类似，栈也有两种存储表示方法。 顺序栈、链栈。
3.1.2 栈的表示和实现
顺序栈,即栈的顺序存储结构是利用一组地址连续的存储单
元依次存放自栈底到栈顶的数据元素。同时附设指针 top指
示栈顶元素在顺序表中的位置。
通常的习惯做法是以 top=0表示空栈,鉴于 C语言中数组的下
标约定从 0开始，则当以 C语言作描述语言时，如此设定会
带来很大不方便 ;
一个合理的做法是：先为栈分配一个基本容量，然后在应用
过程中，当栈的空间不够使用时再逐段扩大。
另一方面,由于栈在使用过程中所需要最大空间的大小很难估
计,因此,一般来说,在初始化设计空栈时不应限定栈的最大容量,
9北京邮电大学自动化学院
为此设定两个常量,STACK_INIT_SIZE(存储空间初始分配量 )
和 STACKINCREMENT(存储空间分配增量 ),并以下述类型说明
作为顺序栈的定义,
其中,stacksize指示栈的当前可使用的最大容量。
typedef Struct{
SElemType *base;
SElemType *top;
int stacksize; }SqStack;
1,顺序栈
栈的初始化操作为, 按设定的初始分配量进行第一次存储分配，
base称为栈底指针,在顺序标中,它始终指向栈底的位置,若 base
的值为 NULL,则表明栈结构不存在,
10北京邮电大学自动化学院
例、一叠书或一叠盘子。
a n
a n-1
a2
a1
……
top
base
1,顺序栈
? 称 top为 栈顶指针,其初始值指
向栈底,即 top=base可作为 栈
空的标记,
? 每当插入新的栈顶元素时,
指针 top增 1;
? 删除栈顶元素时,指针 top减 1,
? 因此，非空栈中的栈顶指针始
终在栈顶元素的下一位置上。
左图展示了顺序栈中数据元素
和栈顶指针之间的对应关系。
11北京邮电大学自动化学院
进栈示例
退栈示例
12北京邮电大学自动化学院
栈的顺序存储表示
?#define STACK_INIT_SIZE 100;
?#define STACKINCREMENT 10;
?typedef Struct{
?SElemType *base;//在栈构造之前和销毁之后，
base的值为 NULL。
?SElemType *top;
?int stacksize; }SqStack;
13北京邮电大学自动化学院
?Status InitStack (SqStack &s);//构造一个空栈
基本操作的函数原型说明
?Status DestroyStack (SqStack &s);//销毁栈
?Status ClearStack (SqStack &s);//把 S置为空栈
?Status StackEmpty (SqStack s);//
?Status StackLengh (SqStack s);//
?Status GetTop (SqStack s,SElemType &e);//
?Status push (SqStack &s,SElemType e);//
?Status Pop (SqStack &s,SElemType &e);//
14北京邮电大学自动化学院
基本操作的算法描述
?Status InitStack (SqStack &s){//构造一个空栈
?S.base=（ SElemType *） malloc
（ Stack_init_size *sizeof（ ELlemType）） ;
? if (!S.base) exit (OVERFLOW);//存储分配失败
?S.top=S.base;
?S.stacksize=STACK_INIT_SIZE;
?return OK;
?}InitStack
15北京邮电大学自动化学院
基本操作的算法描述
?Status GetTop (SqStack &s,SElemtype &e){
?若栈不空，则用 e 返回 S的栈顶元素，并返回 OK；
否则返回 ERROR
?If (S.top==S.base) return ERROR;
?e=*(S.top-1);
?return OK;
?}GetTop
16北京邮电大学自动化学院
基本操作的算法描述
? Status Push (SqStack &s,SElemType e){/插入元素 e为新
的栈顶元素
? If (S.top-S.base>=S.stacksize){栈满，追加存储空间
? S.base=(SElemType*)remalloc(S.stacksize+STACKINCR
EMENT) *sizeof（ ELlemType）） ;
? if (!S.base) exit (OVERFLOW);//存储分配失败
? S.top=S.base+S.stacksize;
? S.stacksize+=STACKINCREMENT;}
? *S.top++=e; return OK;} //PUSH
17北京邮电大学自动化学院
基本操作的算法描述
?Status Pop (SqStack &s,SElemType e){//
?若栈不空，则删除 S的栈顶元素，用 e返回其值，
并返回 OK；否则返回 ERROR
?If (S.top==S.base ） return ERROR;
?e=*--S.top;
?return OK;} //Pop
18北京邮电大学自动化学院
? 栈的链式存储结构称为链栈,它是运算受限的单链表，插
入和删除操作仅限制在表头位置上进行。由于只能在链表
头部进行操作，故链表没有必要像单链表那样附加头结
点。栈顶指针就是链表的头指针。
2,链栈
? 链栈的类型说明如下：
? typedef struct stacknode {
?datatype data
?struct stacknode *next
?}stacknode;
19北京邮电大学自动化学院
? 链式栈的特点：
栈的链接表示 — 链式栈
? 链式栈无栈满问题
? 空间可扩充
? 插入与删除仅在栈顶处执行
? 链式栈的栈顶在链头
? 适合于多栈操作
20北京邮电大学自动化学院
计
算
顺
序
输
出
顺
序
? 例 1,数制转换 十进制数 N和其他 d进制数的转换是计算机实
现计算的基本问题。其中一个简单算法基于下列原理,
3.2 栈的应用举例
? 例如,（ 1348)10 = (2504)8,其运算过程如下：
? N=(N div d)?d+N mod d
? N N div 8 N mod
? 1348 168 4
? 168 21 0
? 21 2 5
? 2 0 2
21北京邮电大学自动化学院
? void conversion () {//对于输入的任意一个非负十进制整
数，打印输出与其等值的八进制数 。
例 1、数制转换
? InitStack(S); //构造空栈
? scanf ("%d",N); ? while (!StackEmpty(S))
{
? Pop(S,e);
? printf ( "%d",e );}
? }
? // conversion
? while (N)
? {
? Push(S,N % 8);
? N = N/8;
? }
22北京邮电大学自动化学院
? 假设在表达式中允许包含两种括号,园括号和方括号,其嵌套是随
意,并假定 （［］（））或［（［ ］［ ］）］等为正确的格式,
? 分析可能出现的不匹配的情况,
例 2,括号匹配的检验
? 例如：考虑下列括号序列,[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
? ［（ ］）或（［（ ））或 (( )])均为不正确的格式。
? 检验括号是否匹配的方法,可用,期待的急迫程度,这个概
念来描述。
?到来的右括弧非是所“期待”的 ;
?到来的是“不速之客” ;
?直到结束，也没有到来所“期待”的括弧 ;。
23北京邮电大学自动化学院
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
? 当计算机接受了第 1个括号后，它期待着与其匹配的第 8个括
号的出现，然而等来的却是第 2个括号，此时 第 1个括号,[‖
只能暂时靠边,“期待的急迫程度”最高 是 第 2个括号
“（” 。? 而迫切等待与第 2个括号“（”相匹配的第 7个扩号“）”的
出现，类似地，因等来的是第 3个括号,[‖,其期待匹配的程
度较第 2个括号更急迫,则第 2个括号也只能靠边，让位于第 3
个括号,[‖,显然第 2个括号,(‖的期待急迫性高于第 1个括号
,[‖;? 在接受了第四个括号,]‖之后,第 3个括号的期待得到满足,消
解之后，第 2个括号的期待匹配就成为当前最急迫的任务
了,……,依次类推；
? 可见这个处理过程恰好与栈的特点相吻合。
24北京邮电大学自动化学院
括号匹配的检验 算法的设计思想
? 1）凡出现左括弧，则进栈； 自然使原有的在栈中的所有
未消解的期待的急迫性都降了一级。
? 2）凡出现右括弧，首先检查栈是否空
? 3）表达式检验结束时，
? 否则和栈顶元素比较
? 否则表明不匹配
? 若相匹配，则“左括
弧出栈”
?若栈空，则表明该“右括弧”多余
? 若栈空，则表明表达式中匹配正确
? 否则表明“左括弧”有余
25北京邮电大学自动化学院
? Status matching(string& exp) { int state = 1;
? while (i<=Length(exp) && state) {
? switch of exp[i] {case ―(‖:{Push(S,exp[i]); i++; break;}
? case ―)‖,{
? if(NOT StackEmpty(S) && GetTop(S)=― (‖) {Pop(S,e); i++;}
? else {state = 0;}
? break; } … … }
? if (StackEmpty(S) && state) return OK; …...
括号匹配的检验 算法
26北京邮电大学自动化学院
如何实现？
“每接受一个字符即存入存储器”?
并不恰当！
例 3、行编辑程序问题
? 合理的作法是,设立一个输入缓冲区，用以接受用户输入
的一行字符，然后逐行存入用户数据区 ; 并假设,#‖为退格
符，,@‖为退行符。
? 在用户输入一行的过程中，允许用户输入出差错，并在发
现有误时可以及时更正。
? 一个简单的行编辑程序的功能是,接受用户从终端输入
的程序或数据,并存入用户的数据区,
27北京邮电大学自动化学院
? 例如,当用户发现刚刚输入的一个字符是错的时候,可以补进
一个,#‖,以表示前一个字符无效 ;
? 如果发现当前输入的行内差错太多或难以补救,则可以键入
一个退行符,@‖,以表示当前行中的字符均无效。
? 假设从终端接受了这样两行字符：
? whli# #ilr#e（ s#*s)
? outcha@putchar(*s=#++);
? 则实际有效的是下列两行：
? while (*s)
? putchar(*s++);
例 3、行编辑程序问题
28北京邮电大学自动化学院
while (ch != EOF && ch != '\n') {
switch (ch) {
?case ?#?, Pop(S,c); break;//仅当栈非空时退栈
?case '@',ClearStack (S); break;// 重置 S为空栈
? default, Push(S,ch); break; //有效字符进栈 }
? ch = getchar(); // 从终端接收下一个字符 }
ClearStack (S); // 重置 S为空栈
if (ch != EOF) ch = getchar();}
while (ch != EOF) { //EOF为全文结束符
将从栈底到栈顶的字符传送至调用过程的数据区；
29北京邮电大学自动化学院
? 求迷宫中从入口到出口的所有路径是一个经典的程序设计问
题。计算机解迷宫问题，通常用的是“穷举求解”的方法。
# # # # # # # # # #
# ? ? # $ $ $ # #
# ? # $ $ $ # #
# ? ? $ $ # # #
# ? # # # # #
# ? ? ? # # #
# # ? ? ? # #
# # # # # ? # # #
# ? ? ? ? #
# # # # # # # # # #
例 4,迷宫求解
30北京邮电大学自动化学院
? 即从入口出发，顺某一方向向前探索，若能走通，则继续往
前走；否则沿原路退回，换一个方向再继续探索，直到所有
可能的通路都探索到为止。
例 4,迷宫求解
? 为了保证在任何位置上都能沿原路退回，显然需要用一个后
进先出的结构来保存从入口到当前位置的路径。因此，在求
迷宫通路的算法中应用“栈”也就是自然而然的事了。
? 首先，在计算机可以用图所示的方块表示迷宫。 途中的每个
方块或为通道（以白方块表示），或为墙（以带阴影的方块
表示）。 所求路径必须是 简单路径,即在求得的路径上不能
重复出现同一通道块。
31北京邮电大学自动化学院
? 假设“当前位置”指的是“在搜索过程中某一时刻所在图中某
个方块的位置”，则求迷宫中一条路径的算法的基本思想是：
? 若当前位置“不可通”，则应顺着“来向”退回到“前一通道
块”，然后朝着除“来向”之外的其它方向继续探索；
? 若当前位置“可通”，则纳入路径，并继续朝“下一个位置”
探索，即切换“下一位置”为“当前位置”,如此重复直至到达
出口；
?若该通道块的四周 4个方块均“不可通”，则应从“当前路
径”上删除该通道块。所谓“下一位置”指的是“当前位
置”四周四个方向（东、南、西、北）上相邻的方块。
? 假设以栈 S记录“当前路径”，则栈顶中存放的是“当前路径
上最后一个通道块”。由此，“纳入路径”的操作即为“当前
位置入栈”；,从当前路径上删除前一通道块”的操作即为
“出栈”。
32北京邮电大学自动化学院
? 求迷宫中一条从入口到出口的路径的算法：
? 设定当前位置的初值为入口位置；
? do｛
? 若当前位置可通，
? 则｛ 将当前位置插入栈顶； //纳入路径
? 若该位置是出口位置，则算法结束； //求得路径
? 否则切换当前位置的东邻方块为新的当前位置；｝
? 否则 { 见下一页 }
? ｝ while (栈不空） ；
例 4,迷宫求解
( i,j ) 东
南
西
北
33北京邮电大学自动化学院
? do｛ 若当前位置可通，则｛ 见上一页｝ ;
? 否则
? 若栈不空且栈顶位置尚有其他方向未被探索，则设定新的
当前位置为, 沿顺时针方向旋转找到的栈顶位置的下一相
邻块；
? 若栈不空但栈顶位置的四周均不可通，则｛
? 删去栈顶位置； // 从路径中删去该通道块
? 若栈不空，则重新测试新的栈顶位置,直至找到一个
可通的相邻块或出栈至栈空； }
? ｝｝ while (栈不空）；
? 若栈空，则表明迷宫没有通路。 ( i,j ) 东
南
西
北
34北京邮电大学自动化学院
? 在此，尚需要说明一点的是，所谓当前位置可通，指的是未曾
走到过的通道块，即要求该方块的位置不仅是通道块，而且既
不在当前路径上（否则所求路径就不是简单路径），也不是曾
经纳入过路径的通道块（否则只能在死胡同内转圈）。
例 4,迷宫求解
? Typedef struct{
? Int ord; // 通道块在路径上的“序号”
? PosType seat; // 通道块在迷宫中的“坐标位置”
? Int di; // 从此通道块走向下一通道块的“方
向”
? }SElemType; / / 栈的元素类型
35北京邮电大学自动化学院
? Status Mazepath(MazeType maze,PosType
start,PosType end){
? //若迷宫中存在从入口到出口的通道,则求得一
条存放在栈中 (从 //栈底到栈顶 ),并返回 TRUE;否
则返回 FLASE;
? InitStack(S);
? curpos=start; //设定“当前位置”为“入口位
置”
? Curstep=1;//探索第一步
例 4,迷宫求解
36北京邮电大学自动化学院
? Do {If ( pass(curpos )) { //当前位置可以通过，即是未曾
走过的通道块
例 4,迷宫求解
? FootPrint ( curpos ); //留下足迹
? e=(curstep,curpos,1);
? Push(S,e);//加入路径
? If( curpos==end) return (TRUE); //到达终点（出口）
? curpos=NextPos(curpos,1);//下一位置是当前位置的东邻
? Curstep++;} //探索下一步
? }// if
37北京邮电大学自动化学院
? Else{//当前位置不通 If (!StackEmpty(S)) {
? Pop(S,e);
? While(e.di==4&&!StackEmpty(S)){
? MarkPrint(e.seat)； Pop(S,e);//留下不能通过的标记，并退
回一步 }//while
? If(e.di<4){ e.di++; Push(S,e);//换下一个方向探索
? Curpos=NextPos(e.seat,e.di);//设定当前位置是该新方向上
的相邻块 }//if }// if }//else
? } while (!StackEmpty(S ));
? Return(FALSE); }//MazePath
38北京邮电大学自动化学院
# # # # # # # # # #
# # # #
# # # #
# # # #
# # # # # #
# # # #
# # # #
# # # # # # # #
# ? #
# # # # # # # # # #
?
? ?
??
?
?
?
?
???
?
1 1 1
1 2 2
2 2 2
3 2 1
3 3 1
3 4 4
2 4 1
2 5 1
2 6 4
1 6 3
1 5 3
1 4 4
3
$ $ $
$$$
$$
例 4,迷宫求解
39北京邮电大学自动化学院
?例如 要对下面的表达式求值,4+2*3-10/5
例 5,表达式求值
?首先要了解算术四则运算的规则。即是：
? （ 1）先乘除，后加减；（ 2）从左到右；（ 3） 先括
号内，后括号外
?由此，这个算术表达式的计算顺序应为：
?4+2*3-10/5
?=4+6-10/5
?=10-10/5
?=10-2=8
40北京邮电大学自动化学院
? 任何一个表达式都是有 操作数、运算符和界限符 组成的。一
般,操作数 可以是常数也可以是被说明伟变量或常量的标注
符； 运算符 可以分算术运算符、关系运算符和逻辑运算符；
基本界限符有左右括号和表达式结束符等。
例 5,表达式求值
? 我们把运算符和界限符统称为 算符,它们构成的集合命名为
OP。
? 根据上述三条运算规则，在运算的每一步中，任意两个相继出现
的算符 Q1和 Q2之间的优先关系至多是下面的三种关系之一：
Q1<Q2 Q1的优先权低于 Q2
Q1=Q2 Q1的优先权等于 Q2
Q1>Q2 Q1的优先权高于 Q2
41北京邮电大学自动化学院
＋ － × ／ ( ) #
＋ > > < < < > >
－ > > < < < > >
× > > > > < > >
／ > > > > < > >
( < < < < < =
) > > > > > >
# < < < < < =
Q2
Q1
例 5,表达式求值
? 由规则 3，＋－
× 和 /为 Q1时的
优先性均低于
“（”但高于
“）”，当
Q1=Q2时，令
Q1>Q2，
“＃”是表达式
的结束符。在表
达式的最左边也
虚设一个“＃”
构成整个表达式
的一对括号。
? 表中的“（”＝“）”表示当左右
括号相遇时，括号内的运算结束。
同理，“＃”＝“＃”整个表达式
结束。
42北京邮电大学自动化学院
为了实现算符优先算法，可以使用两个工作栈。一个称做
OPTR，用以寄存运算符；另一个称做 OPND，用以寄存操
作数或运算结果。
例 5,表达式求值
算法的基本思想是：
首先置操作数栈为空栈，表达式起始符,#‖为运算符栈的栈
底元素；
依次读入表达式中每个字符，若是操作数则进 OPND栈，若
是运算符，则和 OPTR栈的栈顶运算符比较优先权后作相应
操作，直至整个表达式求值完毕（即 OPTR栈顶元素和当前
读入的字符均为,#‖）。
43北京邮电大学自动化学院
OperandType EvaluateExpression(){
//算术表达式求值的算符优先算法，设 OPTR和 OPND分别
为 运算符 栈和 运算数 栈, OP为运算符集合。
While(c!=‘#‘||GetTop(OPTR)!=―#‘){
InitStack(OPTR);Push(OPTR,‘#‘);
InitStack(OPND);c=getchar();
If(!In(c,OP)）
{Push((OPND,c);c=getchar();}//不是运算符则进栈
Else
例 5表达式求值的算法
44北京邮电大学自动化学院
If(!In(c,OP)） {Push((OPND,c);c=getchar();}//
Else
Switch Precede(GetTop(OPTR),c)){
Case ―<?:Push(OPTR,c);c=getchar();break;
Case ―=?:Pop(OPTR,x);c=getchar();break
Case ―>?,//退栈并将运算结果入栈
Pop(OPTR,theta);
Pop(OPND,b); Pop(OPND,a);
Push(OPND,Operate(a,theta,b));break; }
}//while
Return GetTop(OPND);
}//EvaluateExpression
45北京邮电大学自动化学院
步骤 OPTR栈 OPND栈 输入字符 主要操作
RETURN(GETTOP(OPND))
1 # 3*(7-2)# PUSH(OPND,?3?)
2 # 3 *(7-2)# PUSH(OPTR,?*?)
3 #* 3 (7-2)# PUSH(OPTR,?(?)
4 #*( 3 7-2)# PUSH(OPND,?7?)
5 #*( 37 -2)# PUSH(OPTR,?-?)
6 #*(- 37 2)# PUSH(OPND,?2?)
7 #*(- 372 )# operate(?7?,?-?,?2?)
8 #*( 35 )# Pop(OPTR)
9 #* 35 # operate(?3?,?*?,?5?)
10 # 15 #
46北京邮电大学自动化学院
例 6 栈与递归的实现
? 当在一个函数的运行期间调用另一个函数时，在运行该被调用
函数之前，需先完成三项任务：
?为被调用函数的局部变量分配存储区 ;
?将所有的实在参数、返回地址等信息传递给被调用函数保存 ;
?将控制转移到被调用函数的入口保存被调函数的计算结果 ;
? 从被调用函数返回调用函数之前，应该完成下列三项任务：
?保存被调函数的计算结果 ;
? 释放被调函数的数据区 ;
? 依照被调函数保存的返回地址将控制转移到调用函数。
47北京邮电大学自动化学院
?栈的应用
?过程的嵌套调用
r
主
程
序
s
rr
r
s
子
过
程
1 r
s
t
子
过
程
2 rs
t 子过
程
3
48北京邮电大学自动化学院
例 递归的执行情况分析
递归过程及其实现
void print(int w)
{ int i;
if ( w!=0)
{ print(w-1);
for(i=1;i<=w;++i)
printf(“%3d,”,w);
printf(“/n”);
}
}
运行结果：
1，
2,2，
3,3,3，
递归：函数直接或间接的调用自身叫 ~
实现：建立递归工作栈
49北京邮电大学自动化学院
递归调用执行情况如下：
主程序
(1)
print(w)
w=3;
3
print(2);
（ 1） w=3
top
(2) 输出,3,3,3
w
2
print(1);
（ 2） w=2
（ 1） w=3
top
(3) 输出,2,2
w 1
print(0);
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
(4)输出,1
w
0
（ 4） w=0
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
w
(2) 2
(1) 3
输出：
(3) 1
(2) 2
(1) 3
top
(1 ) 3
返回
(3)
(2)
(1) 3
top (4)
结束
50北京邮电大学自动化学院
Tower of Hanoi问题
? 问题描述,有 A,B,C三个塔座,A上套有 n个直径不同的圆
盘，按直径从小到大叠放，形如宝塔,编号 1,2,3…… n。 要
求将 n个圆盘从 A移到 C,叠放顺序不变，移动过程中遵循
下列原则：
A B C
12
3
? 每次只能移一个圆盘
? 圆盘可在三个塔座上任意移动
? 任何时刻，每个塔座上不能将大
盘压到小盘上
51北京邮电大学自动化学院
? 解决方法：
? 执行情况：递归工作栈保存内容：形参 n,x,y,z和返回地
址,返回地址用行编号表示
n x y z 返回地址
A B C
12
3
Tower of Hanoi问题
?n=1时，直接把圆盘从 A移到 C
?n>1时，先把上面 n-1个圆盘从 A移到 B,然后将 n号盘从
A移到 C,再将 n-1个盘从 B移到 C。
?即把求解 n个圆盘的 Hanoi问题转化为求解 n-1个圆盘的
Hanoi问题，依次类推，直至转化成只有一个圆盘的
Hanoi问题 。
52北京邮电大学自动化学院
? void hanoi (int n,char x,char y,char z) {
? 1 if (n==1)
? 2 move(x,1 z); // 将编号为１的圆盘从 x移到 z
? 3 else {
? 4 hanoi(n-1,x,z,y); // 将 x上编号为１至 n-1的圆盘移到
y,z作辅助塔
? 5 move(x,n,z); // 将编号为 n的圆盘从 x移到 z
? 6 hanoi(n-1,y,x,z); // 将 y上编号为１至 n-1的圆盘移到
z,x作辅助塔
? 7 }
? 8
53北京邮电大学自动化学院
main()
{ int m;
printf("Input number of disks”);
scanf("%d",&m);
printf(”Steps, %3d disks”,m);
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
12
3
3 A B C 0
3 A B C 0
2 A C B 6
3 A B C 0
2 A C B 6
1 A B C 6
A B C
3 A B C 0
2 A C B 6
54北京邮电大学自动化学院
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 A C B 6
1 C A B 8
A B C
3 A B C 0
2 A C B 6
3 A B C 0
3 A B C 0
2 A C B 6
55北京邮电大学自动化学院
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 B A C 8
3 A B C 0
2 B A C 8
1 B C A 6
A B C
3 A B C 0
2 B A C 8
3 A B C 0
56北京邮电大学自动化学院
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 B A C 8
1 A B C 8
A B C
3 A B C 0
2 B A C 8
3 A B C 0
栈空
3 A B C 0
2 B A C 8
57北京邮电大学自动化学院
3.3队列
? 3.3.1 抽象数据类型队列的定义
? 队列 (Queue)也是一种运算受限的线性表。它只允许在表的
一端进行插入，而在另一端进行删除。允许删除的一端称为
队头 (front)，允许插入的一端称为 队尾 (rear)。
? 例如：排队购物。操作系统中的作业排队。 先进入队列的成
员总是先离开队列 。因此队列亦称作先进先出 (First In First
Out)的线性表，简称 FIFO表。
? 当队列中没有元素时称为 空队列 。在空队列中依次加入元素
a1,a2,…a n之后,a1是队头元素,an是队尾元素。显然退出队
列的次序也只能是 a1,a2,…a n,也就是说队列的修改是依 先
进先出的原则进行的。
58北京邮电大学自动化学院
出队 入队
队头 队尾
下图是队列的示意图：
a1 a2 a3 an
? 队列的抽象数据定义见书Ｐ 59
? 双端队列,就是限定插入和删除操作在表的两端进行的线性
表。
? 尽管双端队列看起来似乎比栈和队列更灵活，但实际上在应
用程序中远不及栈和队列有用，故在此不作详细讨论。
59北京邮电大学自动化学院
设队首、队尾指针 front和 rear,
front指向头结点,rear指向队尾
? 队列的链式存储结构简称为 链队列,它是限制仅在表头删
除和表尾插入的单链表。显然仅有单链表的头指针不便于
在表尾做插入操作，为此再增加一个尾指针，指向链表的
最后一个结点。
3.3.2 链队列
头结点
…...front
队头 队尾
rear
60北京邮电大学自动化学院
front rear
x入 队 ^x
front rear
y入 队 x ^y
front rear
x出 队 x ^y
front rear
空队 ^
front rear
y出 队 ^
61北京邮电大学自动化学院
? 我们也是将这两个指针封装在一起，将链队列的类型
LinkQueue定义为一个结构类型：
? 链队列结点定义
? typedef struct Qnode
? { QElemType data;
? struct QNode *next;
? } QNode,*QueuPtr;
? Typedef struct{
? QueuPtr front;//对头指针
? QueuPtr rear;//对尾指针
? } LinkQueue
? 基本操作的函数原型说明见书本 P61。
62北京邮电大学自动化学院
基本操作的算法描述（部分）
?Status initQueue(linkqueue &Q)
?{//构造一个空队列 Q
?Q.front=Q.rear=(QueuePtr)malloc(sizeof QNode));
?If(!Q.front)exit (OVERFLOW);//存储分配失败
?Q–>front=Q–>rear=NULL;
?Return OK; }
63北京邮电大学自动化学院
基本操作的算法描述（部分）
?Status DestroyQueue(linkqueue &Q){
?//销毁队列 Q
?While(Q.front){
?Q.rear=Q.front->next;
?free(Q.front);
?Q.front=Q.rear;
?return OK;}
64北京邮电大学自动化学院
? Status EnQueue( LinkQueue &Q,QElemType e)
? //插入元素 e为 Q的新的队尾元素； {
? p=(QueuePtr * )malloc ( sizeof(QNode));
? if (!p) exit (OVERFLOW);//存储分配失败
? p–>data=e;
? p–>next=NULL;
? Q.rear->next=p;
? Q.rear=p;
? return OK;}
65北京邮电大学自动化学院
Status DeQueue(LinkQueue &Q,QElemType &e)
? 注意,在出队算法中，一般只需修改队头指针。但当原队中
只有一个结点时，该结点既是队头也是队尾，故删去此结点
时亦需修改尾指针，且删去此结点后队列变空。
? //若队列不空，则删除 Q的队头元素，用 e返回其值，并返回
OK；否则返回 ERROR {
? if( Q.front==Q.rear) return ERROR;
? p=Q.front->next; e=p–>data;
? Q–>front->next=p–>next;
? if(Q.rear==p) Q.rear=Q.front;
? free(p); return OK;}
66北京邮电大学自动化学院
3.3.2 循环队列－队列的顺序表示和实现
?队列的顺序存储结构称为 顺序队列,在队列的顺序存储
结构中，除了用一组地址连续的储存单元依次存放从对
头到对尾的元素之外，尚需要附设两个指针 front和 rear
分别指示队列头元素和队列尾元素的位置。
?为了在 C语言中描述方便起见，在此我们约定：初始化
建空队列时，令 front＝ rear＝ 0。每当插入新的队列尾
元素时“尾指针增 1‖；每当删除队列头元素时“头指针
增 1‖。
?因此，在非空队列中,头指针始终指向队头元素，而尾
指针始终指向队尾元素的下一位置。
67北京邮电大学自动化学院
J1
J2
J3
rear
? 设两个指针 front,rear,约定,在非
空队列中,front始终 指 向对头元
素； Rear始终 指 向队列 尾元素 的下
一位置 ；初值 front=rear=0
? 空队列条件,front==rear
? 入队列,sq[++rear]=x;
? 出队列,x=sq[++front];
rear
rear
fron
t
front
front
front
队列的顺序存储结构
1
2
3
4
5
0front
J1,J1,J3入队
rear
1
2
3
4
5
0
J1,J2,J3出队
J1
J2
J3
rear
1
2
3
4
5
0
J4,J5,J6入队
J4
J5
J6
fron
t
front=0
rear=0
1
2
3
4
5
0
队空
? 实现：用一维数组实现 sq[M]
68北京邮电大学自动化学院
? 存在问题 rear
1
2
3
4
5
0
J4,J5,J6入队
J4
J5
J6
front
0
M-1
1
front
rear
? 设数组维数为 M,则,当 front=0,rear=M-1时，
再有元素入队发生溢出 ——真溢出
? 解决方案 ? 队首固定，每次出队剩余元素向下移动 ——浪费时间
? 循环队列
? 基本思想,把队列设想成环形，让 sq[0]接
在 sq[M-1]之后，若 rear+1==M,则令
rear=0;
? 当 front?0,rear=M-1时，再有元素入队发生溢
出 ——假溢出
69北京邮电大学自动化学院
0
M-1
1
front
rear
?实现：利用“模”运算
队列的序存储结构
?入队,rear=(rear+1)%M;
? sq[rear]=x;
?出队,front=(front+1)%M
? x=sq[front];
? 队满、队空判定条件
70北京邮电大学自动化学院
? 队满,front==rear?
? 解决方案：
J4
J5
J60
123
4 5
rear
front
初始状态
1
234
5 0
rear
front
? 1.另外设一个标志以区别队空、队满
? 2.少用一个元素空间，约定以“队列
头指针在队列尾指针的下一位置
上”，作为队列呈“满”状态的标
志。
? 队空,front==rear ? 队满,(rear+1)%M==front
J4
J5
J60
123
4 5
rear
front
J9
J8
J7
71北京邮电大学自动化学院
?1,掌握栈和队列类型的特点，并能在相应的应用
问题中正确选用它们。
?2,熟练掌握栈类型的两种实现方法，特别应注意
栈满和栈空的条件以及它们的描述方法。
?3,熟练掌握循环队列和链队列的基本操作实现算
法，特别注意队满和队空的描述方法。
?4,理解递归算法执行过程中栈的状态变化过程。
第 3章学习要点
72北京邮电大学自动化学院
第 3章 作业
? 一、单项选择题
? 1、栈的特点是 B,队列的特点是 A 。
? （ A）先进先出 （ B）先进后出
? 2、栈和队列的共同特点是 C 。
? （ A）都是先进后出 （ B）都是先进先出
? （ C）只允许在端点处插入和删除元素 （ D）没有共同点
? 3、一个栈的进栈序列是 a,b,c,d,e，则栈的不可能的
输出序列是 C 。
? （ A） edcba （ B） decba （ C） dceab （ D） abcde
73北京邮电大学自动化学院
? 4、若已知一个栈的进栈序列是 p1,p2,p3,…, pn 。其输
出序列为 1,2,3,…, n,若 p3=1，则 p1为 C 。
（ A）可能是 2（ B）一定是 2（ C）不可能是 2 （ D）不可能是 3
第 3章 习题
? 5、设有一个空栈，栈顶指针为 1000H（十六进制，下
同），现有输入序列为 1,2,3,4,5，经过 PUSH，
PUSH,POP,PUSH,POP,PUSH,PUSH后，输出
序列是 3,栈顶指针是 8 。
? ① 5,4,3,2,1 ② 2,1 ③ 2,3
? ④ 3,4 ⑤ 1002H ⑥ 1004H
? ⑦ 1005H ⑧ 1003H
74北京邮电大学自动化学院
? 6、一个队列的入对序列是若 1,2,3,4，则队列的输出序
列是 B 。
（ A） 4,3,2,1 （ B） 1,2,3,4
（ C） 1,4,3,2 （ D） 3,2,4,1
第 3章 习题
? 7、若用一个大小为 6的一维数组来实现循环队列，且当前
rear和 front的值分别为 0和 3。当从队列中删除一个元素，再
加入两个元素后,rear和 front的值分别是 B 。
（ A） 1和 5 （ B） 2和 4 （ C） 4和 2 （ D） 5和 1
75北京邮电大学自动化学院
第 3章 思考题
? 1、有 5个元素，其入栈次序为 A,B,C,D,E，在各种可
能的出栈次序中，以元素 C,D最先出栈（即 C第一个且 D
第二个出栈）的次序有哪几个？
? 2、设计算法判断一个算术表达式的圆括号是否正确配对。
（提示：对表达式进行扫描，凡遇到“（”就进栈，遇到
“）”就退掉栈顶的“（”，表达式被扫描完毕，栈应为
空。）
