数据结构 第三章 栈和队列

13.1栈（Stack）第三章栈和队列1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式23.2队列（Queue）第三章栈和队列1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式3数据结构课程的内容41.定义3.1栈与线性表相同，仍为一对一(1:1)关系。用顺序栈或链栈存储均可，但以顺序栈更常见3.存储结构2.逻辑结构限定只能在表的一端进行插入和删除运算的线性表。即栈顶53.1栈只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。4.运算规则5.实现方式

基本操作有：建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。6栈是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶

/top;表头(即a1端)称为栈底/base例如：栈S=(a1,a2,a3,……….,an-1,an

)插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。an称为栈顶元素a1称为栈底元素想一想：要从栈中取出a1，应当如何操作？强调：插入和删除都只能在表的一端（栈顶）进行！1、栈是一种特殊的线性表7Q1：堆栈是什么？它与一般线性表有什么不同？

堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。一般线性表堆栈逻辑结构：1:1逻辑结构：1:1存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取运算规则：后进先出(LIFO)“进”＝插入=压入=PUSH（an+1)“出”＝删除=弹出=POP(an)8a1a2……an顺序栈Sai……Q2：顺序表和顺序栈的操作有何区别？表头表尾低地址高地址写入：S[i]=ai读出：e=S[i]压入(PUSH):S[top++]=an+1弹出(POP):e=S[--top]低地址高地址S[i]a1a2aian……顺序表S……an+1以线性表

S=(a1,a2,….,an-1,an)为例栈底base栈顶top前提：一定要预设栈顶指针top栈顶top9栈不存在的条件：base=NULL;栈为空的条件：base=top;栈满的条件：top-base=stacksize;a1a2……an顺序栈Sai……低地址高地址栈底base栈顶topQ2：顺序表和顺序栈的操作有何区别？10若入栈动作使地址向高端增长，称为“向上生成”的栈；若入栈动作使地址向低端增长，称为“向下生成”的栈；

对于向上生成的堆栈:入栈口诀：堆栈指针top“先压后加”:S[top++]=an+1出栈口诀：堆栈指针top“先减后弹”:e=S[--top]Q3：什么叫“向上生成”的栈？“向下生成”又是何意？11Q4：为什么要设计堆栈？它有什么独特用途？调用函数或子程序非它莫属；递归运算的有力工具；用于保护现场和恢复现场；简化了程序设计的问题。下面用4个例子来帮助理解堆栈：12voidtest(int&sum){①intx;②scanf(x);if(x==0)③sum=0;else{④test(sum);⑤sum+=x;}⑥printf(sum);⑦}断点地址入栈例1

阅读下列递归过程，说明其功能。输入x1≠0输入x5＝0输入x2输入x3输入x4输出sum＝0输出sum＝0+x4输出sum＝x4+x3输出sum＝x4+x3+x2输出sum＝x4+x3+x2+x1注意：最先输入的数据x1

最后才被累加程序功能：对键盘输入数据求和，直到输入0结束2、堆栈举例13答：可以通过穷举所有可能性来求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入，3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合计有5种可能性。例2

一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？14例3：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？答：43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，每压入一数便立即弹出即可。思考：有无通用的判别原则？2、堆栈举例15例4：设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：

Ａ）a，b，c，dＢ）c，d，a，b

Ｃ）b，c，d，aＤ）a，c，d，bA）、D）可以，

B）、C）不行。讨论：有无通用的判别原则？有！若输入序列是…,Pi…Pj…Pk…(i<j<k,输入序号)，一定不存在这样的输出序列

…,Pk…Pi…Pj…答：即对于输入序列1，2，3，不存在输出序列3，1，22、堆栈举例16栈的抽象数据类型定义:(教材P44-45）ADTStack{数据对象：D=……数据关系：R=……基本操作：……}ADTStack入栈、出栈、建栈初始化、判断栈满或栈空、读栈顶元素值等。本节重点：顺序栈和链栈的基本操作17

#defineSTACK-INIT-SIZE100

//存储空间初始分配量

#defineSTACKINCREMENT10

//存储空间分配增量

typedefstruct{

SElemType*base;

//栈的基址即栈底指针

SElemType*top;

//栈顶指针

intstacksize;

//当前分配的空间

}SqStack;SqStacks;动态数组3、顺序栈的存储表示（教材P46)

18顺序栈的入栈操作——例如用堆栈存放（A，B，C，D）AACBABAtop核心语句：top=L;

