数据结构课件第3章

第3章栈和队列内容

3.1栈

3.2栈的应用举例

3.3栈与递归的实现

3.4队列●基本要求：

１）理解栈和队列的概念，存储表示，进栈、退栈和进队、出队操作的算法；

２）对栈和队列的存储方式及基本操作有较深刻的理解；

３）初步了解栈的基本应用。如表达式的求值、递归的设计实现等。●学习重点：

１）栈和队列的基本操作；

２）栈在实现递归中的应用；●

两种重要的受限线性结构：栈和队列

从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集。它们是操作受限的线性表，即可称为限定性的数据结构。但从数据类型角度看，它们又是和线性表大不相同的两类重要的抽象数据类型。引言引言●

栈、队列和线性表三者的操作规则比较

返回目录

线性表：可以在表的任何位置上插入、删除元素。

栈：

对栈仅限定在表的一端（表尾）进行插入或删除操作。可以在表的任何位置上插入、删除元素。

队列：

限定在表的一端进行插入，而在另一端删除元素。

因此，从ADT的角度看，栈、队列和线性表是不相同的。3.1栈3.1.1抽象数据类型”栈”的定义

●定义：栈是限定仅在表的一端进行插入或删除操作的线性表。图3.1栈栈底栈顶出栈进栈a1a2an…在栈中能进行插入和删除的一端称为栈顶（top），相应地另一固定端称为栈底（bottom）。将一个元素放入栈中的操作叫做进栈或压栈，从栈顶取出一个元素的操作叫做出栈或弹出。不含元素的空表称为空栈。栈的存取操作符合后进先出（LastInFirstOut,LIFO）的原则，故栈又称为后进先出线性表，简称LIFO结构。3.1栈3.1.1抽象数据类型”栈”的定义

例3-1：A、B、C依次入栈，若不限出栈顺序，则出栈顺序有几种情况，请一一列出。图3.1栈栈底栈顶出栈进栈a1a2an…解：出栈顺序有5种可能的情况，分别为：ABC，ACB，BAC，BCA，CBACAB（加红色下划线的表示不可能）3.1栈3.1.1抽象数据类型”栈”的定义

例3-2：A、B、C、D依次入栈，若不限出栈顺序，则出栈顺序有几种情况，请一一列出。图3.1栈栈底栈顶出栈进栈a1a2an…解：出栈顺序有14种可能的情况，分别为：ABCD，ABDC，ACBD，ACDB，ADBC，ADCB，BACD，BADC，BCAD，BCDA，BDAC，BDCA，CABD，CADB，CBAD，CBDA，CDAB，CDBA，DABC，DACB，DBAC，DBCA，DCAB，DCBA。规律：按“大，小，中”顺序出栈是不可能的。3.1栈3.1.1抽象数据类型”栈”的定义

●推论：当n个编号元素依某种顺序压入，且可任意弹出时，所能获得的编号元素排列的数目为：例3-1，例3-2用此公式解答如下：其中n为输入序列长度即编号元素个数，Cn为可能的排列数目。3.1栈3.1.1抽象数据类型”栈”的定义

●栈的抽象数据类型的定义如下：ADTStack{

数据对象：D={ai|ai∈ElemSet，i=1,2,…,n,n>=1}

数据关系：R={<ai,ai+1>|ai,ai+1∈D,i=1,2,…,n}

基本操作：

InitStack(&S)；初始化操作生成一个空栈SDestroyStack(&S);释放栈

ClearStack(&S)；清空栈

Push(&S,x)；入栈操作

Pop(&S,&e)；出栈操作

GetTop(S,&e)；取栈顶元素函数

EmptyStack(&S)；置栈空操作

intStackLength(S);求当前栈中元素个数}3.1栈3.1.2

”栈”的表示和实现

●顺序栈——栈的顺序存储结构

用一维数组S(1:arrmax)表示栈。S(1:arrmax)S(1:arrmax)arrmaxarrmaxTop=0Top=非空栈空栈栈顶栈底图3.2栈顶指针和栈中元素的关系3.1栈3.1.2

”栈”的表示和实现

●顺序栈的ADT表示constintMAX_STACK=1000;structSqStkTp{ ElemTypeElement[MAX_STACK]; intTop;};//基本操作的算法描述（部分实现）InitStack(SqStkTp&s){s.top=0}//init_stackStatusisStackEmpty(SqStkTps){return(s.top==0)?True:False;}//empty_stack3.1栈3.1.2

”栈”的表示和实现

●顺序栈的ADT表示StatusPush(SqStkTp&s,ElemTpx){if(s.top==MAX_STACK)returnfalse;s.top++;s.elem[s.top]=x;returnTrue;}//push_stackElemTpPop(SqStkTp&s){if(s.top==0)return;s.top--;returns.elem[s.top+1]}//pop_stack3.1栈3.1.2

