数据结构(清华)第三章 栈和队列

通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,

i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n栈和队列是两种常用的数据类型第三章栈和队列3.1栈3.2栈的应用举例3.4队列3.3栈与递归的实现学习提要：1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。4.理解递归算法执行过程中栈的状态变化过程。重难点内容：顺序栈的相关操作、循环队列的判空判满3.1栈（stack）3.1.1

栈的类型定义3.1.2

栈的表示和实现

栈的定义：限定仅在表尾进行插入或删除操作的线性表。不含元素的空表称空栈。ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)特点：后进先出（LIFO）3.1.1栈的类型定义表尾—栈顶

表头—栈底

ADTStack

{

数据对象：

D＝{ai|ai

∈ElemSet,i=1,2,...,n,n≥0}

数据关系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

约定an

端为栈顶，a1端为栈底。基本操作：

}ADTStack栈的抽象数据类型定义：InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())一、顺序栈3.1.2栈的表示和实现//-----栈的顺序存储表示

-----

#defineSTACK_INIT_SIZE100;

#defineSTACKINCREMENT10;

typedef

struct{

SElemType

*base;//栈底指针

SElemType

*top;//栈顶指针

int

stacksize;

}

SqStack;实现：一维数组s[M]top123450进栈Push(&S,e)A栈满BCDEF设数组维数为Mtop=base,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450空栈topbasebasetoptop出栈Pop(&S,&e)123450ABCDEFtoptoptoptop栈空basetoptop栈底指针base,始终指向栈底位置；栈顶指针top,其初值指向栈底，始终在栈顶元素的下一个位置

Status

InitStack(SqStack

&S){

//构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZE*

sizeof(SElemType));

if(!S.base)exit(OVERFLOW);//存储分配失败

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;}

StatusPush(SqStack

&S,SElemTypee)

{if(S.top-S.base>=

S.stacksize){

//栈满，追加存储空间

S.base=(SElemType*)realloc

(S.base,(S.stacksize+STACKINCREMENT)*

sizeof

(SElemType));

if(!S.base)exit(OVERFLOW);//存储分配失败

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;}

*S.top++=e;

returnOK;

}StatusPop(SqStack

&S,SElemType

&e){//若栈不空，则删除S的栈顶元素，

//用e返回其值，并返回OK；

//否则返回ERROR

if

(S.top

==

S.base)

returnERROR;

e=*--S.top;

returnOK;}0M-1栈1底栈1顶栈2底栈2顶在一个程序中同时使用两个栈二、链栈栈的链式存储结构。

栈顶指针就是链表的头指针。注意:链栈中指针的方向栈顶指针∧a1anan-1入栈操作push(&S,e)出栈操作pop(&S,&e)^…...栈底toptopxptop^…...栈底topqp->next=top;top=p

q=top;top=top->next

3.2栈的应用3.2.1数制转换3.2.2括号匹配的检验3.2.3行编辑程序问题3.2.4迷宫求解3.2.5表达式求值3.2.1数制转换十进制N和其他d进制数的转换原理:

N=(Ndivd)*d+Nmodd

其中：div为整除运算，

mod为求余运算toptop4top40top405

例如：

(1348)10=(2504)8，其运算过程如下：

NNdiv8Nmod8134816841682102125202计算顺序输出顺序top4052

voidconversion(){

//对于输入的任意一个非负十进制整数，

//打印输出与其等值的八进制数

initstack(S);

scanf(“%d”,N);

while(N){

push(S，N%8);N=N/8;}

while(!Stackempty(s)){

pop(S,e);

printf

(“%d”,e);}}//conversion3.3.2括号匹配的检验则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。假设在表达式中（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或（（）］)均为不正确的格式。分析可能出现的不匹配的情况:到来的右括弧并非是所“期待”的；例如：考虑下列括号序列：

[([][])]12345678到来的是“不速之客”；直到结束，也没有到来所“期待”的括弧。算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。3.2.3行编辑程序问题如何实现？“每接受一个字符即存入存储器”?

不恰当!合理的作法是：设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“@”为退行符。假设从终端接受了这样两行字符：

whli##ilr#e（s#*s)