顺序栈入栈函数PUSH（）见教材Push(B);Push(C);Push(D);toptoptoptop低地址LPush(A);高地址MBCD19顺序栈出栈操作——例如从栈中取出‘B’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心语句：Pop();顺序栈出栈函数POP()见教材Pop();Printf(Pop());20链栈的入栈操作和出栈操作（教材省略）(1)链栈的构造方式——以头指针为栈顶，在头指针处插入或删除.Node*st,*p;intm=sizeof(Node);栈顶栈底栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈sta1a2an-1annextdata链栈中每个结点由两个域构成：data域和next域，其定义为：typedefStructSNode{SElemTypedata;StructSNode*next;}Node;21Push(SElemTypee){p=(Node*)malloc(m);if(!p){上溢}else{p->data=e;p->link=st;st=p;}}StatusPop(){if(st==NULL){下溢}else{e=st->data;p=st;st=st->link; free(p);return(e);}}链栈入栈函数（包括建栈）链栈出栈函数插入表头从表头删除(2)入、出栈操作由此可以看出：一个链栈由其栈顶指针唯一指定设st指向栈顶元素，则st=NULL表示栈空22链栈不必设头结点，因为栈顶（表头）操作频繁；链栈一般不会出现栈满情况，除非没有空间导致malloc分配失败。链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成。采用链栈存储方式的优点是，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。几点说明:23例1：数制转换（十转N）——见教材设计思路：用栈暂存低位值例2：括号匹配的检验————见教材设计思路：用栈暂存左括号例3

：表达式求值—-————见教材设计思路：用栈暂存运算符例4：汉诺（Hanoi）塔-———见教材设计思路：用栈实现递归调用4、栈的应用举例24例3

表达式求值(这是栈应用的典型例子)

这里，表达式求值的算法是

“算符优先法”。例如：编写算法，用栈实现表达式3*（7–2）求值。一个算术表达式是由操作数（x，y，z…）和算符（*，/，+，-，（，），#）组成.表达式的起止符号栈的应用举例25例3

表达式求值(这是栈应用的典型例子)

这里，表达式求值的算法是

“算符优先法”。教材表3.1给出了算符之间的优先级专为计算机处理而设计的表!(1)

表达式求值必须满足算术四则运算规则：

a.从左算到右

b.先乘除，后加减

c.先括号内，后括号外栈的应用举例为了实现算符优先算法，可以设定两个工作栈，OPND—存放操作数或运算结果，OPTR—存放运算符号。26(2)算法思想1）首先置操作数栈OPND为空栈，表达式的起始符#为运算符栈OPTR的栈底元素2）依次读入表达式中的每个字符，若运算符是‘#’或栈顶是‘#’，结束计算，返回OPND栈顶值。

if（是操作数）→则PUSH（OPND，操作数）；

if（是运算符）→则与OPTR栈顶元素进行比较，按优先级(规定详见表3.1）进行操作；if栈顶元素<输入算符，则算符压入OPTR栈，并接收下一字符

if栈顶元素=运算符但≠‘#’，则脱括号(弹出左括号)并收下一字；if栈顶元素>运算符，则退栈、按栈顶计算，将结果压入OPND栈。且该未入栈的运算符要保留，继续与下一个栈顶元素比较！栈的应用举例273）直到整个表达式求值完毕（当前读入的字符和OPTR栈的栈顶元素均为#

）

(2)算法思想栈的应用举例28问：教材表3.1中，1和2哪个对应栈顶元素，哪个对应键盘输入值？答：根据Precede()函数可知，1对应栈顶元素由表3.1可看出，右括号)

和井号

#作为2时级别最低；由c规则得出：*，/，+，-为1时的优先权低于‘（’，高于‘）’由a规则得出：‘（’=‘）’表明括号内的运算已完成；‘#’=‘#’表明表达式求值完毕。附：栈的应用举例29表达式求值过程的描述：OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,’3’)

#*(7-2)#3#Push(optr,’*’)#,*3(7-2)#Push(optr,’(’)#,*,(37-2)#Push(opnd,’7’)#,*,(3,7-2)#Push(optr,’-’)#,*,(,－3,72)#Push(opnd,’2’)#,*,(,－3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)3*（7–2）30StatusEvaluateExpression(OperandType&result){InitStack(OPND);InitStack(OPTR);Push(OPTR,’#’);c=getchar();while((c!=‘#’)&&(GetTop(OPTR)!=‘#’)){if(!In(c,OP){Push(OPND,c);c=getchar();}elseswitch(precede(GetTop(OPTR),c)){case‘<’:Push(OPTR,c);c=getchar();break;case‘=’:Pop(OPTR);c=getchar();break;

