第四讲-栈与队列教学课件

第四讲栈与队列第四讲栈与队列第四讲栈与队列栈与队列栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。栈和队列被广泛应用于各种程序设计中。3、顺序栈栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。地址连续的存储单元.top321

顺序栈的数据结构：#defineMAXNUM100

typedefintelemtype;/*顺序栈结构定义：*/typedefstructstack_type{elemtypestack[MAXNUM];

inttop;}stacktype;/*定义一个堆栈s;*/stacktypes;进栈操作（插入）退栈操作（删除）【顺序栈的基本操作】顺序栈的基本操作#definetrue1#definefalse0intPush(Stacktype*s,elemtypex){ if(s->top>=MAXNUM-1) return(false); else {s->top++; s->stack[s->top]=x; } returntrue;}进栈操作（插入）顺序栈的基本运算321topx退栈(出栈)操作（删除）elemtypePop(stacktype*s){ if(s->top<0) return(NULL); else {s->top--; return(s->stack[s->top+1]); }}顺序栈的基本运算x321top顺序栈的基本运算【例】将十进制数13转化为二进制数。解答：按除2取余法，得到的余数依次是1、0、1、1，则十进制数转化为二进制数为1101。分析：由于最先得到的余数是转化结果的最低位，最后得到的余数是转化结果的最高位，因此很容易用栈来解决。13263012221011voiddec_to_bin(intN,intB){ inte; SETNULL（s） while(N){ Push(s,N%B); N=N/B; } while(!Empty(s)){ e=Pop(s); printf(“%d”,e); }}【例】将十进制数13转化为二进制数。132630122210114、链栈链栈是运算受限的单链表。栈顶指针就是链表的头指针。DataNextDataNextData^Stopbase链栈的数据结构：Data域：存放结点值的数据域Next域：存放结点的直接后继的地址（位置）的指针域（链域）此结构的C语言描述为：structnode{elemtypedata;

structnode*next;};进栈PUSHvoidpushs(structnode*top,elemtypex){structnode*p;

p=(structnode*)malloc(sizeof(structnode));

p->data=x;

p->next=top;

top=p;}DataNextDataNextData^topbasex^ptop出栈POPelemtypePop(structnode*top){

elemtypex;structnode*p;

if(top==NULL) {printf(“stackisunderflow”); return(NULL);}

x=top->data;p=top;

top=top->next;

free(P);returnx;

}栈的应用1）数据转换2）表达式求值3）括号匹配的检验4）阶乘运算5）迷宫求解迷宫求解

入口出口例：已知入栈序列为ABC，以下序列，哪些是允许的出栈序列？ABC、ACB、BAC、BCA、CBA、CAB。例：计算表达式A＋B*C－D/E运算符栈，用于在表达式处理过程中存放运算符。在开始时，运算符栈中先压入一个表达式结束符“；”。操作数栈，用于在表达式处理过程中存放操作数。从左到右依次读出表达式中的各个符号：若是操作数，则压入操作数栈，依次读下一个符号。若是运算符，则作进一步判断：①若读出运算符的优先级大于运算符栈栈顶运算符的优先级，则将读出的运算符压入运算符栈，并依次读下一个符号。②若读出的是表达式结束符“；”，且运算符栈栈顶的运算符也是表达式结束符“；”，则表达式处理结束，最后的计算结果在操作数栈的栈顶位置。③若读出运算符的优先级不大于运算符栈栈顶运算符的优先级，则从操作数栈连续退出两个操作数，并从运算符栈退出一个运算符，然后作相应的运算（运算符为刚从运算符栈退出的运算符，运算对象为刚从操作数栈退出的两个操作数），并将运算结果压入操作数栈。A＋B*C－D/E；A＋B*C－D/E；A＋B*C－D/E；A＋B*C－D/E；voidmain(){intn;n=Factorial(4);cout<<"4!="<<n<<endl;}longFactorial(longn){if(n==0)return1;elsereturnn*Factorial(n-1);}例：用递归求4!★每次调用都将返回地址addi进栈。★每次返回将地址addi出栈，把这级调用的结果值返回到上级调用表达式处。★调用是将问题逐次分解为较简单的问题，直到满足递归结束条件，能求出确定值为止。★递归过程的运行要有较大的空间和时间开销。topstack{…return4*F(3);}add1F(4)-1012345（设add1～add4

