专业课参考数据结构

第三章栈和队列栈和队列操作受限的线性表栈（Stack）运算只在表的一端进行队列（Queue）运算只在表的两端进行3.1栈3.1.1栈的概念一、栈(stack)仅能在表尾进行插入、删除操作的线性表。（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除能进行插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。称插入操作为进栈(push)，删除操作为出栈(pop)。进栈出栈操作只能在栈顶进行。3.1栈出栈进栈栈的特点后进先出第一个进栈的元素在栈底最后一个进栈的元素在栈顶第一个出栈的元素为栈顶元素最后一个出栈的元素为栈底元素栈示意图栈顶栈底ana2a1后进先出表（LIFO表Last_inFirst_out）3.1栈二、栈的基本操作1）初始化操作InitStack(&S)功能：构造一个空栈S。2）销毁栈操作DestroyStack(&S)功能：销毁一个已存在的栈。3）置空栈操作ClearStack(&S)功能：将栈S置为空栈。4）取栈顶元素操作GetTop(S,&e)功能：取栈顶元素，并用e返回。3.1栈二、栈的基本操作5）进栈操作Push(&S,e)功能：元素e进栈。6）退栈操作Pop(&S,&e)功能：栈顶元素退栈，并用e返回。7）判空操作StackEmpty(S)

功能：若栈S为空，则返回True，否则，栈不空返回False。3.1栈栈的实现方式顺序栈（Array-basedStack）

使用数组实现，本质上是顺序表的简化版（只需栈的大小）

关键是确定哪一端作为栈顶链式栈（LinkedStack）

用单链表方式存储，其中指针的方向是从栈顶向下链接3.1栈3.1.2栈的顺序存储和实现一、栈的顺序存储结构#defineSTACK_INIT_SIZE100

//栈存储空间的初始分配量#defineSTACKINCREMENT10

//空间的分配增量

typedefstruct{

ElemType*base;

//栈空间基址

ElemType*top;

//栈顶指针

intstacksize;

//当前分配的栈空间大小}SqStack;3.1栈3.1.2栈的顺序存储和实现顺序栈的图示S.stacksizeS.topS.base10099nn-1n-210anan-1a2a1当栈用顺序结构存储时，栈的基本操作如建空栈、进栈、出栈等如何实现？？约定：栈顶指针指向栈顶元素的下一个位置3.1栈3.1.2栈的顺序存储和实现topbasebasetopABCDE空栈basetopAA进栈BCDE进栈basetopABEDC出栈称为：栈满空栈

top=base栈满

top-base=stacksize

(无可分配空间)12340ABCDE3.1栈不可扩充栈的操作top=012340栈空栈顶指针top，指向实际栈顶后的空位置，初值为basetop进栈A栈满BCDE设数组大小为Mtop=M，栈满，此时入栈，则上溢

(overflow)toptoptoptoptoptoptoptoptoptop栈空top==base，栈空，此时出栈，则下溢(underflow)top12340出栈12340ABCDE3.1栈可扩充栈的操作栈顶指针top，指向实际栈顶后的下一个位置，初值为top=basetop进栈A出栈栈当前空间不足，需扩充BCDE设栈的初始分配量为Stacksize=STACK_INIT_SIZE。若top==Stacksize，栈满，此时入栈，则需扩充栈空间，每次扩充

STACK_INCREMENT；若无可利用的存储空间，则上溢

(overflow)。toptoptoptoptoptoptoptoptoptop栈空若top==base,栈空，此时出栈，则下溢(underflow)base栈空topbasebasetop12340123403.1栈二、顺序栈基本操作的算法1）初始化操作InitStack(SqStack&S)参数：S是存放栈的结构变量功能：建一个空栈SS.stacksizeS.topS.base10099nn-1n-2103.1栈初始化操作算法StatusInitStack(SqStack&S)

{

//构造一个空栈S

S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

//为顺序栈动态分配存储空间

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

//分配失败

S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}

//InitStack99nn-1n-210anan-1a2a1S.stacksizeS.topS.base2）销毁栈操作

DestroyStack(SqStack&S)功能：销毁一个已存在的栈100null0null3.1栈StatusDetroyStack(SqStack&S){if(!S.base)returnERROR;

//若栈未建立（尚未分配栈空间）

free(S.base);

//回收栈空间

S.base=S.top=NULL;

S.stacksize=0;

returnOK;

}

//DetroyStack

销毁操作算法3.1栈3）置空栈操作ClearStack(SqStack&S)功能：将栈S置为空栈

S.stacksizeS.topS.base10099nn-1n-210anan-1a2a1S.stacksizeS.topS.base10099nn-1n-210anan-1a2a13.1栈StatusClearStack(SqStack&S){if(!S.base)returnERROR;

//若栈未建立（尚未分配栈空间）

S.top=S.base;

returnOK;

}

//ClearStack

置空操作算法3.1栈eanS.stacksizeS.topS.base10099nn-1n-210anan-1a2a14）取栈顶元素操作GetTop(SqStackS,ElemType&e)功能：取栈顶元素，并用e返回3.1栈StatusGetTop(SqStackS,ElemType&e){if(S.top==S.base)returnERROR;

//栈空

e=*(S.top-1);

returnOK;

}

//GetTop取栈顶元素操作算法3.1栈5）进栈操作Push(SqStack&S,ElemTypee)功能：元素e进栈。S.stacksizeS.topS.base10099nn-1n-210anan-1a2a1e进栈前e进栈后S.stacksizeS.topS.base10099nn-1n-210eanan-1a2a13.1栈*S.top=e;S.top++;进栈操作算法StatusPush(SqStack&S,ElemTypee){

//将元素e插入栈中，使其成为新的栈顶元素

if(S.top-S.base>=S.stacksize)

//若栈满则追加存储空间

{S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

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

//存储分配失败

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

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

//元素e插入栈顶，后修改栈顶指针

returnOK;

}

//Push3.1栈出栈操作前S.stacksizeS.topS.base10099nn-1n-210anan-1a2a16）出栈操作Pop(SqStack&S,ElemType&e)功能：栈顶元素退栈，并用e返回。3.1栈ean出栈操作后S.stacksizeS.topS.base10099nn-1n-210an-1a2a1S.top--;e=*S.top;StatusPop(SqStack&S,ElemType&e){if(S.top==S.base)returnERROR;

//栈空

e=*--S.top;

//

--S.top;e=*S.top;

returnOK;

}