case‘>’:Pop(OPTR,theta);Pop(OPND,b);a=Pop();Push(OPND,Operate(a,theta,b));break;;}//switch}//while

result=GetTop(OPND);}//EvaluateExpressionOperate=abC是操作符吗？运算符与栈顶比较并查3.1表程序清单递归算法的设计步骤第一步骤（递归步骤）：将规模较大的原问题分解为一个或多个规模更小、但具有类似于原问题特性的子问题。即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题。第二步骤：确定一个或多个无须分解、可直接求解的最小子问题（称为递归的终止条件）。【例】非负整数n的阶乘可递归定义为：31

32传说在创世纪时，在一个叫Brahma的寺庙里，有三个柱子，其中一柱上有64个盘子从小到大依次叠放，僧侣的工作是将这64个盘子从一根柱子移到另一个柱子上。xyznn–1移动时的规则：每次只能移动一个盘子；只能小盘子在大盘子上面；可以使用任一柱子。当工作做完之后，就标志着世界末日到来。例4汉诺（Hanoi）塔33分析：设三根柱子分别为x,y,z,盘子在x柱上，要移到z柱上。1、当n=1时，盘子直接从x柱移到z柱上；2、当n>1

时,则:①

设法将前n–1个盘子从x移到y柱上（借助z），则盘子n就能从x移到z柱上；②再设法把n–1个盘子从y移到z柱上(这又是一个与原来相同的问题，只是规模少１了）。xyznn–1例4汉诺（Hanoi）塔34VoidHanoi(intn,charx,chary,charz){//将n个编号从上到下为1…n的盘子从x柱，借助y柱移到z柱if(n==1)move(x,1,z);//将编号为1的盘子从x柱移到z柱

else{//将n-1个编号从上到下为1…n-1的盘子从x柱，借助y柱移到z柱

Hanoi(n-1,x,z,y);move(x,n,z);//将编号为n的盘子从x柱移到z柱

//将n-1个编号从上到下为1…n-1的盘子从y柱，借助x柱移到z柱

Hanoi(n-1,y,x,z);}}//Hanoi程序设计如下谁能画出Hanoi塔的递归函数运行示意图？栈在递归算法的内部实现中所起的作用①调用函数时：系统将会为调用者构造一个由返回地址、参数表（实参）和中间变量组成的活动记录，并将其压入到由系统提供的运行时刻栈的栈顶，然后将程序的控制权转移到被调函数。若被调函数有局部变量，则在运行时刻栈的栈顶也要为其分配相应的空间。因此，活动记录和这些局部变量形成了一个可供被调函数使用的活动结构。

35栈在递归算法的内部实现中所起的作用注意：

参数表的内容为实参，返回地址是函数调用语句的下一指令的位置。②被调函数执行完毕时：系统将运行时刻栈栈顶的活动结构退栈，并根据退栈的活动结构中所保存的返回地址将程序的控制权转移给调用者继续执行。36递归算法的执行过程是不断地自调用，直到到达递归出口才结束自调用过程；到达递归出口后，递归算法开始按最后调用的过程最先返回的次序返回；返回到最外层的调用语句时递归算法执行过程结束。37堆栈递归调用总结383.2队列与线性表相同，仍为一对一关系。顺序队或链队，以循环顺序队更常见。存储结构逻辑结构只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。尾部插入首部删除队列定义393.2队列只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。运算规则实现方式基本操作：入队或出队，建空队列，判队空或队满等操作。40队列（Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。它是一种先进先出（ＦＩＦＯ）的线性表。例如：队列Q=(a1

,a2,a3,……….,an-1,an)在队尾插入元素称为入队；在队首删除元素称为出队。队首队尾1、队列是一种特殊线性表41问：为什么要设计队列？它有什么独特用途？离散事件的模拟（模拟事件发生的先后顺序,例如CPU芯片中的指令译码队列）；操作系统中的作业调度（一个CPU执行多个作业）；3.简化程序设计。答：3.2.1、队列是一种特殊线性表42队的实现方式是本节重点，关键是掌握入队和出队操作。

具体实现依存储结构（链队或顺序队）的不同而不同。队的抽象数据类型定义：ADTQueue{数据对象：D=……数据关系：R=……基本操作：……}ADTQueue建队、入队或出队、判队空或队满等，教材P59-60罗列了9种基本操作。3.2.2、队列实现方式队列存储方式431、链队列2、顺序队44链队列类型定义：

typedefstruct{QueuePtrfront;//队首指针

QueuePtr

rear;//队尾指针

}LinkQueue;结点类型定义：

typedefStructQNode{QElemTypedata;//元素StructQNode*next;//指向下一结点的指针}Qnode,*QueuePtr;关于整个链队的总体描述链队中任一结点的结构1.链队列45讨论：空链队的特征？Q(队尾)(队首)fronta1a2a3^rearpfront^rear③怎样实现链队的入队和出队操作？②链队会满吗？front=rear一般不会，因为删除时有free动作。除非内存不足！入队（尾部插入）：rear->next=s;rear=s;出队（头部删除）：front->next=front->next->next;SD^链队示意图：完整操作函数见教材46采用动态分配空间的形式顺序队类型定义：建队核心语句：q.base=(QElemType*)malloc(sizeof(QElemType）*QUEUE_MAXSIZE);

//分配空间关于整个顺序队的总体描述#defineQUEUE-MAXSIZE100//最大队列长度

typedefstruct{QElemType*base;//队列的基址

intfront;//队首指针

intrear;//队尾指针

}SqQueue2.顺序队47Q(队尾)(队首)fronta1a2a3dataa40.......99rear②队列会满吗？极易装满！因为数组通常有长度限制，而其前端空间无法释放。①空队列的特征？约定：front=rear队尾后地址入队(尾部插入)：Q[rear]=e;rear++

;

出队(头部删除)：e=Q[front];front++;

讨论：假溢出！有缺陷③怎样实现入队和出队操作？核心语句如下：用base做数组名e顺序队示意图：48解决假溢出的途径———采用循环队列答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。问：什么叫“假溢出”？如何解决？2.顺序队49a3a2a10123N-1rearfront循环队列（臆造）顺序队列a3a2a1frontrear0123..N-1顺序队列转化为循环队列50新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有三：①使用一个计数器记录队列中元素个数（即队列长度）；②加设标志位，删除时置1,插入时置0,则可识别当前front=rear属于何种情况③人为浪费一个单元，则队满特征可改为front=(rear+1)%N；顺序队列转化为循环队列51队空条件:front=rear(初始化时：front=rear)队满条件：front=(rear+1)%N(N=maxsize)队列长度（即数据元素个数）：L=（N＋rear－front）%NJ2J3 J1J4

J5frontrear

实际中常选用方案3（人为浪费一个单元）：即front和rear二者之一指向实元素，另一个指向空闲元素。

问3：在具有n个单元的循环队列中，队满时共有多少个元素？N-1个6

问1：左图中队列maxsizeN=？问2：左图中队列长度L=？5顺序队列转化为循环队列52（Ａ）r－f（Ｂ）（n＋f－r）%n（Ｃ）n＋r－f（Ｄ）（n＋r－f）%n要分析4种公式哪种最合理？当r≥f时（A）合理；当r<f时（C）合理；答：综合2种情况，以（D）的表达最为合理例2：在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是先移动队首指针取出元素√，后。例1：数组Ｑ[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素的公式为:示例53例3：一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?J2J3 J1J4

J5front=1rear=0解：由图可知，队头和队尾指针的初态分别为front=1和rear=0。删除4个元素后f=5；再插入4个元素后，r=(0+4)%6=4

front=5J6J5J7J8J9rear=4rear=0front=554讨论：循环队列的基本操作如何实现？以建队、入队和出队三种基本操作为例1）初始化一个空队列算法要求：生成一空队列算法操作：为队列分配基本容量空间设置队列为空队列，其特征即：

front=rear=0（也可为任意单元，如1，2，…甚至-1）循环队列操作551)建队的完整算法StatusInitQueue(SqQueue&q)//初始化空循环队列q{q.base=(QElemType*)malloc(sizeof(QElemType）*QUEUE_MAXSIZE);//分配空间if(!q.base)exit(OVERFLOW);//内存分配失败，退出程序q.front=q.rear=0;//置空队列returnOK;}//InitQueue;56算法说明：向循环队列的队尾插入一个元素分析：(1)插入前应当先判断队列是否满？

if((q.rear+1)%QUEUE_MAXSIZE)==q.front)retur