是F(n-1)调用编译程序编码在内存的地址）add1{…return3*F(2);}add2F(3)add3{…return1*F(0);}add4F(1)add4{return1;}if(n==0)F(0)add2{…return2*F(1);}add3F(2)top二、队列（Queue）队列是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。a1a2…an出队入队队尾队头FIFO队列的基本逻辑运算1）SETNULL（Q）//置空队。构造一个空队列Q。2）Empty（Q）//判队空。3）ENTER（Q，x）//｛入队列｝。Q非满，则将元素x插入Q的队尾。此操作简称入队。4）DELETE（Q）//｛出队列｝。若队列Q非空，则删去Q的队头元素，并返回该元素。此操作简称出队。5）GETHEAD（Q）//{取对头元素}若队列Q非空，则返回队头元素，但不改变队列Q的状态。顺序队列定义：队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。顺序队列的基本操作①入队时：将新元素插入rear所指的位置，然后rear加1。②出队时：删去front所指的元素，然后将front加1并返回被删元素。注意： ①当头尾指针相等时，队列为空。 ②在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。【顺序队列基本操作】队列的类型定义#defineMAXSIZE100/*最大队列长度*/typedefstructqueue_type{ elemtypequeue[MAXSIZE+1]

intfront;

/*头，若队列不空，指向队列头元素*/

intrear;

/*尾，若队列不空，指向队列尾元素的下一个位置*/}queuetype;queuetypeQ;入队列操作：#definetrue1#definefalse0intenter(queuetype*q,elemtypex){if(q->rear>=MAXNUM) return(false);else {q->rear++;q->queue[q->rear]=x; returntrue; }}BCDfrontrearx出队列操作：elemtypedelete(queuetype*q){ if(q->front==q->rear return(NULL); else {q->front++; return(q->queue[q->front]); }}BCDrearfront顺序队列中的溢出现象①“下溢”现象 当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。②“真上溢”现象

当队列满时，做进队运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。③“假上溢”现象 由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。【例】假设在下列满队列中先执行出队操作，然后再执行入队操作，结果便会是一种假溢出现象。出队两个元素后：再要进行入队操作：（报告失败）

可见，这种假溢出现象严重影响了队列的利用率，所以必须解决这一现象。循环队列（CircularQueue）为充分利用向量空间，克服"假上溢"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列。【循环队列操作】

循环队列边界条件处理循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。循环队列边界条件处理解决这个问题的方法至少有三种：

①另设一布尔变量以区别队列的空和满；②少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；③使用一个计数器记录队列中元素的总数（即队列长度）。循环队列入队操作：#definetrue1#definefalse0intenter(queuetype*q,elemtypex){ if((q->rear+1)%MAXNUM==q->front) return(false);/*队列已满*/ else {q->rear=(q->rear+1)%MAXNUM; q->queue[q->rear]=x; returntrue; }}强调循环队列出队操作：elemtypedelete(queuetype*q){if(q->font==q->rear return(NULL);else {q->front=(q->front+1)%MAXNUM; return(q->queue[q->front]); }}链队列队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。DataNextDataNextData^Q.front队头队尾DataNextQ.rear链队列的结构类型定义structnode{elemtypedata;structnode*next;};structqtype{node*front;node*rear;}q;入队Aq->frontq->rearBC^xp^voidenter(qtype*q,elemtypex){node*p;p=(node*)malloc(sizeof(node));p->data=x;p->next=NULL;/*新的队尾结点*/q->rear->next=p;/*链入队列中*/q->rear=p;/*修改队尾指针*/}p->data=x;p->next=NULL;q->rear->next=p;q->rear=p;强调在队尾插入！Aq->frontq->rearBC^xp^elemtypedelete(qtype*q){node*p;elemtypex;if(q->front->next==NULL) return(NULL);/**/else {p=q->front; x=p->data; q->front=p->next; if(p->next==NULL) q->rear=q->front; free(p); return(x); }}出队Aq->frontq->rearBCDE^px=‘A’DataNextDataNextData^q->front队头DataNext队尾q->rearp=q->front;x=p->data;q->front=p->next;P队头q->front在队头删除！强调队列的应用1、键盘缓冲——外设与处理机的速度匹配2、作业队列——处理机对作业的“选择”小结1)、堆栈的定义、特性、进栈操作、出栈操作、以及典型应用算法；2)、队列的定义、特性，队列的出入操作、溢出现象以及循环队列；3)、队列的应用举例。作业1、循环队列的优点是什么？如何判别它的空和满？写出循环队列的入队和出队函数。2、对于循环队列（非链队列），写出求队列长度的公式。3、编程序实现进制转换程序。4、设计算法判断一个算术表达式的圆括号是否正确配对。（提示：对表达式进行扫描，凡遇“(”就进栈，遇“)”就退掉栈顶的“(”，表达式被扫描完毕，栈应为空。）思考：1、有abcd四个元素在一栈中，分别出栈后通过一队列，进入另一栈中，则在另一栈中的元素从下往上排列顺序如何？2、有a、b、c、d、e依次进栈，问出栈的序列不可能是哪些？(a)edcba