第三章堆栈和队列

第三章堆栈和队列中国矿业大学（北京）2010年春季主讲：李佳静lijj@主要内容知识点栈与队列的特征栈与递归循环队列重点难点栈的操作递归循环队列栈与队列的综合应用内容安排3.1栈的类型定义3.2栈类型的实现3.3栈的应用举例3.4队列的类型定义3.5队列类型的实现栈(stack)的类型定义3.1栈的类型定义栈是操作受限制的线性表定义：仅在表尾进行插入或删除操作的线性表；概念：栈顶：在栈顶操作，是表尾，通常用top表示；栈底：bottom，是表头；空栈:空表；通常栈底固定，栈顶移动。栈(stack)示意图a1a2a3an…栈顶top栈底

bottom表头表尾3.1栈的类型定义栈操作示例(1/2)base空栈a进栈b进栈aabtopbasetopbasetop3.1栈的类型定义栈操作示例(1/2)toptopabcdee进栈abcdef进栈溢出abde出栈cbasebasebasetop3.1栈的类型定义3.1栈的类型定义

ADTStack

{

数据对象：

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

数据关系：

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

约定an

端为栈顶，a1端为栈底。

基本操作：

}ADTStack3.1栈的类型定义InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())3.1栈的类型定义InitStack(&S)

操作结果：构造一个空栈SDestroyStack(&S)

初始条件：栈S已存在。

操作结果：栈S被销毁3.1栈的类型定义InitStack(&S)

操作结果：构造一个空栈SDestroyStack(&S)

初始条件：栈S已存在。

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

初始条件：栈S已存在。

操作结果：若栈S为空栈，则返回TRUE，否则FALE。3.1栈的类型定义StackLength(S)

初始条件：栈S已存在。

操作结果：返回S的元素个数，即栈的长度。3.1栈的类型定义GetTop(S,&e)

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

操作结果：用e返回S的栈顶元素。a1a2an……3.1栈的类型定义ClearStack(&S)

初始条件：栈S已存在。

操作结果：将S清为空栈3.1栈的类型定义Push(&S,e)

初始条件：栈S已存在。

操作结果：插入元素e为新的栈顶元素。a1a2ane……3.1栈的类型定义Pop(&S,&e)

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

操作结果：删除S的栈顶元素，并用e返回其值。a1a2anan-1

……3.1栈的类型定义内容安排3.1栈的类型定义3.2栈类型的实现顺序栈链栈3.3栈的应用举例3.4队列的类型定义3.5队列类型的实现栈的顺序存储表示//-----栈的顺序存储表示

-----

#defineSTACK_INIT_SIZE100;

#defineSTACKINCREMENT10;

typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;

类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。3.2栈类型的实现InitStack在顺序栈中的实现

StatusInitStack(SqStack&S){//构造一个空栈SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

if(!S.base)exit(OVERFLOW);//存储分配失败

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;}3.2栈类型的实现Push在顺序栈中的实现

StatusPush(SqStack&S,SElemTypee){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;

returnOK;}3.2栈类型的实现Pop在顺序栈中的实现StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，

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

//否则返回ERROR

if

(S.top

==

S.base)

returnERROR;

e=*--S.top;

returnOK;}3.2栈类型的实现链栈栈顶指针∧a1an注意:链栈中指针的方向an-13.2栈类型的实现内容安排3.1栈的类型定义3.2栈类型的实现3.3栈的应用举例3.4队列的类型定义3.5队列类型的实现例一数制转换算法基于原理：

N=(Ndivd)×d+Nmodd例如：（1348)10=(2504)8

