数据结构林业信息学院第3章栈和队列

2023年4月15日

北京林业大学信息学院李冬梅

数据结构

2023年4月15日

北京林业大学信息学院3.1

栈3.2栈的应用3.3栈与递归3.4队列3.5队列的应用教学内容

2023年4月15日

北京林业大学信息学院第3章栈和队列掌握栈和队列的特点，并能在相应的应用问题中正确选用熟练掌握栈的两种存储结构的基本操作实现算法，特别应注意栈满和栈空的条件熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的条件理解递归算法执行过程中栈的状态变化过程

教学目标

2023年4月15日

北京林业大学信息学院栈（Stack）1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式队列（Queue）1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式

2023年4月15日

北京林业大学信息学院3.1栈1.定义用顺序栈或链栈存储均可，但以顺序栈更常见3.存储结构与线性表相同，仍为一对一关系2.逻辑结构只能在表的一端（栈顶）进行插入和删除运算的线性表

2023年4月15日

北京林业大学信息学院只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则4.运算规则关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等5.实现方式

2023年4月15日

北京林业大学信息学院栈是一种特殊的线性表，它只能在表的一端（栈顶）进行插入和删除运算栈与一般线性表的区别：仅在于运算规则不同“进”＝压入=PUSH（)“出”＝弹出=POP()一般线性表

逻辑结构：一对一存储结构：顺序表、链表运算规则：随机、顺序存取栈逻辑结构：一对一存储结构：顺序栈、链栈运算规则：后进先出栈与一般线性表的区别

2023年4月15日

北京林业大学信息学院“进”＝压入=PUSH（)“出”＝弹出=POP()

2023年4月15日

北京林业大学信息学院a1a2……an顺序栈Sai……表头表尾栈底base栈顶top低地址高地址写入：v[i]=ai读出：x=v[i]压入：PUSH(an+1)弹出：POP(x)前提：一定要预设栈顶指针top！低地址高地址v[i]a1a2

aian

……顺序表V[n]

……an+1顺序栈与顺序表

2023年4月15日

北京林业大学信息学院顺序栈的表示空栈base==top

是栈空标志stacksize=4topAbasebasetopABABCtopbasetopbaseABCDbasetop3120top指示真正的栈顶元素之上的下标地址栈满时的处理方法：1、报错,返回操作系统。2、分配更大的空间，作为栈的存储空间,将原栈的内容移入新栈。

2023年4月15日

北京林业大学信息学院#defineMAXSIZE100typedefstruct{

SElemType*base; SElemType*top; intstacksize;}SqStack;顺序栈的表示

2023年4月15日

北京林业大学信息学院构造一个空栈步骤：(1)分配空间并检查空间是否分配失败，若失败则返回错误顺序栈初始化basestacksizetops(2)设置栈底和栈顶指针

S.top=S.base;(3)设置栈大小

2023年4月15日

北京林业大学信息学院StatusInitStack(SqStack&S){

S.base=newSElemType[MAXSIZE]；

if(!S.base) returnOVERFLOW;

S.top=S.base; S.stackSize=MAXSIZE; returnOK;}顺序栈初始化

2023年4月15日

北京林业大学信息学院判断顺序栈是否为空boolStackEmpty(SqStackS){ if(S.top==S.base)returntrue;elsereturnfalse;}basetop3120

2023年4月15日

北京林业大学信息学院求顺序栈的长度intStackLength(SqStackS){ returnS.top–S.base;}basetopAB

2023年4月15日

北京林业大学信息学院StatusClearStack(SqStackS){ if(S.base)S.top=S.base; returnOK;}清空顺序栈basetop3120

2023年4月15日

北京林业大学信息学院StatusDestroyStack(SqStack&S){ if(S.base) { deleteS.base;

S.stacksize=0; S.base=S.top=NULL; }returnOK;}销毁顺序栈

2023年4月15日

