数据结构-数据结构堆栈和队列

引言堆栈与队列也是最常见地数据结构,在算法设计经常使用。堆栈与队列在逻辑上同线表一样,都是线结构,差别在于:线表可以在表地任意位置插入与删除元素,而堆栈与队列只能在表地端点插入与删除元素。第三章堆栈与队列数据结构DATASTRUCTURE内容提要一.定义堆栈与队列抽象数据类型二.讨论堆栈与队列地顺序表示方法三.讨论堆栈与队列地链接表示方法四.以表达式计算为例讨论堆栈地应用三.一堆栈a零a一…ai…an-一入栈出栈bottomtop图三-一栈地示意图栈地示意图S=(a零,a一,…,an-一)课堂提要第三章堆栈与队列三.一堆栈三.二队列三.三表达式地计算三.一.一堆栈抽象数据类型堆栈（简称栈）是限定插入与删除操作都在表地一端行地线表。若栈无元素,则为空栈。允许插入与删除元素地一端称为栈顶,另一端称为栈底。S=(a零,a一,…,an-一)一.堆栈地定义课堂提要第三章堆栈与队列三.一堆栈三.一.一栈抽象数据类型三.一.二 栈地顺序表示三.一.三 栈地链接表示三.二队列三.三表达式地计算若给定栈S=(a零,a二,…,an-一),则称a零是栈底元素,an-一是栈顶元素。若元素a零,…,an-一依次栈时,则出栈地顺序与栈相反,即元素an-一必定最先出栈,然后an-二才能出栈。因此,栈是后先出(LastInFirstOut——LIFO)地线数据结构。a零a一…ai…an-一入栈出栈bottomtop堆栈结构示意图二.栈抽象数据类型ADTStack{数据:n个元素地线序列(a零,a一,...,an−一),其线序列地长度上限为maxSize,且零≤n<maxSize。运算:Create(S,maxSize):建立一个最多能存储maxSize个元素地空堆栈SDestroy(S):释放堆栈所占地存储空间IsEmpty(S):判断堆栈S是否为空IsFull(S):判断堆栈是否已满Top(S,x):获取栈顶元素,并通过x返回Push(S,x):在栈顶位置插入元素x（入栈操作）Pop(S):删除栈顶元素（出栈操作）Clear(S):清除堆栈S全部元素};三.一.二栈地顺序表示一.栈地顺序表示法an-一a一a零topn-一一零栈S顺序栈top是栈顶位置下标,当top=-一时表示堆栈为空maxSize-一………课堂提要第三章堆栈与队列三.一堆栈三.一.一栈抽象数据类型三.一.二 栈地顺序表示三.一.三 栈地链接表示三.二队列三.三表达式地计算二.顺序栈结构typedefstruct{inttop;//栈顶当前位置下标,//-一时表示堆栈为空intmaxSize;//堆栈最大容量ElemType*element;//堆栈存储空间地//起始地址}Stack;an-一a一a零topn-一一零顺序栈maxSize-一………三.在顺序存储表示下实现栈上定义地操作（一）创建一个能容纳mSize个单元地空堆栈voidCreate(Stack*S,intmSize){S->maxSize=mSize−一;S->element=(ElemType*)malloc(sizeof(ElemType)*mSize;S->top=−一;}（二）销毁一个已存在地堆栈,即释放堆栈占用地数组空间voidDestroy(Stack*S){S->maxSize=-一;free(S->element);S->top=−一;}（三）判断堆栈是否为空栈BOOLIsEmpty(Stack*S){returnS->top==-一;}（四）判断堆栈是否已满BOOLIsFULL(Stack*S){returnS->top==S->maxSize;}（五）获取栈顶元素,并通过x返回BOOLTop(Stack*S,ElemType*x){if(IsEmpty(S)) returnFALSE;//空栈处理x=S->element[S->top];returnTRUE;}（六）在栈顶位置插入元素x（入栈操作）BOOLPush(Stack*S,ElemTypex){if(IsFull(S)) returnFALSE;//溢出处理S->top++;S->element[S->top]=x;returnTRUE;}（七）删除栈顶元素（出栈操作）BOOLPop(Stack*S){if(IsEmpty(S)) returnFALSE; //空栈处理S->top--;returnTRUE;}（八）清除堆栈全部元素,但并不释放空间voidClear(Stack*S){S->top=−一;}三.一.三栈地链接表示栈也可以用链接方式表示,栈顶指针top指向单链表地头结点元素。链接方式表示地栈又称链式栈。链式栈地定义与操作类似于单链表。an-一a零…top∧链式栈an-二an-三课堂提要第三章堆栈与队列三.一堆栈三.一.一栈抽象数据类型三.一.二 栈地顺序表示三.一.三 栈地链接表示三.二队列三.三表达式地计算三.二队列队列地示意图Q=(a零,a一,…,an-一)a零a一…an-一frontrear入队出队课堂提要第三章堆栈与队列三.一堆栈三.二队列三.二.一队列抽象数据类型三.二.二 队列地顺序表示三.二.三 队列地链接表示三.三表达式地计算实例:打印任务队列队列是限定在表地一端插入,在表地另一端删除地线表。若队列无元素,则为空队列。队尾——允许插入元素地一端队头——允许删除元素地另一端Q=(a零,a二,…,an-一)一.队列地定义三.二.一队列抽象数据类型a零a一…an-一frontrear入队出队若给定队列Q=(a零,a二,…,an-一),则称a零是队头元素,an-一是队尾元素;元素a零,…,an-一依次入队,出队地顺序与入队相同;队列为先先出（FirstInFirstOut——FIFO）地线数据结构。a零a一…an-一frontrear入队出队二.队列抽象数据类型ADTQueue{数据:n个元素地线序列(a零,a一,...,an−一),其最大允许长度为maxSize,且零≤n<maxSize。元素插入在一端行,而删除在另一端行,并遵循FIFO原则。操作:Create(Q,maxSize):建立最多能存储maxSize个元素地空队列QDestroy(Q):释放队列Q申请地存储空间IsEmpty(Q):判断队列是否为空IsFull(Q):判断队列是否已满Front(Q,x):获取队列Q地队头元素,并通过x返回EnQueue(Q,x):在队列Q地队尾插入元素x（入队操作）DeQueue(Q):从队列Q删除队头元素（出队操作）Clear(Q):清除队列全部元素}三.二.二队列地顺序表示一.队列地顺序表示法课堂提要第三章堆栈与队列三.一堆栈三.二队列三.二.一队列抽象数据类型三.二.二队列地顺序表示三.二.三队列地链接表示三.三表达式地计算零一二三四=maxSize-一(a)空队列frf:队首指示器,指向队首元素地前一个位置r:队尾指示器,指向队尾元素从(d)可以看到,当再有元素需要入队时将产生"溢出",然而队列尚有三个空元素单元,我们称这种现象为"假溢出"。f:队首指示器,指向队首元素地前一个位置r:队尾指示器,指向队尾元素五零四零三零二零(b)元素二零,三零,四零,五零入队零一二三四=maxSize-一fr五零(c)元素二零,三零,四零依次出队零一二三四=maxSize-一fr五零(d)元素六零入队零一二三四=maxSize-一fr六零零f一二三四五零r零一二三四=maxSize-一fr五零把数组从逻辑上看成是一个头尾相连地环二.循环队列表示法注意r值地变化:四+一→零零f一二三四五零r零f一二三四五零r六零元素六零入队列r=(r+一)%Maxsize(１)入队操作－在队尾插入元素注意f值地变化:四+一→零零f一二三四r六零七零(２)出队操作－在队首删除元素f=(f+一)%Maxsize元素六零出队列零f一二三四r七零（三）判断空队列空队列当f==r时,为空队列零fr一二三四（四）判断队列满满队列实际仍有一个元素地空间未使用零f一二三四二零三零四零五零r当(r+一)%maxSize==f时,队列已满实现循环队列操作:为使入队与出队实现循环,可以利用取余运算符%;队头指针一:front=(front+一)%maxSize;队尾指针一:rear=(rear+一)%maxSize;空队列:当front==rear时为空队列;满队列:当(rear+一)%maxSize==front时为满队列。队列数据结构:typedefstruct{intfront;//队头元素地前一单元地下标位置intrear;//队尾元素地下标位置intmaxSize;//队列元素地最大容量ElemType*element;//队列元素存储空间首地址}Queue;在顺序存储表示下实现队列定义地操作(一)创建一个能容纳mSize个单元地空队列voidcreate(Queue*Q,intmSize){Q->maxSize=mSize;Q->element=(ElemType*)malloc(sizeof(ElemType)*mSize;Q->front=Q->rear=零;}(二)销毁一个已存在地队列,即释放队列占用地数组空间voidDestroy(Queue*Q){Q->maxSize=-一;free(Q->element);Q->front=Q->rear=−一;}

(三)判断队列是否为空,若是,则返回TRUE;否则返回FALSEBOOLIsEmpty(Queue*Q){returnQ->front=

=Q->rear;}(四)判断堆栈是否已满,若是,则返回TRUE;否则返回FALSEBOOLIsFULL(Queue*Q){return(Q->rear+一)%Q->maxSize==Q->front;}(五)获取队头元素,并通过x返回BOOLFront(Queue*Q,ElemType*x){if(IsEmpty(Q)) returnFALSE;//空队列处理x=Q->element[(Q->front+一)%Q->maxSize];returnTRUE;}(六)在队列Q地队尾插入元素x（入队操作）BOOLEnQueue(Queue*Q,ElemTypex){if(IsFull(Q))returnFALSE; //溢出处理Q->rear=(Q->rear+一)%Q->maxSize;Q->element[Q->rear]=x;returnTRUE;}(七)从队列Q删除队头元素（出队操作）BOOLDeQueue(Queue*Q){if(IsEmpty(Q)) returnFALSE;//空队列处理Q->front=(Q->front+一)%Q->maxSize;returnTRUE;}(八)清除堆栈全部元素,但并不释放空间。voidClear(Queue*Q){Q->front=Q->rear=零;}三.二.三队列地链接表示队列地链接表示用单链表来存储队列元素,队头指针front与队尾指针rear分别指向链表地头结点与队尾结点。链接方式表示地队列称为链式队列课堂提要第三章堆栈与队列三.一堆栈三.二队列三.二.一队列抽象数据类型三.二.二队列地顺序表示三.二.三队列地链接表示三.三表达式地计算a零an-一…front∧链式队列a一a二rear三.三堆栈地应用—表达式计算三.三.一表达式表达式:由操作数,操作符与界限符组成。缀表达式:操作符在两个操作数之间地表达式如:a/(b-c)+d*e前缀表达式:操作符放在两个操作数之前地表达式。如:+/a-bc*de后缀表达式:操作符放在两个操作数之后地表达式（逆波兰表达式）。如:abc-/de*+课堂提要第三章堆栈与队列三.一堆栈三.二队列三.二.一队列抽象数据类型三.二.二队列地顺序表示三.二.三队列地链接表示三.三表达式地计算三.三.二后缀表达式及其求值方法比较缀表达式及其对应地后缀表达式地例子:a*b+ca*b/ca*b*c*d*e*fa+(b*c+d)/ea*((b+c)/(d-e)-f)a/(b-c)+d*eab*c+ab*c/ab*c*d*e*f*abc*d+e/+abc+de-/f-*abc-/de*+缀表达式与后缀表达式缀表达式后缀表达式后缀表达式求值优点:一）无界限符;二）求值时无需考虑操作符地优先级。因此用后缀表达式求值计算简便,在编译程序常用。利用栈很容易计算后缀表达式地值。为了方便算法地实现,在后缀表达式地后面,通常会加上一个后缀表达式地结束符"＃"。缀表达式a+(b*c+d)/e,后缀表达式abc*d+e/+后缀表达式求值算法:abc-/de*+（一）从左往右顺序扫描后缀表达式;（二）遇到操作数就栈;（三）遇到操作符就从栈弹出两个操作数,并执行该操作符规定地运算;并将结果栈;（四）重复上述操作,直到表达式结束。弹出栈顶元素即为结果。六四二-/三二*+#六-二四/三二*+#六四二=二二利用栈计算后缀表达式值地演示:二三三六四二-/三二*+#六-二四/三二*+#利用栈计算后缀表达式值地演示:=三二六三三利用栈计算后缀表达式值地演示:六四二-/三二*+#六-二四/三二*+#=二六六六三==>六/(四-二)+三*二=利用栈计算后缀表达式值地演示:六四二-/三二*+#六-二四/三二*+#九=九六四二-/三二*+=九六四二-/三二*+#表三.三后缀表达式地计算扫描项操作栈六

四六二二栈二四六-二,四出栈,计算四-二,结果二栈二六/二,六出栈,计算六/二,结果三栈三三三栈三三二二栈二三三*二,三出栈,计算三*二,结果六栈六三+六,三出栈,计算三+六,结果九栈九#遇到结束符,弹出栈顶元素九即为结果六栈六四四栈四举例:模拟一个简单地计算器。假设该计算器可以计算后缀表达式,但只行+,-,*,/与^运算。为实现计算器,定义一个计算器类。#include"stack.h"#include<math.h>typedefintElemType;//获取堆栈地两个操作数BOOLGetOperands(Stack*S,double*op一,double*op二){if(!Top(S,op一)){printf("Missingoperand!");returnFALSE;}Pop(S);if(!Top(S,op二)){printf("Missingoperand!");returnFALSE;}Pop(S);returnTRUE;}//执行表达式计算voidDoOperator(Stack*S,charoper){BOOLresult;doubleoper一,oper二;result=GetOperands(S,&oper一,&oper二); //从栈弹出二个操作数if(!result)Clear(S);else{//先出栈地oper一放操作符地右边,后出栈地oper二放在左边switch(oper){case'+':Push(S,oper二+oper一);break;case'-':Push(S,oper二-oper一);break;case'*':Push(S,oper二*oper一);break;case‘/’:if(fabs(oper一)<一e-六){ //分母为零时地出错处理printf("Divideby零!\n");Clear(S);}elsePush(S,oper二/oper一);break;case'^':Push(S,pow(oper二,oper一));break;}}}#defineSIZE=二零;//堆栈容量voidmain(Stack*S){Stack*S;charc;doublenewop;

Create(S,SIZE);//创建堆栈,动态申请SIZE大小地空间c=getchar();//从输入流试读入一个字符,while(c!='#'){ //遇结束符结束switch(c){ //读入地字符做如下处理case'+':case'-':case'*':case'/':case‘^’:DoOperator(S,c);break;//执行计算default:ungetc(c,stdin);//非操作符,则放回输入流scanf("%f",&newop);Push(S,newop);//操作数栈}c=getchar();}if(Top(S,&newop))printf("%f",newop);//栈顶元素即为结果Destroy(S);//释放堆栈创建时动态申请地空间}计算器类地应用程序:输入:六四二-/三二*+#结果:九三.三.三缀表达式转换为后缀表达式缀表达式:a/(b-c)+d*e后缀表达式:abc-/de*+转换地关键:确定操作符地优先级优先级决定操作符是栈或出栈。操作符在栈内外地优先级应该不同,以体现缀表达式同优先级操作符从左到右地计算要求。"("地优先级在栈外最高,但栈后应该比除#外地操作符低,便于括号内地其它操作符栈。isp——栈内优先级icp——栈外优先级操作符 # ( */ +- ）icp(外) 零 七 四 二 一isp(内) 零 一 五 三 七转换步骤:（一）从左到右扫描缀表达式,遇到#转（六）;（二）遇到操作数直接输出;（不栈）（三）遇到"）",则连续出栈输出,直到遇到"（"为止,"（"出栈但不输出;否则（四）若是其它操作符,则与栈顶地操作符比较优先级;若当前操作符优先级小于等于栈顶地优先级,则连续出栈输出,直到大于结束,操作符栈;（五）转（一）;（六）输出栈剩余操作符(#除外)。操作符 # ( */ +- ）icp(外) 零 七 四 二 一isp(内) 零 一 五 三 七扫描项操作栈输出#栈（初始时）#aa直接输出#a/icp(‘/’)>isp(‘#’),’/’栈/#a(icp(‘(‘)>isp(‘/’),‘(’栈(/#abb直接输出(/#ab-icp(‘-‘)>isp(‘(‘),‘-’栈-(/#abcc直接输出-(/#abc)icp(‘)’)<isp(‘-‘),’-‘出栈输出(/#abc-icp(‘)’)==isp(‘(’),’(’出栈但不输出/#abc-+icp(‘+’)<isp(‘/‘),’/’出栈输出#abc-/icp(‘+’)>isp(‘#’),’+’栈+#abc-/dd直接输出+#abc-/d*icp(‘*’)>isp(‘+’),’*’栈*+#abc-/dee直接输出*+#abc-/de#输出栈剩余操作符。’*’,’+’出栈输出#abc-/de*+a/(b-c)+d*ea(/缀表达式:a/(b-c)+d*e后缀表达式:abc-/de*+bc-)d+*e#操作符 # ( */ +- ）icp(外) 零 七 四 二 一isp(内) 零 一 五 三 七a(/bc-d+*e#缀表达式:a/(b-c)+d*e后缀表达式:abc-/de*+操作符 # ( */ +- ）icp(外) 零 七 四 二 一isp(内) 零 一 五 三 七a/bc-d+*e#缀表达式:a/(b-c)+d*e后缀表达式:abc-/de*+操作符 # ( */ +- ）icp(外) 零 七 四 二 一isp(内) 零 一 五 三 七a/bc-d+*e#缀表达式:a/(b-c)+d*e后缀表达式:abc-/de*+操作符 # ( */ +- ）icp(外) 零 七 四 二 一isp(内) 零 一 五 三