//Pop出栈操作算法3.1栈另一种约定：栈顶指针指向栈顶元素。该如何处理？栈的链式存储结构，也称链栈。栈顶栈底根据线性链表的插入、删除操作算法，不难写出链式栈初始化、进栈、出栈等操作的算法3.1.3栈的链式存储和实现3.1栈DatanextSan-1a1an∧顺序栈和链式栈的比较栈的特点：后进先出体现了元素之间的透明性时间效率所有操作都只需常数时间O(1)顺序栈和链式栈在时间效率上难分伯仲空间效率顺序栈须说明一个固定的长度链式栈的长度可变，但增加结构性开销顺序栈和链式栈的比较实际应用中，顺序栈比链式栈用得更广泛顺序栈容易根据栈顶位置，进行相对位移，快速定位并读取栈的内部元素顺序栈读取内部元素的时间为O(1)，而链式栈则需要沿着指针链游走，显然慢些，读取第k个元素需要时间为O(k)一般来说，栈不允许“读取内部元素”，只能在栈顶操作数制转换括号匹配的检验行编辑程序迷宫求解表达式求值消除递归3.2栈的应用举例迷宫求解3.2栈的应用举例入口出口如何走出迷宫？求迷宫路径算法若当前位置“可通”，则纳入路径，继续前进；若当前位置“不可通”，后退一个位置，换方向继续探索；若四周“均已探索”，则后退一步，将当前位置从路径中删除出去，换方向继续探索。3.2栈的应用举例求迷宫路径算法若当前位置“可通”，则纳入路径，继续前进；若当前位置“不可通”，后退一个位置，换方向继续探索；若四周“均已探索”，则后退一步，将当前位置从路径中删除出去，换方向继续探索。3.2栈的应用举例1234567891233入口出口64859问题：输入算术表达式，求计算结果。2+3*(5-4)=5栈的应用举例－表达式求值3.2栈的应用举例表达式的递归定义基本符号集：{0,1,…,9,+,-,*,/,(,)}

