第三章 栈和队列

第三章栈和队列1栈和队列是重要的数据结构栈和队列是线性表的子集（是插入和删除受限的线性表）前言2【学习目标】

1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。

2.熟练掌握栈类型的两种实现方法。

3.熟练掌握循环队列和链队列的基本操作实现算法。

4.理解递归算法执行过程中栈的状态变化过程。

【重点和难点】

栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。

3【学习指南】

在这一章中，主要是学习如何在求解应用问题中适当地应用栈和队列，栈和队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。4【课前思考】

1.什么是线性结构？简单地说，线性结构是一个数据元素的序列。

2.你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,…,n的次序往上叠的,那么使用时候的次序应是什么样的？必然是依从上往下的次序，即n,…,2,1。它们遵循的是"后进先出"的规律，这正是本章要讨论的"栈"的结构特点。

3.在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？是"排队"。在计算机程序中，模拟排队的数据结构是"队列"。5栈必须按“后进先出”的规则进行操作队列必须按“先进先出”的规则进行操作和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构从“数据结构”的角度看:

它们都是线性结构，即数据元素之间的关系相同。

但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的"限定"。6通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。

线性表栈队列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栈和队列是两种常用的数据类型7

3.1

栈8

3.1.1栈的类型定义

栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。在表中，允许插入和删除的一端称作“栈顶(top)”，不允许插入和删除的一端称作“栈底(bottom)"。9通常称往栈顶插入元素的操作为"入栈"，称删除栈顶元素的操作为"出栈"。因为后入栈的元素先于先入栈的元素出栈，故被称为是一种"后进先出"的结构，因此又称LIFO（LastInFirstOut的缩写）表。很多书上都以如下图所示的铁路调度站形象地表示栈的这个特点。

10栈的类型定义

ADTStack{

数据对象：

D＝{ai|ai

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

数据关系：

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

约定an

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

}ADTStack11InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())12

InitStack(&S)

操作结果：构造一个空栈S。

DestroyStack(&S)

初始条件：栈S已存在。

操作结果：栈S被销毁。13StackEmpty(S)

初始条件：栈S已存在。

操作结果：若栈S为空栈，则返回

TRUE，否则FALSE。

判定栈是否为空栈是栈在应用程序

中经常使用的操作，通常以它作为循环结束的条件。14

StackLength(S)

初始条件：栈S已存在。

操作结果：返回S的元素个数，

即栈的长度。15GetTop(S,&e)

初始条件：栈S已存在且非空。

操作结果：用e返回S的栈顶元素,并

不将它从栈中删除。

a1a2an……e16ClearStack(&S)

初始条件：栈S已存在。

操作结果：将

S清为空栈。

17Push(&S,e)

初始条件：栈S已存在。

操作结果：插入元素e为新的栈

顶元素。

a1a2ane……18Pop(&S,&e)

初始条件：栈S已存在且非空。

操作结果：删除S的栈顶元素，

并用e返回其值。a1a2anan-1

……e19StackTraverse(S,visit())初始条件：栈S已存在且非空，visit()为元素的访问函数。

操作结果：从栈底到栈顶依次对S的每个元素调用函数visit()，一旦

visit()失败，则操作失败。

这是对栈进行从栈底到栈顶的“遍历”操作，应用较多的场合是，输出栈中所有数据元素。

20顺序栈3.1.2栈的表示和实现类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。//-----栈的顺序存储表示

-----#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;

typedef

struct{

SElemType*base;

SElemType*top;

int

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

StatusInitStack(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;}23

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;}24StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，

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

//否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}25在一个程序中同时使用两个栈：0M-1栈1底栈1顶栈2底栈2顶263.2栈的应用举例由于栈的操作具有后进先出的固有特性，致使栈成为程序设计中的有用工具。凡应用问题求解的过程具有"后进先出"的天然特性的话，则求解的算法中也必然需要利用"栈"。27栈的应用举例例一、数制转换例二、括号匹配的检验例三、行编辑程序问题例四、迷宫求解例五、表达式求值例六、实现递归28例一、数制转换

十进制数N和其他d进制数的转换是

计算机实现计算的基本问题，其解决方

法很多，其中一个简单算法基于下列原

理：

N=(Ndivd)×d+Nmodd

(其中：div为整除运算，mod为求余运算)29

NNdiv8Nmod8

13481684

168210

2125

202计算顺序输出顺序例如：（1348)10=(2504)8，

其运算过程如下：30voidconversion(){

InitStack(S);//构造空栈

scanf("%d",&N);//输入一个十进制数

while(N){Push(S,N%8);//"余数"入栈

N=N/8;

//非零"商"继续运算

}while(!StackEmpty(S)){

//和"求余"所得相逆的顺序输出八进制的各位数

Pop(S,&e);

printf("%d",e);}}//conversion31例二、括号匹配的检验假设在表达式中［］（））或［（［］［］）］等为正确的格式，［（］）或（［]（）或（（）））均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。32