北京林业大学信息学院(1)判断是否栈满，若满则出错(2)元素e压入栈顶(3)栈顶指针加1顺序栈进栈StatusPush(SqStack&S,SElemTypee){ if(S.top-S.base==S.stacksize)//栈满

returnERROR;

*S.top++=e; returnOK;}*S.top=e;S.top++;ABCtopbase

2023年4月15日

北京林业大学信息学院(1)判断是否栈空，若空则出错(2)获取栈顶元素e(3)栈顶指针减1顺序栈出栈StatusPop(SqStack&S,SElemType&e){ if(S.top==S.base)//栈空

returnERROR;

e＝*--S.top; returnOK;}--S.top;e=*S.top;ABCtopbase

2023年4月15日

北京林业大学信息学院判断是否空栈，若空则返回错误否则通过栈顶指针获取栈顶元素取顺序栈栈顶元素StatusGetTop(SqStackS,SElemType&e){ if(S.top==S.base) returnERROR; //栈空

e=*(S.top–1); returnOK;}

e=*(S.top--);???ABCtopbase

2023年4月15日

北京林业大学信息学院435612中到了12顺序不能实现；135426可以实现。1.如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？练习

2023年4月15日

北京林业大学信息学院练习Ａ．iＢ．n-iＣ．n-i+1Ｄ．不确定Ｃ2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为

2023年4月15日

北京林业大学信息学院练习Ａ．top不变Ｂ．top=0Ｃ．top++

Ｄ．top--D3.在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为

2023年4月15日

北京林业大学信息学院考研试题b[0]t[0]t[1]b[1]0m-1V双栈共享一个栈空间优点：互相调剂，灵活性强，减少溢出机会

2023年4月15日

北京林业大学信息学院将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长（如下图所示）。考研试题bot[0]top[0]top[1]bot[1]0m-1V

2023年4月15日