语法成分集：{<表达式>,<项>,<因子>,<常数>,<数字>}语法公式集中缀表达式

23+(34*45)/(5+6+7)后缀表达式

233445*56+7+/+3.2栈的应用举例<表达式>∷=<项>+<项>|<项>－

<项>|<项><项>∷=<因子>*<因子>|<因子>/<因子>|<因子><因子>∷=<常数>|（

<表达式>）<常数>∷=<数字>|<数字><常数><数字>∷=

0|1|2|3|4|5|6|7|8|93.2栈的应用举例计算规则先执行括号内的计算，后执行括号外的计算。在具有多层括号时，按层次反复地脱括号，左右括号必须配对在无括号或同层括号时，先乘(*)、除(／)，后加(+)、减(-)在同一个层次，若有多个乘除（*、／）或加减(+，-)的运算，那就按自左至右顺序执行3.2栈的应用举例1.表达式的构成

操作数+运算符+界符1234如何确定运算符的运算顺序？？常数+、-、*、/()、#3.2栈的应用举例2.表达式的求值：例：5+6(1+2)-4按照四则运算法则，上述表达式的计算过程为：5+6(1+2)-4=5+63-4=5+18-4=23-4=193.算符优先关系表。表达式中相邻运算符1、2的优先关系：

<：1低于2

=：1等于2

>：1高于2+

θ2

θ1

-*/()#+

-

*

/

(

)

#>><<<>>>>>><>>注：θ1、θ2是相邻算符，θ1在左，θ2在右3.2栈的应用举例>><

<

<

>>>>>><

>><

<

<

<

<

=

>>>>E

E

>

>

<

<

<

<

<

E

=

用两个栈分别保存扫描过程中遇到的操作数和运算符从左向右扫描表达式：遇操作数，保存；遇运算符号j，与刚处理过的运算符i比较：

若i<j

则保存j（已存入栈中的运算符的优先关系为1<2<3<4…）若i>j

则说明i是已扫描过的运算符中优先级最高的，可进行运算若i=j

则说明括号内算式已算完，需消去括号5+4(1+2)-6后面也许有优先级更高的算符+