”栈”的表示和实现

●顺序栈的ADT表示ElemTpGetTop(SqStkTps){if(s.top==0)return;returns.elem[s.top]}//gettop_stackClearStack(SqStkTp&s){s.top=0}//clear_stack3.1栈3.1.2

”栈”的表示和实现

●链式栈——栈的链式存储结构设不带头结点，用单链表表示栈。图3.3链栈示意图ls栈空：ls==NULL;栈满：当内存分配无法实现时（堆区满）进栈：在表头插入;出栈：从表头删除;

数据结构的描述elemtype……//任何一种数据类型typedefstructtlkstktp{ElemTypeelem;tlkstktp*Next}*lkstktp;^datanext栈顶栈底…3.1栈3.1.2

”栈”的表示和实现

●链式栈的ADT表示(部分实现）PushStack(lkstktp&ls;elemtpx){//算法中p为结点类型指针变量

p=new(ElemType);p->elem=x;p->next=ls;ls=p}//push_stackelemtpPopStack(lkstktp&ls){//算法中p为结点类型指针变量

if(ls==NULL)returnNULL//pop为elemtp类型变量

p=ls;ls=p->next;pop=p->elem;free(p);returnpop;}//pop_stack

返回目录3.2栈的应用举例3.2.1行编辑程序

输入字符串。用“#”表示退格符，即它使前一个字符无效；用“@”表示退行符，以表示此前整行字符均无效。编写行输入处理过程，内设一个栈来逐行处理从终端输入的字符串。每次从终端接收一个字符后先作如下判别：如果它既不是退格符也不是退行符，则将该字符插入栈顶；如果是一个退格符，则从栈顶删去一个字符；如果它是一个退行符，就把字符域清为空栈。比如，若键入

BGE##EGIM#N RAD(A@READ(A);则实际有效的是下面两行

BEGINREAD(A);//设s为栈。本算法从终端接收一个正文文件并逐行传送至调用过程的数据VoidLine_Edit(){ InitStack(S); //构造空栈S

ch=getchar()； //从终端接收一个字符

while(ch!=EOF) //EOF为全文结束符

{while(ch!=EOF&&ch!=‘\n’){switch(ch){ case‘#’:Pop(s,c);break;

//若栈非空则退栈

case

‘@’:ClearStack(s);break;//将栈重新设置为空域

default:Push(s,ch);break;

//有效字符入栈

}；3.2栈的应用举例3.2.1行编辑程序

ch=getchar()//继续接收下一字符

}

将自栈底至栈顶的栈内字符作成一行,并传送至调用过程的数据区.ClearStack(s);//重置S为空栈

if(ch!=EOF)ch=getchar()//继续接收下一行（先接收下一行第一个字符）

}}//LineEdit3.2栈的应用举例3.2.1行编辑程序

●

讨论简单算术表达式的求值问题。3.2栈的应用举例3.2.2表达式求值

使用栈实现简单算术表达式的求值运算。依据算术四则运算的规则，在运算的每一步中。任何两个相继出现的算符θ1和θ2之间的优先关系，可能是

θ1<θ2θ1的优先数低于θ2θ1=θ2θ1的优先数等于θ2θ1>θ2θ1的优先数高于θ23.2栈的应用举例3.2.2表达式求值

表3.1算符间的优先关系3.2栈的应用举例3.2.2表达式求值

说明：

1）+、-、*和/为θ1时的优先性均低于“(”

，但高于“)”

；

2）当θ1=θ2

时，令θ1>θ2

;

3）

“(”

=“)”表示当左、右括号相遇时，括号内的运算已完成;

4）

“#”是表达式的结束符。设表达式的最左边也虚设一个#符，以构成整个表达式的一对“括号”，

5）