北京林业大学信息学院typedefstruct{ inttop[2],bot[2];//栈顶和栈底指针

SElemType*V;//栈数组

intm;//栈最大可容纳元素个数}DblStack;数据结构定义如下考研试题

2023年4月15日

北京林业大学信息学院voidDblpush(DblStack&s,SElemTypex,inti)；//把x插入到栈i的栈intDblpop(DblStack&s,inti,SElemType&x)；

//退掉位于栈i栈顶的元素intIsEmpty(DblStacks,inti)

；//判栈i空否,空返回1,否则返回0intIsFull(DblStacks)

；//判栈满否,满返回1,否则返回0试编写判断栈空、栈满、进栈和出栈四个算法的函数(函数定义方式如下）考研试题

2023年4月15日

北京林业大学信息学院b[0]t[0]t[1]b[1]0m-1V栈空：top[i]==bot[i]i表示栈的编号栈满：top[0]+1==top[1]或top[1]-1==top[0]提示

2023年4月15日

北京林业大学信息学院链栈的表示运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针

typedefstructStackNode{SElemTypedata;structStackNode*next;}StackNode,*LinkStack;LinkStackS;

datanext栈顶栈底∧S

2023年4月15日

北京林业大学信息学院链栈的初始化voidInitStack(LinkStack&S){

S=NULL;}∧S

2023年4月15日

北京林业大学信息学院判断链栈是否为空StatusStackEmpty(LinkStackS)

{

if(S==NULL)returnTRUE;

elsereturn

FALSE;

}

2023年4月15日

北京林业大学信息学院链栈进栈StatusPush(LinkStack&S,SElemTypee)

{

p=newStackNode;//生成新结点p

if(!p)exit(OVERFLOW);

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

returnOK;}p∧S

2023年4月15日

北京林业大学信息学院链栈进栈p∧SeStatusPush(LinkStack&S,SElemTypee)

{

p=newStackNode;//生成新结点p

if(!p)exit(OVERFLOW);

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

returnOK;}

2023年4月15日

北京林业大学信息学院链栈进栈p∧SeStatusPush(LinkStack&S,SElemTypee)

{

p=newStackNode;//生成新结点p

if(!p)exit(OVERFLOW);

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

returnOK;}

2023年4月15日

北京林业大学信息学院链栈进栈p∧SeSStatusPush(LinkStack&S,SElemTypee)

{

p=newStackNode;//生成新结点p

if(!p)exit(OVERFLOW);

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

returnOK;}

2023年4月15日

北京林业大学信息学院链栈出栈∧SAe=‘A’StatusPop(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;

e=S->data;p=S;S=S->next;deletep;returnOK;}

2023年4月15日

北京林业大学信息学院链栈出栈∧SAe=‘A’pStatusPop(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;

e=S->data;p=S;S=S->next;deletep;returnOK;}

2023年4月15日

北京林业大学信息学院链栈出栈∧SAe=‘A’pSStatusPop(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;

e=S->data;p=S;S=S->next;deletep;returnOK;}

2023年4月15日

北京林业大学信息学院链栈出栈StatusPop(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;

e=S->data;p=S;S=S->next;deletep;returnOK;}∧e=‘A’S

2023年4月15日

北京林业大学信息学院取链栈栈顶元素SElemTypeGetTop(LinkStackS){

if(S==NULL)

exit(1)；

elsereturnS–>data;}

2023年4月15日

北京林业大学信息学院3.2栈的应用例1：数制转换（十转N）用栈暂存低位值例2：括号匹配的检验用栈暂存左括号例3：表达式求值用栈暂存运算符例4：迷宫求解用栈实现递归调用简化了程序设计的问题

2023年4月15日

北京林业大学信息学院迷宫求解

2023年4月15日

北京林业大学信息学院从入口出发，按某一方向向未走过的前方探索若能走通，则到达新点，否则试探下一方向;若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。求解思想：回溯法迷宫求解

2023年4月15日

北京林业大学信息学院需要解决的问题：1、表示迷宫的数据结构2、试探方向3、栈的设计4、防止重复到达某点，避免发生死循环迷宫求解

2023年4月15日

北京林业大学信息学院1、表示迷宫的数据结构表示一个m行n列迷宫：用maze[m][n]表示，0≤i<m,0≤j<nmaze[i][j]=0通路maze[i][j]=1不通改进：用maze[m+2][n+2]表示且maze[i][j]=1，i=0或m＋1,j=0或n＋1入口坐标为（1，1），出口坐标为（m，n）

迷宫求解

2023年4月15日

北京林业大学信息学院012345678901111111111110010001012100100010131000011001410111000015100010000161010001001710111011018110001000191111111111

2023年4月15日

北京林业大学信息学院迷宫的定义：#definem8

/*迷宫的实际行*/#definen8

/*迷宫的实际列*/intmaze[m+2][n+2];2、试探方向表示位置的类型PosType定义如下：typedefstruct{ intx，y;}PosType;迷宫求解

2023年4月15日

北京林业大学信息学院试探顺序规定为：从正东沿顺时针方向与点(x，y)相邻的4个点及坐标(x,y)(x,y+1)(x,y-1)(x+1,y)(x-1,y)迷宫求解

2023年4月15日

北京林业大学信息学院3、栈的设计栈中每个元素的组成：通道块在路径上的序号坐标位置前进方向（东为1，南为2，西为3，北为4）栈元素的类型定义：typedefstruct{intord;PosTypeseat;intdi;}SElemType;迷宫求解

2023年4月15日

北京林业大学信息学院4、防止重复到达某点走过不通之处要加以标记（MarkPrint操作）迷宫求解算法思想及算法参见P51迷宫求解

2023年4月15日

北京林业大学信息学院表达式求值算术四则运算规则(1)先乘除,后加减(2)从左算到右(3)先括号内,后括号外

2023年4月15日

北京林业大学信息学院表达式常数标识符操作数(operand)运算符(operator)界限符(delimiter)算术逻辑关系括号结束符

2023年4月15日

北京林业大学信息学院>><<<>>>><<<>>>>>><>>>>>><>><<<<<=>>>>x>><<<<<=xx表3.1算符间的优先关系

2023年4月15日

北京林业大学信息学院【算法思想】（1）初始化OPTR栈和OPND栈，将“#”压入OPTR（2）依次读入字符ch，循环执行（3）至（5）（3）取出OPTR的栈顶元素，当OPTR的栈顶元素和ch均为“#”时，表达式求值完毕，OPND栈顶元素为表达式的值设定两栈：OPND-----操作数或运算结果OPTR------运算符（4）if(ch是操作数)则ch进OPND，读入下一字符ch（5）else比较OPTR栈顶元素和ch的优先级case‘<’:运算符ch进OPTR，读入下一字符chcase‘=’:脱括号（弹出左括号），读入下一字符chcase‘<’:栈顶运算符退栈、计算，结果进OPND

2023年4月15日

北京林业大学信息学院OperandTypeEvaluateExpression(){InitStack(OPND);ch=getchar();while(ch!='#'||GetTop(OPTR)!='#'){if(!In(ch,OP)){Push(OPND,ch);ch=getchar();}//ch不是运算符则进栈

elseswitch(Precede(GetTop(OPTR),ch)){//比较优先权

case'<'://当前字符ch压入OPTR栈，读入下一字符chPush(OPTR,ch);ch=getchar();break;case'>'://弹出OPTR栈顶的运算符运算，并将运算结果入栈

Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;case'='://脱括号并接收下一字符

Pop(OPTR,x);ch=getchar();break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression

2023年4月15日

北京林业大学信息学院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)

2023年4月15日

北京林业大学信息学院3.3栈与递归递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。

2023年4月15日

北京林业大学信息学院当多个函数构成嵌套调用时,遵循后调用先返回栈

2023年4月15日

北京林业大学信息学院以下三种情况常常用到递归方法递归定义的数学函数具有递归特性的数据结构可递归求解的问题

2023年4月15日

北京林业大学信息学院1.递归定义的数学函数:阶乘函数:

2阶Fibonaci数列:

2023年4月15日

北京林业大学信息学院树

2.具有递归特性的数据结构:RootLchildRchild广义表

A=(a,A)3.可递归求解的问题:迷宫问题Hanoi塔问题

2023年4月15日

北京林业大学信息学院分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解1、能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的2、可以通过上述转化而使问题简化3、必须有一个明确的递归出口，或称递归的边界用分治法求解递归问题必备的三个条件

2023年4月15日

北京林业大学信息学院分治法求解递归问题算法的一般形式：

voidp(参数表){if（递归结束条件）可直接求解步骤；-----基本项

elsep（较小的参数）；------归纳项

}longFact(longn){if(n==0)return1;//基本项

elsereturnn*Fact(n-1);//归纳项}

2023年4月15日

北京林业大学信息学院返回2

参数2计算2*Fact(1)返回1

参数1计算1*Fact(0)返回1

参数0直接定值=1参数传递递归调用结果返回回归求值if(n==0)return1;elsereturnn*Fact(n-1);求解阶乘n!的过程主程序

main:Fact(4)返回24参数4计算4*Fact(3)返回6

参数3计算3*Fact(2)

2023年4月15日

北京林业大学信息学院设有一个递归算法如下:intX(intn){if(n<=3)return1;elsereturnX(n-2)+X(n-4)+1}则计算X(X(8))时需要计算X函数

次.D练习A.8 B.9C.16 D.18

2023年4月15日

北京林业大学信息学院在印度圣庙里，一块黄铜板上插着三根宝石针。主神梵天在创造世界时，在其中一根针上穿好了由大到小的64片金片，这就是汉诺塔。僧侣不停移动这些金片，一次只移动一片，小片必在大片上面。当所有的金片都移到另外一个针上时，世界将会灭亡。

汉诺塔

2023年4月15日

北京林业大学信息学院规则:(1)每次只能移动一个圆盘(2)圆盘可以插在A,B和C中的任一塔座上(3)任何时刻不可将较大圆盘压在较小圆盘之上Hanoi塔问题ABC

2023年4月15日

北京林业大学信息学院Hanoi塔问题

n=1，则直接从A移到C。否则(1)用

C柱做过渡，将

A的(n-1)个移到

B(2)将

A最后一个直接移到

C(3)用

A做过渡，将

B的

(n-1)个移到

C

2023年4月15日

北京林业大学信息学院#include<iostream.h>intc=0;voidmove(charx,intn,charz){cout<<++c<<","<<n<<","<<x<<","<<z<<endl;}voidHanoi(intn,charA,charB,charC){if(n==1)move(A,1,C);else{Hanoi(n-1,A,C,B);move(A,n,C);Hanoi(n-1,B,A,C);}}voidmain(){Hanoi(3,'a','b','c');}跟踪程序，给出下列程序的运行结果，以深刻地理解递归的调用和返回过程

2023年4月15日

北京林业大学信息学院3,a,b,c递归调用树2,a,c,b2,b,a,ca-3->c

2023年4月15日

北京林业大学信息学院调用前,系统完成:(1)将实参,返回地址等传递给被调用函数(2)为被调用函数的局部变量分配存储区(3)将控制转移到被调用函数的入口调用后,系统完成:(1)保存被调用函数的计算结果(2)释放被调用函数的数据区(3)依照被调用函数保存的返回地址将控制转移到调用函数函数调用过程

2023年4月15日

北京林业大学信息学院“层次”主函数第1次调用第i次调用0层1层i层“递归工作栈”“工作记录”实在参数,局部变量,返回地址递归函数调用的实现

2023年4月15日

北京林业大学信息学院程序的具体执行过程参见：“Hanoi塔执行过程.ppt”

2023年4月15日

北京林业大学信息学院空间效率时间效率O(2n)与递归树的结点数成正比与递归树的深度成正比O(n)递归算法的效率分析

2023年4月15日

北京林业大学信息学院1234f(1)=1f(1)+1+f(1)=3f(2)+1+f(2)=7f(3)+1+f(3)=15f(n)=2f(n-1)+1f(n-1)=2f(n-2)+1f(n-2)=2f(n-3)+1......f(3)=2f(2)+1f(2)=2f(1)+120f(n)=21f(n-1)+2021f(n-1)=22f(n-2)+2122f(n-2)=23f(n-3)+22......2n-3f(3)=2n-2f(2)+2n-32n-2f(2)=2n-1f(1)+2n-2f(n)=20+21+…+2n-2+2n-1f(1)=2n-1递归算法的效率分析

2023年4月15日

北京林业大学信息学院64片金片移动次数：264-1=15假如每秒钟一次，共需多长时间呢？一年大约有31536926秒，移完这些金片需要５８００多亿年世界、梵塔、庙宇和众生都已经灰飞烟灭

……!

2023年4月15日

北京林业大学信息学院优点：结构清晰，程序易读缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。递归的优缺点递归非递归

2023年4月15日

北京林业大学信息学院3.4队列

队列是一种先进先出(FIFO)的线性表.它只允许在表的一端进行插入,而在另一端删除元素a1a2a3an...入队列队头队尾

2023年4月15日

北京林业大学信息学院a1a2a3an...队头队尾出队列

2023年4月15日

北京林业大学信息学院a1a2a3an...队头队尾出队列

2023年4月15日

北京林业大学信息学院a1a2a3an...队头队尾出队列

2023年4月15日

北京林业大学信息学院设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。（A）2（B）3（C）4（D）6练习B

2023年4月15日

北京林业大学信息学院数据对象:数据关系:基本操作:

(1)

InitQueue(&Q)//构造空队列

(2)DestroyQueue(&Q)//销毁队列

(3)ClearQueue(&S)//清空队列

(4)QueueEmpty(S)//判空.空--TRUE,ADTQueue{队列的抽象数据类型

2023年4月15日

北京林业大学信息学院(5)QueueLength(Q)//取队列长度

(6)GetHead(Q,&e)//取队头元素,(7)EnQueue(&Q,e)//入队列

(8)DeQueue(&Q,&e)//出队列

(9)QueueTraverse(Q,visit())//遍历}ADTQueue队列的抽象数据类型

2023年4月15日

北京林业大学信息学院#defineM100//最大队列长度Typedefstruct{QElemType*base;//初始化的动态分配存储空间

intfront;//头指针

intrear;//尾指针}SqQueue;

队列的顺序表示－－用一维数组base[M]

2023年4月15日

北京林业大学信息学院队列的顺序表示－－用一维数组base[M]Q.front012345Q.rearQ.frontQ.rearJ1J2J3Q.frontQ.rearJ3Q.frontQ.rearJ5J6front=rear=0空队标志：front==rear入队：base[rear++]=x;出队：x=base[front++];

2023年4月15日

北京林业大学信息学院Q.frontQ.rearJ5J6Q.front012345Q.rearJ5J6J1J2J3J4存在的问题设数组大小为Mfront=0rear=M时再入队——真溢出front0rear=M时再入队——假溢出

2023年4月15日

北京林业大学信息学院解决的方法－－循环队列10Q.rearQ.front......base[0]接在base[M-1]之后若rear+1==M则令rear=0;实现：利用“模”运算入队：

base[rear]=x;rear=(rear+1)%M;出队：

x=base[front];front=(front+1)%M;

2023年4月15日

北京林业大学信息学院J4J5J6012345rearfrontJ9J8J7J7,J8,J9入队队空：front==rear队满：front==rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front==rear

队满：(rear+1)%M==frontJ4J5J6012345rearfront012345frontJ4,J5,J6出队rear

2023年4月15日

北京林业大学信息学院循环队列#defineMAXQSIZE100//最大队列长度Typedefstruct{QElemType*base;//初始化的动态分配存储空间

intfront;//头指针

intrear;//尾指针}SqQueue;

2023年4月15日

北京林业大学信息学院StatusInitQueue(SqQueue&Q){

Q.base=newQElemType[MAXQSIZE]

if(!Q.base)exit(OVERFLOW);

Q.front=Q.rear=0;returnOK;}循环队列初始化

2023年4月15日

北京林业大学信息学院求循环队列的长度intQueueLength(SqQueueQ){

return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;

}

2023年4月15日

北京林业大学信息学院StatusEnQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}循环队列入队

2023年4月15日

北京林业大学信息学院StatusDeQueue(LinkQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;

e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}循环队列出队

2023年4月15日

北京林业大学信息学院...datanext队头队尾Q.frontQ.rear链队列

2023年4月15日

北京林业大学信息学院typedefstructQNode{QElemTypedata;structQnode*next;}Qnode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针}LinkQueue;

链队列

2023年4月15日

北京林业大学信息学院(a)空队列(b)元素x入队列(d)元素x出队列(c)元素y入队列链队列

2023年4月15日

北京林业大学信息学院StatusInitQueue(LinkQueue&Q){

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);

Q.front->next=NULL;returnOK;}链队列初始化

2023年4月15日

北京林业大学信息学院StatusDestroyQueue(LinkQueue&Q){while(Q.front){

Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}销毁链队列

2023年4月15日

北京林业大学信息学院StatusQueueEmpty(LinkQueueQ){return(Q.front==Q.rear);}判断链队列是否为空

2023年4月15日

北京林业大学信息学院StatusGetHead(LinkQueueQ,QElemType&e){if(Q.front==Q.rear)returnERROR;

e=Q.front->next->data;returnOK;}求链队列的队头元素

2023年4月15日

北京林业大学信息学院StatusEnQueue(LinkQueue&Q,QElemTypee){p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);

p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}链队列入队p

2023年4月15日

北京林业大学信息学院StatusDeQueue(LinkQueue&Q,QElemType&e){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;}链队列出队p

2023年4月15日

北京林业大学信息学院【例】汽车加油站

随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加2个队列。3.5队列的应用

2023年4月15日

北京林业大学信息学院【例】模拟打印机缓冲区

在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个