+(后保存的算符优先级高3.2栈的应用举例：算符优先算法在算符优先算法中，建立了两个工作栈。一个是OPTR栈，用以保存运算符；一个是OPND栈，用以保存操作数或运算结果。算法的基本思想是：1、首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素。2、依次读入表达式中每个字符，若是操作数，则进OPND栈；若是运算符，则与OPTR栈的栈顶运算符比较优先级后作相应操作。直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。3.2栈的应用举例表达式求值示意：5+6(1+2)-4topbaseOPTR栈#OPND栈topbase5toptop+top6top×top(top1top+top2toptoptoptop3toptoptoptoptop18toptoptoptop23top-top4toptoptoptop19toptoptop5读入表达式过程：+6×(1+2)-4#=191+2=36×3=185+18=2323-4=193.2栈的应用举例#include<stdio.h>#include<math.h>#defineNul0x00charchinput[200],*p; /*运算式存储字符串*/ /*运算式当前读取位置*/structt /*符号栈*/{ chardat[200]; inttop;}prt;structd /*数字栈*/{ longintdat[200]; inttop;}prd;3.2栈的应用举例charPRI[9][9]=/*优先级列表*/{ {'>','>','<','<','<','<','<','>','>'}, {'>','>','<','<','<','<','<','>','>'}, {'>','>','>','>','<','<','<','>','>'}, {'>','>','>','>','<','<','<','>','>'}, {'>','>','>','>','>','<','<','>','>'}, {'>','>','>','>','>','<','<','>','>'}, {'<','<','<','<','<','<','<','=',Nul}, {'>','>','>','>','>','>',Nul,'>','>'}, {'<','<','<','<','<','<','<',Nul,'='}};3.2栈的应用举例voidpushd(longinta) /*数字入栈*/{ prd.dat[prd.top++]=a;}voidpusht(chara) /*符号入栈*/{ prt.dat[prt.top++]=a;}longintpopd() /*数字出栈*/{ returnprd.dat[--prd.top];}charpopt() /*符号出栈*/{ returnprt.dat[--prt.top];}3.2栈的应用举例longintnumble() /*数字整理*/{ longintb=0; do { b=b*10+*p-'0'; p++; } while(*p>='0'&&*p<='9'); returnb;}3.2栈的应用举例longoperation(longintx,longinty,chara){switch(a){case'+':returnx+y;case'-':returnx-y;case'*':returnx*y;case'/':if(y) returnx/y; else {printf("Divide0.\n"); exit(0); }case'%':return(longint)fmod(x,y);case'^':if(y>=0)return(long)pow(x,y); elsereturn(0);default:printf("ErrorNo.3\n"); exit(1);}}3.2栈的应用举例intsignswitch(chara) /*符号转换*/{switch(a){case'+':return0;case'-':return1;case'*':return2;case'/':return3;case'%':return4;case'^':return5;case'(':return6;case')':return7;case'#':return8;default:printf("ErrorNo.2\n");exit(1);}}charrefusal(chara,charb)/*判定优先级*/{ returnPRI[signswitch(a)][signswitch(b)];}3.2栈的应用举例voidmain(){inti,j,k,l,flag=0;/*flag=0前一个符号不是)*/charb;prt.dat[0]='#';prt.top=1;prd.top=0;printf("EnterExpression=");scanf("%s",chinput); /*接收运算式*/strcat(chinput,"#"); /*在运算式结尾加#号*/p=chinput;....printf("%d\n",prd.dat[prd.top-1]);/*输出*/}3.2栈的应用举例while(*p!='#'||prt.dat[prt.top-1]!='#'){if(*p>='0'&&*p<='9'){j=numble();/*如果是数字进行整理并入栈*/ pushd(j);}

else/*如果是符号与栈顶的符号比较并运算*/

{if(flag==1&&*p=='('){printf("ErrorNo.1:%s\n",p);exit(0);

}

elseif(*p==')')flag=1; else flag=0; switch(refusal(prt.dat[prt.top-1],*p)) { ....

}

}}3.2栈的应用举例switch(refusal(prt.dat[prt.top-1],*p)){ case'<':pusht(*p++);/*高则入栈*/ break; case'=':popt();/*脱括号*/ p++;break; case'>':b=popt();/*低则进行栈顶计算*/k=popd();/*第二操作数出栈*/l=popd();/*第一操作数出栈*/

k=operation(l,k,b); /*计算*/

pushd(k); /*计算结果入栈*/

break;

caseNul:printf("ErrorNo.4:%s\n",p);

exit(1);}3.2栈的应用举例两个独立的栈底部相连：双栈

迎面增长：对顶栈3.2栈的应用举例对顶栈top1top2递归是很有用的工具，在数学和程序设计等许多领域中得到应用。任何一个递归程序都可以通过非递归程序实现。3.3栈与递归栈在实现函数递归调用中所发挥的作用栈的最广泛的应用隐藏在用户看不到的地方：高级语言运行时环境提供的函数调用机制。

运行时环境指的是目标计算机上用来管理存储器并保存指令执行过程中所需信息的寄存器及存储器的结构。C/C++编译程序占用的内存情况：栈（Stack）堆（Heap）全局区常量区程序代码区动态区静态区自由空间高地址低地址函数调用过程 在非递归情况下（不支持递归的程序设计语言中），数据区的分配可以在程序运行前进行，直到整个程序运行结束才释放，这种分配称为静态分配。 采用静态分配时，函数的调用和返回处理比较简单，不需要每次分配和释放被调函数的数据区。3.3栈与递归函数的递归调用过程 在递归调用的情况下，被调函数的局部变量不能静态地分配某些固定单元，而必须每调用一次就分配一份新的局部变量，以存放当前函数所使用的数据，当函数结束返回时随即释放。 故其存储分配只能在调用时（程序运行过程中）才能进行，即所谓的动态分配。 在内存中要开辟一个称为运行栈（runtimestack）的足够大的动态区，以处理运行数据。3.3栈与递归函数运行时的动态分配过程用于动态数据分配的存储区可按多种方式组织。典型的组织是将这个存储器分为栈（stack）区域和堆（heap）区域：

栈区域用于分配发生在后进先出LIFO风格中的数据（诸如函数的调用）。