“(”与“#”，“)”与“(”以及“#”与“)”之间无优先关系，若出现此类情况，应是语法错误。下面的讨论，假定不会出现语法错误；

6）

“#”=“#”表示整个表达式求值完毕。3.2栈的应用举例3.2.2表达式求值

operandtypeEvaluateExpression(){/*算术表达式求值的算符优先算法。假定从终端输入的表达式无语法错误，以‘#’作结束符。设OPTR和OPND分别为运算符栈和操作数栈，OP为运算符的集合*/InitStack(OPTR)；//初始化运算符栈

Push(OPTR，‘#‘)；//在运算符栈的栈底压入表达式左端的虚设字符#InitStack(OPND)；//初始化操作数栈

c=getchar()；

//从终端接收一个字符

while((c!=‘#’)||(GetTop(OPTR)!='#'))

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

else3.2栈的应用举例3.2.2表达式求值

switch(precede(GetTop(OPTR),c)){//比较优先级

case‘<’://栈顶元素优先权低，运算符入栈

Push(OPTR,c);c=getchar();break;case‘=’://左括号遇右括号，脱括号并接收下一字符

x=pop(OPTR);c=getchar();break;case‘>’:/*运算符及两个操作数分别退栈，结果入栈*/theta=Pop(OPTR);b=Pop(OPND);a=pop(OPND);Push(OPND,operate(a,theta,b));break;}}

//CASEWHILEreturn(GetTop(OPND)){返回最终结果值}}

//EvaluateExpression3.2栈的应用举例3.2.2表达式求值

例3-3：利用算法EvaluateExpression对算术表达式3*(7-2)求值。其操作过程如表3.2所示：表3.2

3*(7-2)求值的操作过程

返回目录3.3栈与递归的实现●

递归的概念

栈还有一个重要应用是在程序设计中实现递归。一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。3.3栈与递归的实现●

递归函数的3个示例

例3-4：阶乘函数非递归形式递归形式用类C写求阶乘函数intfact(intn){if(n<0)ERROR(‘n应大于0’);elseif(n==0)return1;

//递归出口

elsereturn(n*fact(n-1));}//fact注：递归函数必须有递归终结分支（递归出口）！3.3栈与递归的实现●

递归函数的3个示例

写出Fibonacci数列递归函数：

intfib(intn)

{switch(n){

casen<0:ERROR(‘n应大于0’)；break;

casen=0:return(0)；break;

//递归出口

casen=1:return(1)；break;//递归出口

default:

return(fib(n-1)+fib(n-2));

}}//switch//fib

例3-5：斐波那契(Fibonacci)数列非递归形式递归形式3.3栈与递归的实现●

递归函数的3个示例

圆盘移动规则

1）每次只能移动一个圆盘；

2）圆盘可以插在X，Y和Z中的任一塔座上；

3）任何时刻都不能将一个较大的圆盘压在较小的圆盘上。例3-6：n阶Hanoi塔问题(p55)XYZXYZ初始结果图3.4

3阶Hanoi塔问题的初始与结果状态3.3栈与递归的实现●

递归函数的3个示例

(1)从X移动1~n-1号圆盘至Y，Z作辅助；(递归)[分析]此问题可归之于三个子问题

(2)从X移动n号圆盘至Z；(一次搬运)

(3)从Y移动1~n-1号圆盘至Z，X作辅助。(递归)1~nn1~n-11~n-1n1~n-1nXYZXYZXYZXYZ图3.53.3栈与递归的实现●

递归函数的3个示例

Voidhanoi(intn,charx,chary,charz)//将塔座x上编号从1至n、直径依小至大的n个圆盘移到塔座Z上，y可用作辅助塔座1{2if(n==1)3move(x,1,z);//将编号为1的圆盘从x移到z4elseif(n>1){5hanoi(n-1,x,z,y);//将x上编号从1至n-1的圆盘移到y上，z为辅助塔座6move(x,n,z);//将编号为n的圆盘从x移到z7hanoi(n-1,y,x,z);

//将y上编号从1至n-1的圆盘移到z上，x为辅助塔座8}9}//hanoi[解答]求解n阶Hanoi塔问题的递归算法。

返回目录3.4队列3.4.1

抽象数据类型“队列”的定义队列是限定仅能在表的一端进行插入，在表的另一端进行删除的线性表。在队列中可以插入的一端称为队尾(rear)，可以删除的一端称为队头或队首(front)。将一个元素插到队列中的操作叫做入队列或进队，从队列中删除一个元素的操作叫做出队列或出队。队列是一种先进先出(FirstInFirstOut,FIFO)的线性表，或简称队列是一种FIFO结构。●队列的定义a1a2a3•••

an出队列入队列队头队尾图3.6队列示意图3.4队列3.4.1

抽象数据类型“队列”的定义●队列的ADT定义ADTQueue{

数据对象：D={ai|ai∈ElemSet，i=1,2,…,n,n>=1}

数据关系：R={<ai,ai+1>|ai,ai+1∈D,i=1,2,…,n}

基本操作：

InitQueue(&Q)；初始化构造一个空队列QDestroyQueue(&Q);释放队列QClearQueue(&Q)；将Q清为空队列

EnQueue(&Q,x)；入队列操作

DeQueue(&Q,&e)；出队列操作

GetTop(S,&e)；取栈顶元素函数

QueueEmpty(&S)；判断栈是否为空

QueueLength(Q);求当前队列Q中元素个数}3.4队列3.4.2

链队列——队列的链式表示和实现●链队列：用链表表示的队列。链队列应包含两个指针：队头指针、队尾指针。

为了操作方便，给链队列附加一个头节点。^···^q.frontq.rear

队头指针q.front队尾指针q.front附加头结点队头队尾空链队列：图3.7链队列示意图3.4队列3.4.2

链队列——队列的链式表示和实现●链队列的表示structqueuenode{elemtpdata;queuenode*next;};^···队头指针q.front队尾指针q.front附加头结点队头队尾图3.8链队列示意图structlinkedqueue{queuenode*front;queuenode*rear;};3.4队列3.4.2

链队列——队列的链式表示和实现●链队列的实现init_linkedque(linkedqueue&q){

//构造一个空链队列

q.front=new(queuenode);//建链队列结点

q.rear=q.front;q.front->next=NULL;}//init_linkedque图3.9链队列初始化q.front^q.rear3.4队列3.4.2

链队列——队列的链式表示和实现●链队列的实现en_linkedque(linkedqueue&q,elemtpx){

//插入元素X为Q的新的队尾元素

queueptrp;p=new(queuenode);p->data=x;p->next=NULL;//建新尾结点

q.rear->next=p;q.rear=p;//插入队尾}//en_linkedque图3.10建立一个新结点（值为x），并插入链队列队尾x^q.frontq.rearp3.4队列3.4.2

链队列——队列的链式表示和实现●链队列的实现图3.11建立一个新结点（值为y），并插入链队列队尾y^q.frontq.rearxy^q.frontq.rearxS图3.12将队头结点（值为x）删除（出队列）3.4队列3.4.2

链队列——队列的链式表示和实现●链队列的实现Statusdl_linkedque(linkedqueue&q,elemtp&e){

//若队列不空，则删除Q的队头元素，用e返回其值

queueptrs;elemtpx;if(q.front==q.rear)returnfalse;//队列为空

s=q.front->next;q.front->next=s->next;//删除链队列的队头元素

if(!s->next)q.rear=q.front;//若删除后队列为空则修改尾指针

x=s->data;delete(s);//回收无用结点e=x;returnOK;//返回该元素}//dl_linkedque3.4队列3.4.3

循环队列——队列的顺序表示和实现●循环队列：用数组表示的队列

用数组实现队列：定义一个数组和分别指向队头元素和队尾元素的游标。

约定：尾指针指示队尾元素在队列中的下一个位置，头指针指示队列中队头元素的当前位置。数据结构描述：structsequeuetp{

elemtpelem[maxsize];

int

front,rear;

}

sequeuetpsq;3.4队列3.4.3

循环队列——队列的顺序表示和实现●循环队列：用数组表示的队列543210Sq.rearSq.frontSq.rearSq.frontSq.rearSq.frontSq.rearSq.frontJ1J2J3J4J4J5J6(a)(b)(c)(d)图3.13头、尾指针和队列中元素之间的关系(a)空队列；(b)J1，J2，J3，J4相继入队列；

(c)J1，J2，J3相继出队列；(d)J4出队，J5，J6入队列(加满)。3.4队列3.4.3

循环队列——队列的顺序表示和实现●循环队列：用数组表示的队列由图3.13可以看出：队空：sq.front==sq.rear队满：sq.rear==maxsize//可能是假溢出入队：sq.elem[sq.rear]=x；//x入队列

sq.rear++；//修改尾指针出队：sq.front++；//修改头指针3.4队列3.4.3

循环队列——队列的顺序表示和实现●循环队列：用数组表示的队列由图3.13(d)的假满状态可以看出时，不可再继续向队列插入新的队尾元素，但队列的实际可用空间并未占满。一个较巧妙的办法是将顺序队列构造为一个环状的空间。如图3.14所示，称之为循环队列。Q.frontQ.rear图3.14循环队列示意图3.4队列3.4.3

循环队列——队列的顺序表示和实现●循环队列：用数组表示的队列入队：cq.elem[cq.rear]=x；cq.rear=(cq.rear+1)%maxsize；出队：cq.front=(cq.front+1)%maxsize；图3.15循环队列的头尾指针（a）一般情况501243cq.frontcq.rearJ4J5J3（b）队列满时501243cq.frontcq.rearJ4J5J6J7J8J3(a)=>(b)（c）空队列501243cq.frontcq.rear(a)=>(c)3.4队列3.4.3

循环队列——队列的顺序表示和实现●循环队列：用数组表示的队列由图3.15可以看出：图3.15（b）队满：sq.front==sq.rear图3.15（c）队空：sq.front==sq.rear由此可见，只凭等式sq.front==sq.rear无法判别队列空间是队满？还是队空？区分队满与队空的解决方法：

1）另设一标志位记录队列的状态；

2）少用一个元素的空间（如图3.16所示）。3.4队列3.4.3

循环队列——队列的顺序表示和实现●循环队列：用数组表示的队列队满：cq.front==(cq.