，其运算过程如下：3.3栈的应用举例voidconversion(){InitStack(S);

scanf("%d",N);

while(N){

Push(S,N%8);N=N/8;

}

while(!StackEmpty(S)){

Pop(S,e);

printf("%d",e);

}}//conversion编程实现3.3栈的应用举例例二、括号匹配的检验假设在表达式中正确的格式为：（［］（））或［（［］［］）］不正确的格式为［（］）或（［（））或（（）］)则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。3.3栈的应用举例用期待的急迫程度描述括号匹配即后出现的“左括弧”，它等待与其匹配的“右括弧”出现的“急迫”心情要比先出现的左括弧高对“左括弧”来说，后出现的比先出现的“优先”等待检验对“右括弧”来说，每个出现的右括弧要去找在它之前“最后”出现的那个左括弧去匹配显然，必须将先后出现的左括弧依次保存，为了反映这个优先程度，保存左括弧的结构用栈最合适这样对出现的右括弧来说，只要"栈顶元素"相匹配即可。如果在栈顶的那个左括弧正好和它匹配，就可将它从栈顶删除3.3栈的应用举例算法的设计思想1）凡出现左括弧，则进栈；2）凡出现右括弧首先检查栈是否空若栈空，则表明该“右括弧”多余否则和栈顶元素比较,若相匹配，则“左括弧出栈”，否则表明不匹配。3）表达式检验结束时，若栈空，则表明表达式中匹配正确,否则表明“左括弧”有余。3.3栈的应用举例编程实现3.3栈的应用举例Statusmatching(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;…...内容安排3.1栈的类型定义3.2栈类型的实现3.3栈的应用举例3.4队列的类型定义3.5队列类型的实现队列(Queue)的定义队列：队列是一种只允许在表的一端插入，在另一端删除的存取受限的线性表。概念：队尾rear：插入端，线性表的表尾。队头front：删除端，线性表的表头3.4队列的类型定义队列(Queue)图示FIFO（FirstInFirstOut）（先进先出表）a1a2a3an-1出队列入队列队头队尾……3.4队列的类型定义队列举例例如，在一个局域网上有一台共享的网络打印机，网上每个用户都可以将数据发送给网络打印机进行输出为了保证不丢失数据，操作系统为网络的打印机生成一个"作业队列“每个申请输出的“作业”应按先来后到的顺序排队打印机从作业队列中逐个提取作业进行打印3.4队列的类型定义队列的类型定义

ADTQueue{

数据对象：

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

数据关系：

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

约定其中a1

端为队列头，an

端为队列尾基本操作：}

ADTQueue3.4队列的类型定义队列的基本操作

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit())3.4队列的类型定义

InitQueue(&Q)

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

DestroyQueue(&Q)

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

操作结果：队列Q被销毁，不再存在。3.4队列的类型定义

QueueEmpty(Q)

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

操作结果：若Q为空队列，则返回TRUE，否则返回FALSE3.4队列的类型定义

QueueLength(Q)

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

操作结果：返回Q的元素个数，即队列的长度。3.4队列的类型定义

GetHead(Q,&e)

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

操作结果：用e返回Q的队头元素。a1a2an……3.4队列的类型定义

ClearQueue(&Q)

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

操作结果：将Q清为空队列。3.4队列的类型定义

EnQueue(&Q,e)

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

操作结果：插入元素e为Q的新的队尾元素。a1a2ane……3.4队列的类型定义

DeQueue(&Q,&e)

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

操作结果：删除Q的队头元素，并用e返回其值a1a2an……

3.4队列的类型定义内容安排3.1栈的类型定义3.2栈类型的实现3.3栈的应用举例3.4队列的类型定义3.5队列类型的实现链队列——链式映象循环队列——顺序映象链队列——链式映象用链表表示的队列简称为链队列。为便于操作，一个链队列需要分别指示队头和队尾的两个指针

…a2rearfronta1an∧3.5队列类型的实现链队示意图(a)非空队frontreara1an∧

…a2Q(b)空队rearfrontQ

∧

(c)链队中只有一个元素结点frontrearQa1∧

3.5队列类型的实现链队列的定义

typedefstructQNode{//结点类型

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;3.5队列类型的实现typedefstruct{//链队列类型

QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针}LinkQueue;a1∧an…Q.frontQ.rearQ.frontQ.rear∧空队列3.5队列类型的实现InitQueue在链队列中的实现

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

Q.front=Q.rear=

(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)exit(OVERFLOW);//存储分配失败

Q.front->next=NULL;

returnOK;}3.5队列类型的实现EnQueue在链队列中的实现

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;}3.5队列类型的实现DeQueue在链队列中的实现

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

//用e返回其值，并返回OK；否则返回ERROR

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;}3.5队列类型的实现循环队列——顺序映象#defineMAXQSIZE100//最大队列长度

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

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

//指向队列头元素

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

//队列尾元素的下一个位置

}SqQueue;3.5队列类型的实现队列的顺序表示约定队头指针指向队列头元素，队尾指针指向队尾元素的下一个位置frontJ1J2J3J4frontrearJ1J2J3J4frontrearfrontrearJ1frontrearJ1J2J3J4J6J5rear543210543210问题：如何解决“假上溢”现象?3.5队列类型的实现循环队列3.5队列类型的实现循环队列操作示意图3.5队列类型的实现a5a6a7a8a10a11a12a13a14a5a6a7a8a9a10a11a12a13a5a6a7a8a90123456789frontrearfrontrearrearfrontfrontrear循环队列的状态问题空队列条件：Q.rear=Q.front;满队列条件：Q.rear=Q.front;问题：如何区别队空和队满有三种方法1.牺牲一个存储空间2.引入一个标志变量区别空和不空3.使用计数器3.5队列类型的实现InitQueue在循环队列中的实现

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