堆区域则用于不符合LIFO（诸如指针的分配）的动态分配。3.3栈与递归堆自由空间代码区域全程/静态区域栈函数活动记录（activationrecord）是动态存储分配中一个重要的单元。当调用或激活函数时，函数的活动记录包含了为其局部数据分配的存储空间。3.3栈与递归临时数据域局部数据域机器状态域控制链参数域返回值域函数的活动记录运行栈的动态变化每次调用时，执行进栈操作，将被调函数的活动信息压入栈中，即每当进行一次新的函数调用时，都要在栈的顶部为新的活动记录分配空间。在每次从函数返回时，执行出栈操作，释放本次的活动记录，恢复到上次调用所分配的数据区中。被调函数中变量地址全部采用相对于栈顶的相对地址来表示。3.3栈与递归一个函数在运行栈上可以有若干不同的活动记录，每个活动记录都代表了一次不同的调用对于递归函数来说，递归的深度就决定了其在运行栈中活动记录的数目。当函数递归调用时，函数体的同一个局部变量，在不同的递归层次要分配不同的存储空间，放在内部栈的不同位置。3.3栈与递归函数调用时的三个步骤

1.调用函数发送调用信息。调用信息包括调用方要传送给被调方的信息，诸如实参、返回地址等。

2.为被调函数分配需要的局部数据区，用来存放被调方定义的局部变量、形参变量（存放实参）、返回地址等，并接受调用方传送来的调用信息。

3.调用方暂停，把计算控制转到被调方，即自动转移到被调用的函数的程入口。3.3栈与递归当被调方结束运行，返回到调用方时，其返回处理也分解为三步进行

1.传送返回信息，包括被调方要传回给调用方的信息，诸如计算结果等。

2.释放分配给被调方的数据区。

3.按返回地址把控制转回调用方。3.3栈与递归以阶乘为例：#include<stdio.h>main(){ intx; scanf(”%d”,&x)；