即后出现的"左括弧"，它等待与其匹配的"右括弧"出现的"急迫"心情要比先出现的左括弧高。换句话说，对"左括弧"来说，后出现的比先出现的"优先"等待检验，对"右括弧"来说，每个出现的右括弧要去找在它之前"最后"出现的那个左括弧去匹配。显然，必须将先后出现的左括弧依次保存，为了反映这个优先程度，保存左括弧的结构用栈最合适。这样对出现的右括弧来说，只要"栈顶元素"相匹配即可。如果在栈顶的那个左括弧正好和它匹配，就可将它从栈顶删除。

33分析可能出现的不匹配的情况:到来的右括弧并非是所“期待”的；例如：考虑下列括号序列：

[([][])]12345678到来的是“不速之客”；直到结束，也没有到来所“期待”的括弧。34这三种情况对应到栈的操作即为：

1．和栈顶的左括弧不相匹配；

2．栈中并没有左括弧等在哪里；

3．栈中还有左括弧没有等到和它 相匹配的右括弧。35算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空

若栈空，则表明该“右括弧”多余，

否则和栈顶元素比较，

若相匹配，则“左括弧出栈”，

否则表明不匹配。3）表达式检验结束时，

若栈空，则表明表达式中匹配正确，

否则表明“左括弧”有余。36Statusmatching(charexp[]){

intstate=1;while(i<=Length(exp)&&state){switchexp[i]{case'('||'['

:{Push(S,exp[i]);i++;break;}case')'

:{if(！StackEmpty(S)&&GetTop(S)=‘(’

){Pop(S,e);i++;}else{state=0;}break;}case‘]'

:{if(！StackEmpty(S)&&GetTop(S)=‘['）

{Pop(S,e);i++;}else{state=0;}break;}}if(StackEmpty(S)&&state)returnOK;…...37例三、行编辑程序问题如何实现？“每接受一个字符即存入存储器”?并不恰当！38设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区,并假设“#”为退格符，“@”为退行符。在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。合理的作法是：39假设从终端接受了这样两行字符：

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

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

while(*s)

putchar(*s++);40可设这个输入缓冲区为一个栈结构，每当从终端接受了一个字符之后先作如下判断：

1、既不是退格也不是退行符，则将该字符压入栈顶；

2、如果是一个退格符，则从栈顶删去一个字符；

3、如果是一个退行符，则将字符栈清为空栈。41

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();}

ch=getchar();

ClearStack(S);//重置S为空栈

while(ch!=EOF){//EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；42例四、迷宫求解通常用的是“穷举求解”的方法43

为了保证在任何位置上都能沿原路退回,需要用一个“后进先出”的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后,栈中保存的正是一条从入口到出口的路径所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。

“纳入路径”的操作即为“当前位置入栈；

“从当前路径上删除前一通道块”的操作即为"出栈"。44迷宫路径算法的基本思想：若当前位置“可通”,则纳入路径，继续前进;若当前位置“不可通”,则后退,换方向继续探索;若四周“均无通路”,则将当前位置从路径中删除出去。45设定当前位置的初值为入口位置；

do｛

若当前位置可通，则｛将当前位置插入栈顶；

若该位置是出口位置，则算法结束；

否则切换当前位置的东邻方块为新的当前位置；

}

否则

{

若栈不空且栈顶位置尚有其他方向未被探索，求迷宫中一条从入口到出口的路径的算法：46

则设定新的当前位置为:沿顺时针方向转找到的栈顶位置的下一相邻块；

若栈不空但栈顶位置的四周均不可通，则{删去栈顶位置；//从路径中删去该通道块

若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；

}

}

}while(栈不空)；若栈空，则表明迷宫没有通路。47例五、表达式求值任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成。

操作数可以是常数也可以是被说明为变量或常量的标识符；

运算符可以分为算术运算符、关系运算符和逻辑运算符等三类；

基本界限符有左右括弧和表达式结束符等。48

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

Exp=S1OPS2

操作数:变量、常量、表达式运算符:算术运算符、关系运算符、逻辑运算符界限符：括号、结束符表达式求值49

表达式的三种标识方法：设Exp=S1+OP+S2则称OP+S1+S2为前缀表示法

S1+OP+S2为中缀表示法

S1+S2+OP为后缀表示法50算术四则运算的规则：先乘除，后加减从左算到右先括号内，后括号外运算符和界限符通称为算符。两个算符和之间的优先关系：，的优先权低于；，的优先权等于；，的优先权高于。51规则注意：＋、-、×、/为时，优先权均低于“（”，但均高于“）”；时，令，“#”是表达式的结束符；表中的“（”与“）”相遇时，括号内的运算完成；当“#”遇到“#”时，表达式求值完成当输入的运算符优先权高于栈顶运算符时，运算符入栈52中缀表达式求值基本算法思想：置操作数栈为空栈，表达式起始符“#”为运算符栈底元素；依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符栈则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即OPTR栈的的栈顶元素和当前读入的字符均为“#”）。定义两个工作栈：一个为OPTR，寄存运算符；一个为OPND，寄存操作数或运算结果。53例：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)54OperandType

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

}//whilereturnGetTop(OPND);}//EvaluateExpression……55switch(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;}//switch56

OPTR为运算符的集合，若ch是运算符，则函数IN(ch,OP)的值为“TRUE”。若c(栈顶运算符)的优先性高于栈顶运算符，则函数precede(GetTop（OPTR),c)值为“>"。……