outcha@putchar(*s=#++);则实际有效的是下列两行：

while(*s)

putchar(*s++);

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为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；3.2.4迷宫求解通常用的是“穷举求解”的方法。求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。设定当前位置的初值为入口位置；

do｛

若当前位置可通，

则｛将当前位置插入栈顶；

若该位置是出口位置，则算法结束；否则切换当前位置的东邻方块为新的当前位置；

｝

否则{

｝｝while(栈不空）；求迷宫中一条从入口到出口的路径的算法：……若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则｛删去栈顶位置；//从路径中删去该通道块

若栈不空，则重新测试新的栈顶位置，

直至找到一个可通的相邻块或出栈至栈空；｝若栈空，则表明迷宫没有通路。

typedef

struct{

int

ord;//通道块在路径上的“序号”

PosTypeseat;//通道块在迷宫中的“坐标位置”

int

di;//从此通道块走向下一通道块的“方向”}SElemType;//栈的元素类型

Status

MazePath(MazeTypemaze,PosTypestart,

PosTypeend){

InitStack(S);

curpos=start;

//设定“当前位置”为“入口位置”

curstep=1;//探索第一步

do{

if(Pass(curpos)){//当前位置可以通过，即是未曾走到过的通道块

}

else{}}while(!StackEmpty(S));return(FALSE);}//MazePath

…………FootPrint(curpos);e=(curstep,curpos,1);Push(S,e);//加入路径if(curpos==end)return(TRUE);

//到达终点curpos=NextPos(curpos,1);

//下一位置是当前位置的东邻curstep++;

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(curpos,e.di);

//设定当前位置是该新方向上的相邻块

}//if}//if}//else

限于二元运算符的表达式定义:

Exp=S1OP

S2

操作数:

变量、常量、表达式

运算符:

算术运算符、关系运算符、

逻辑运算符

界限符：括号、结束符3.2.5表达式求值表达式求值的算法：算符优先法根据运算优先关系的规定来实现对表达式的编译或解释执行。例：3*(7–2)OPND栈OPTR栈＃＃CCC3*(C7C－C2C－275C*5315例：3*(7–2)

OPTR栈OPND栈输入操作1# 3*(7–2)#PUSH(OPND,‘3’)2#

3*(7–2)#PUSH(OPTR,‘*’)3#*3(7–2)#PUSH(OPTR,‘(’)4#*(37–2)#PUSH(OPND,‘7’)5#*(37–2)#PUSH(OPTR,‘–’)6#*(–372)#PHSH(OPND,‘2’)7#*(–372)#operate(‘7’,’-’,’2’)8#*(35)#POP(OPTR)9#*35#operate(‘3’,‘*’,‘5’)10#15#returnGetTop(OPND)OperandType

EvaluateExpression(){

//设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。

InitStack(OPTR);Push(OPTR,'#');

initStack(OPND);c=getchar();

while(c!='#'||

GetTop(OPTR)!='#')

{

if(!In(c,OP)){Push((OPND,c);c=getchar();}

//不是运算符则进栈

else}//while

return

GetTop(OPND);}//EvaluateExpression……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;

}//switchr主程序srrrs子过程1rst子过程2rst子过程33.3栈与递归的实现当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事:(1)将所有的实在参数、返回地址等信息传递给被调用函数保存;(2)为被调用函数的局部变量分配存储区;(3)将控制转移到被调用函数的入口。

从被调用函数返回调用函数之前，应该完成:(1)保存被调函数的计算结果;(2)释放被调函数的数据区;(3)依照被调函数保存的返回地址将控制转移到调用函数。多个函数嵌套调用的规则是：后调用先返回此时的内存管理实行“栈式管理”。递归过程指向过程中占用的数据区，

称之为递归工作栈每一层的递归参数合成一个记录，

称之为递归工作记录栈顶记录指示当前层的执行情况，

称之为当前活动记录栈顶指针，

称之为当前环境指针例：递归的执行情况分析voidprint(intw){inti;if(w!=0){print(w-1);for(i=1;i<=w;++i)

printf(“%3d,”,w);

printf(“/n”);}}运行结果：1，2，2，3，3，3，递归调用执行情况如下：主程序(1)print(w)w=3;3print(2);（1）w=3top(2)输出：3,3,3w2print(1);（2）w=2（1）w=3top(3)输出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)输出：1w0（4）w=0（3）w=1（2）w=2（1）w=3topw(3)输出：2,2(2)2(1)3top(4)输出：1(3)1(2)2(1)3top(2)输出：3,3,3(1)3top返回(3)1(2)2(1)3top(4)0结束(1)例：n阶Hanoi问题。问题描述：有X,Y,Z三个塔座，X上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔，编号1,2,3……n。要求将n个圆盘从X移到Z，叠放顺序不变，移动过程中遵循下列原则：(1)每次只能移一个圆盘;(2)圆盘可在三个塔座上任意移动;(3)任何时刻都不能将大盘压到小盘上;解决方法：n=1时，直接把圆盘从X移到Z；n>1时，先把上面n-1个圆盘从X移到Y，然后将n号盘从X移到Z，再将n-1个盘从Y移到Z。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题。voidhanoi(intn,charx,chary,charz)

//将塔座x上按直径由小到大且至上而下编号为1至n

//的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1{2if(n==1)3move(x,1,z);//将编号为１的圆盘从x移到z4else{5hanoi(n-1,x,z,y);//将x上编号为１至n-1的圆

//盘移到y,z作辅助塔6move(x,n,z);//将编号为n的圆盘从x移到z

hanoi(n-1,y,x,z);//将y上编号为１至n-1的圆

//盘移到z,x作辅助塔8}9}执行情况：

递归工作栈保存内容：形参n,x,y,z和返回地址（返回地址用语句行号表示）。

工作记录结构：返回地址nxyz

voidhanoi(intn,charx,chary,charz)1{2if(n==1)3move(x,1,z);4else{5hanoi(n-1,x,z,y);6move(x,n,z);7hanoi(n-1,y,x,z);8}9}abc1230

3abc0

3abc6

2acb0

3abc6

2acb6

1abcabc0

3abc6

2acbabc0

3abc6

2acb8

1cababc0

3abc0

3abc6

2acb

voidhanoi(intn,charx,chary,charz)1{2if(n==1)3move(x,1,z);4else{5hanoi(n-1,x,z,y);6move(x,n,z);7hanoi(n-1,y,x,z);8}9}abc0

3abc6

2acbabc0

3abc8

2bac0

3abc8

2bac6

1bcaabc0

3abc

voidhanoi(intn,charx,chary,charz)1{2if(n==1)3move(x,1,z);4else{5hanoi(n-1,x,z,y);6move(x,n,z);7hanoi(n-1,y,x,z);8}9}0

3abc8

2bac

voidhanoi(intn,charx,chary,charz)1{2if(n==1)3move(x,1,z);4else{5hanoi(n-1,x,z,y);6move(x,n,z);7hanoi(n-1,y,x,z);8}9}abc0

3abc8

2bac8

1abcabc0

3abc栈空0

3abc8

2bac0

3abc8

2bac3.4队列3.4.1

队列的类型定义3.4.2

链队列3.4.3

循环队列队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。a1a2a3…….an入队出队frontrear队列Q=(a1,a2,……,an)队列特点：先进先出(FIFO)3.4.1

队列的类型定义队尾(rear)——允许插入的一端队头(front)——允许删除的一端

ADTQueue{

数据对象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：

R1＝{<ai-1,ai>|ai-1,ai

∈D,i=2,...,n}

约定其中a1

端为队列头，an

端为队列尾基本操作：队列的抽象数据类型定义：}

ADTQueue队列的基本操作：

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit())typedef

struct

QNode{//结点类型

QElemTypedata;

struct

QNode*next;

}QNode,*QueuePtr;typedef

struct{//链队列类型

QueuePtr*front;

//队头指针

QueuePtr*rear;//队尾指针}LinkQueue;3.4.2链队列－队列的链式表示和实现a1∧an…Q.frontQ.rearQ.frontQ.rear∧空队列

Status

InitQueue(LinkQueue&Q){//构造一个空队列Q

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)exit(OVERFLOW);//存储分配失败

Q.front->next=NULL;

returnOK;}

Status

EnQueue(LinkQueue

&Q,

QElemTypee){//插入元素e为Q的新的队尾元素

p=(QueuePtr)malloc(sizeof

(QNode));

if(!p)exit(OVERFLOW);//存储分配失败

p->data=e;p->next=NULL;

Q.rear->next=p;Q.rear=p;

returnOK;}

Status

DeQueue(LinkQueue

&Q,

QElemType

&e){

//若队列不空，则删除Q的队头元素，

//用e返回其值，并返回OK；否则返回ERROR

if(Q.front==Q.rear)returnERROR;

p=Q.front->next;e=p->data;Q.front->next=p->next;

if(Q.rear==p)Q.rear=Q.front;

free(p);

returnOK;}3.4.3

循环队列－队列的顺序表示和实现

#defineMAXQSIZE100//最大队列长度

typedef

struct{

QElemType

*base;//动态分配存储空间

intfront;//头指针，若队列不空，

//指向队列头元素

intrear;//尾指针，若队列不空，指向

//队列尾元素的下一个位置

}

SqQueue;实现：用一维数组实现base[M]123450空队列rear=0front=0J1J2J3rearrear123450J4,J5,J6入队J4J5J6frontrearrear123450frontJ1,J2,J3入队rear123450J1,J2,J3出队J1J2J3frontfrontfrontfront存在问题：当front=0,rear=M时，再有元素入队发生溢出——真溢出当front≠0,rear=M时，再有元素入队发生溢出——假溢出解决方案队首固定，每次出队剩余元素向下移动——浪费时间循环队列基本思想：把队列设想成环形，让base[0]接在base[M-1]之后，若rear+1==M,则令rear=0;实现：利用“模”运算入队：base[rear]=e;rear=(rear+1)%M;出队：e