printf(”%d\n”,factorial(4));}longfactorial(longn){ if(n==0) return1; else returnn*factorial(n-1);//递归调用}3.3栈与递归递归函数调用过程3.3栈与递归n:4控制链返回地址第1次调用factorial时的活动记录x:4主程序main的活动记录栈生长方向n:4控制链返回地址第1次调用factorial时的活动记录x:4主程序main的活动记录n:3控制链返回地址第2次调用factorial时的活动记录栈生长方向3.3栈与递归n:4控制链返回地址第1次调用factorial的活动记录n:3控制链返回地址n:2控制链返回地址n:1控制链返回地址n:0控制链返回地址0!=11!=1*0！=12!=2*1！=23!=3*2！=64!=4*3！=24自由空间栈生长方向x:4主程序main的活动记录返回地址n:2控制链返回地址返回地址！！！第2次调用factorial的活动记录第3次调用factorial的活动记录第4次调用factorial的活动记录第5次调用factorial的活动记录3.4.1队列的概念一、队列（queue)仅能在表头进行删除，表尾进行插入的线性表。（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除能进行插入的一端称为队尾(rear)，能进行删除的一端称为队头(front)。称插入操作为入队(enqueue)，删除操作为出队(dequeue)。3.4队列a1a2a3an队头队尾出队列队列的示意图队列的特点先进先出第一个入队的元素在队头最后一个入队的元素在队尾第一个出队的元素为队头元素最后一个出队的元素为队尾元素入队列3.4队列二、队列的基本操作1）初始化操作InitQueue(&Q)功能：构造一个空队列Q。2）销毁操作DestroyQueue(&Q)功能：销毁已存在队列Q。3）置空操作ClearQueue(&Q)功能：将队列Q置为空队列。4）出队操作DeQueue(&Q,&e)功能：删除Q的队头元素。5）取队头元素操作GetHead(Q,&e)功能：取队头元素，并用e返回。3.4队列二、队列的基本操作6）入队操作EnQueue(&Q,e)功能：将元素e插入Q的队尾。7）判空操作QueueEmpty(Q)功能：若队列Q为空，则返回True，否则返回False。3.4队列队列的实现方式顺序队列关键是如何防止假溢出。链式队列用单链表方式存储，队列中每个元素对应链表中的一个结点。3.4队列3.4.2循环队列——队列的顺序存储和实现一、队列的顺序存贮结构#defineMAXSIZE100//最大队列长度

typedefstruct{ElemType*base;//初始化时分配存储空间的基址

intfront;//队头指针，指向队头元素

intrear;//队尾指针，指向队尾元素的下一个位置}SqQueue;队头,队尾指针是用整型实现的3.4队列Q.rearQ.frontJ1J2J3Q.rearQ.frontJ3(a)空队列(b)J1,J2和J3相继入队列(c)J1和J2相继出队(d)J4,J5和J6相继入队之后,J3出队Q.rearQ.front012345Q.rearQ.frontJ6J5J4Q.front,Q.rear均为整数用箭头指示只是为了直观又有J7入队,该怎么办？？3.4队列3.4队列队列基本操作123450队空front=0rear=0123450frontJ1,J2,J3入队J1J2J3rearJ4,J5,J6入队rear123450J4J5J6front设两个指针：front,rear。rear指向队尾元素的下一个位置；front指向队头元素。初值

front=rear=0队空条件：front==rear入队列：Q.base[rear++]=e;出队列：e=Q.base[front++];rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront又有J7入队,该怎么办？？Q.base3.4队列存在问题设数组大小为M，则：当front=0，rear=M时，再入队发生溢出——真溢出当front0，rear=M时，再入队发生溢出——假溢出解决方案队首固定，每次出队后将剩余元素向下移动——浪费时间循环队列基本思想：把队列设想成环形，让Q.base[M-1]接在

Q.base[0]之后，若

rear+1==M，则令

rear=0;rear123450J4,J5,J6入队J4J5J6front0M-11frontrear…...…...3.4队列实现：利用“模”运算入队：Q.base[rear]=e;rear=(rear+1)%M;出队：e=Q.base[front];front=(front+1)%M;队满、队空判定条件?012345rearfrontJ7J5J6012345frontJ4J9J8rearJ5J6J4012345rearfrontJ4,J5,J6出队J7,J8,J9入队队空：front==rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front==rear

队满：(rear+1)%M==front队满：front==rear3.4队列J4,J5,J6出队J7,J8入队队满：front==(rear+1)%M

少用一个元素空间：队空：front==rear

队满：(rear+1)%M==front队空：front==rearJ5J6J4012345rearfront012345rearfrontJ7J5J6012345frontJ4J8rear1）初始化操作InitQueue_Sq(SqQueue&Q)

参数：Q是存放队列的结构变量功能：建一个空队列Q算法：StatusInitQueue_Sq(SqQueue&Q){//构造一个空队列Q

Q.base=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));if(!Q.base)exit(OVERFLOW);

//存储分配失败

Q.front=Q.rear=0;

ReturnOK;

}

//InitQueue_Sq二、循环队列的基本操作算法3.4队列Q.frontQ.rear54

03

122）入队操作EnQueue_Sq(SqQueue&Q,ElemTypee)功能：将元素e插入队尾Q.frontQ.rear54

03

12J1J3J2eQ.frontQ.rear54

03

12J1J3J2元素e入队前元素e入队后3.4队列入队操作算法：

StatusEnQueue_Sq(SqQueue&Q,ElemTypee)

{//将元素e插入队尾

if((Q.rear+1)%MAXSIZE==Q.front)returnERROR;//队满

Q.base[Q.rear]=e;//将元素e插入队尾Q.rear=(Q.rear+1)%MAXSIZE;//修改队尾指针

returnOK;

}//EnQueue_Sq3.4队列3)出队操作DeQueue_Sq(SqQueue&Q,QElemType&e)功能：删除队头元素，用e返回其值Q.frontQ.rear54

03

12J1J3J2Q.frontQ.rear54

03

12J1J3J2出队操作前出队操作后eJ13.4队列出队操作算法：StatusDeQueue_Sq(SqQueue&Q,ElemType&e)