算法的时间复杂度为O(n)，其中n为表达式字符串的长度。57

ADTQueue{

数据对象：

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

数据关系：

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

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

约定其中a1

端为队列头，an

端为队列尾基本操作：3.4队列的类型定义}

ADTQueue58队列的基本操作：

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

操作结果：构造一个空队列Q。

DestroyQueue(&Q)

初始条件：队列Q已存在。

操作结果：队列Q被销毁，不再存在。

60QueueEmpty(Q)

初始条件:队列Q已存在。

操作结果:若Q为空队列,则返回TRUE，

否则返回FALSE。QueueLength(Q)

初始条件:队列Q已存在。

操作结果:返回Q的元素个数，即队列

的长度。61

GetHead(Q,&e)

初始条件：Q为非空队列。

操作结果：用e返回Q的队头元素。a1a2an……62

ClearQueue(&Q)

初始条件：队列Q已存在。

操作结果：将Q清为空队列。63EnQueue(&Q,e)

初始条件:队列Q已存在。

操作结果:插入元素e为Q的新的队尾元素。a1a2ane……64

DeQueue(&Q,&e)

初始条件：Q为非空队列。

操作结果：删除Q的队头元素，并用e返

回其值。a1a2an……653.5队列类型的实现链队列——链式映象循环队列——顺序映象66

typedef

struct

QNode{//结点类型

QElemTypedata;

struct

QNode*next;}QNode,*QueuePtr;链队列——链式映象67typedef

struct{//链队列类型

QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针}LinkQueue;a1∧anQ.frontQ.rearQ.frontQ.rear∧空队列68

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

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);//存储分配失败

Q.front->next=NULL;returnOK;}69

StatusEnQueue(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;}70

StatusDeQueue(LinkQueue&Q,

QElemType&e){//若队列不空，则删除Q的队头元素，//用e返回其值，并返回OK；否则返回ERRORif(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;}71循环队列——顺序映象初始化建空队列时，令front=rear=0，每当插入一个新的队尾元素后，尾指针增1；每当删除一个队头元素之后，头指针front增1。因此，在非空队列中，头指针始终指向队头元素，而尾指针指向队尾元素的"下一个"位置。如下图所示。72实现：用一维数组实现sq[M]123450空队列rear=0front=0J1J2J3rearrear123450J4,J5,J6入队J4J5J6frontrearrear123450frontJ1,J1,J3入队rear123450J1,J2,J3出队J1J2J3frontfrontfront存在问题：当front=0,rear=M时再有元素入队发生溢出——真溢出当front≠0,rear=M时再有元素入队发生溢出——假溢出rear73解决方案队首固定，每次出队剩余元素向下移动——浪费时间循环队列基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;实现：利用“模”运算入队：base[rear]=x;rear=(rear+1)%M;出队：x=base[front];front=(front+1)%M;队满、队空判定条件74012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4,J5,J6出队J7,J8,J9入队队空：front==rear队满：front==rear解决方案：1.另外设一个标志位以区别队空、队满2.少用一个元素空间：队空：front==rear队满：(rear+1)%M==front3.使用一个计数器记录队列中元素的总数J5J6012345rearfront初始状态J475循环队列－队列的顺序表示和实现

#defineMAXQSIZE100//最大队列长度

typedef

struct{

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

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

//指向队列头元素

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

//队列尾元素的下一个位置}SqQueue;76

StatusInitQueue(SqQueue&Q){//构造一个空队列QQ.base=(QElemType*)malloc

(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);//存储分配失败

Q.front=Q.rear=0;returnOK;}第二种解决方案，占用一个元素空间77StatusEnQueue(SqQueue&Q,QElemTypee){//插入元素e为Q的新的队尾元素

if((Q.rear+1)%MAXQSIZE==Q.front)

returnERROR;//队列满

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}第二种解决方案，占用一个元素空间78

StatusDeQueue(SqQueue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，

//用e返回其值，并返回OK;否则返回//ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}第二种解决方案，占用一个元素空间79

#defineMAXQSIZE100//最大队列长度

typedef

struct{

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

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

//指向队列头元素

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

//队列尾元素的下一个位置}SqQueue;循环队列——顺序映象第一种解决方案：设标志

int

emptyflag;//队列空的标志，空为180

StatusInitQueue(SqQueue&Q){//构造一个空