{//删除队头元素，用e返回其值，并返回OK；否则返回ERRORif((Q.rear==Q.front)returnERROR;//队空

e=Q.base[Q.front];//取队头元素eQ.front=(Q.front+1)%MAXSIZE;//修改队头指针

returnOK;

}//EnQueue_Sq3.4队列3.4.3链队列——队列的链式存储结构和实现一、链队列Q.frontQ.rear∧空链队列J1∧Q.frontQ.rearJ2∧链队列图示3.4队列二、链队列的类型定义typedefstructQNode//链队列结点的类型定义{ElemTypedata;

structQNode*next;}QNode,*QueuePtr;3.4队列typedefstruct//链队列的表头结点的的类型定义{

QueuePtrfront;

//队头指针，指向链表的头结点

QueuePtr

rear;

//队尾指针，指向队尾结点}LinkQueue;头结点

^…...front队头队尾rearfront指向头结点，rear指向队尾3.4队列链式队列的基本操作frontrearx入队^xfrontreary入队x^yfrontrearx出队x^yfrontrear空队^frontreary出队^判断队空的条件：front==rear顺序队列与链式队列的比较顺序队列固定的存储空间，方便访问队列内部元素链式队列可以满足队列大小无法估计的情况，但访问队列内部元素不方便3.4队列变种的栈或队列双端队列双栈超队列超栈

三、队列的应用3.4队列只要满足先来先服务特性的应用均可采用队列作为其数据组织方式或中间数据结构。

调度或缓冲消息缓冲器邮件缓冲器计算机的硬设备之间的通信也需要队列作为数据缓冲操作系统的资源管理队列应用提出问题 某运动会设立N个比赛项目，每个运动员可以参加1～3个项目。如何安排赛程既可使同一运动员参加的项目不安排在同一时间进行，又可使总的竞赛日程最短。问题抽象 若将此问题抽象成数学模型，则归属于“划分子集”问题。 N个比赛项目构成一个大小为n的集合，有同一运动员参加的项目则抽象为“冲突”关系。栈和队列例如：某运动会设有9个项目：A={0，1，2，3，4，5，6，7，8}，七名运动员报名参加的项目分别为： （1,4,8）、（1,7）、（8,3）、（1,0,5）、（3,4）、（5,6,2）、（6,4）它们之间的冲突关系为：R={(1,4),(4,8),(1,8),

(1,7),(8,3),

(1,0),(0,5),(1,5),

(3,4),(5,6),(5,2),(6,2),(6,4)}构造9×9的“冲突”矩阵clash。栈和队列数据表示R={(1,4),(4,8),(1,8),(1,7),(8,3),(1,0),(0,5),(1,5),(3,4),(5,6),(5,2),(6,2),(6,4)}对称矩阵

012345678001000100011000110112000001100300001000140101001015111000100600101100070100000008010110000栈和队列问题分析“划分子集”问题即为：将集合A划分成k个互不相交的子集：A1，A2，…，Ak（k≤n） 使同一子集中的元素均无冲突关系，并要求划分的子集数目尽可能地少。 对前述例子而言，问题即为：同一子集中的项目是可以同时进行的项目，显然希望运动会的日程尽可能短。栈和队列算法设计 可利用“过筛”的方法来解决划分子集问题。 从第一个元素考虑起，凡不与第一个元素发生冲突的元素都可以和它分在同一子集中，然后再“筛”出一批互不冲突的元素为第二个子集。 依次类推，直至所有元素都进入某个子集为止。栈和队列

012345678001000100011000110112000001100300001000140101001015111000100600101100070100000008010110000012345678145684588

010001000

010002100

010012101

02001210171(0237)(16)栈和队列 为了减少重复察看R数组的时间，可另设一个数组clash[n]，记录和当前已入组元素发生冲突的元素的信息。 每次新开辟一组时，令clash

数组各分量的值均为“0”，当序号为“i”的元素入组时，将和该元素发生冲突的信息记入clash数组。栈和队列pre(前一个出队列的元素序号)=n;组号=0;全体元素入队列;while(队列不空){

队头元素i出队列;

if(i<pre)//开辟新的组

{

组号++;clash数组初始化;

}

if(i能入组)

{i入组，记下序号为i的元素所属组号;

修改clash数组;

}

elsei重新入队列;pre=i;}结果：(0,2,3,7)，(1,6)，(4,5)，(8)栈和队列练习1、已知一堆栈的进栈序列为：1234