(栈和队列)课件

运算受限的线性表栈和队列Chapter

3DataStructuresandAlgorithmAnalysis运算受限的线性表Cha主要内容栈的逻辑结构定义栈的存储结构及其运算的实现队列的逻辑结构定义队列的存储结构及其运算的实现主要内容栈的逻辑结构定义学习目标掌握栈和队列的特点及操作方法能在实际应用中正确选用它们学习目标掌握栈和队列的特点及操作方法3.1CONTENTS栈——按照先入后出的方式管理的线性表队列——按照先入先出的方式管理的线性表3.23.3本章小结3.1CONTENTS栈——按照先入后出的方式管理的线性表队日常生活中的栈先入后出日常生活中的栈先入后出3.1栈3.1.13.1.23.1.33.1.4栈处理模式的引入栈的逻辑结构栈的存储结构设计栈的操作3.1.5各种栈结构的比较栈的应用举例3.1.63.1栈3.1.13.1.23.1.33.1.4栈处理模式的3.1栈3.1.13.1.23.1.33.1.4栈处理模式的引入栈的逻辑结构栈的存储结构设计栈的操作3.1.5各种栈结构的比较栈的应用举例3.1.63.1栈3.1.13.1.23.1.33.1.4栈处理模式的栈引例1——Word中的误操作8abcd操作顺序——abcd撤销顺序——dcba栈引例1——Word中的误操作8abcd操作顺序——abcd栈引例2——括号匹配问题编号0123456789括号{{{}[]}()}pq设计思路用p记录左括号的最新位置，用q指向当前新进入的括号，将p与q的内容比对，如果相匹配，则删除该左括号，p后退一位，即在从左至右的扫描过程中只保存遇到的左括号。问题编译器判断出现在字符串中的括号是否配对测试用例：{{{}[]}()}栈引例2——括号匹配问题编号0123456789括号{{{}10编号0123456789括号{{{}[]}()}10编号0123456789括号{{{}[]}()}栈引例3——函数的递归调用11递归函数求4!234运算中间量的存取栈引例3——函数的递归调用11递归函数求4!234运算中间栈引例4——函数的嵌套调用问题12栈引例4——函数的嵌套调用问题12引例特点归结13数据的处理过程具有“后进先出”的特性栈引例特点归结13数据的处理过程具有“后进先出”的特性栈3.1栈3.1.13.1.23.1.33.1.4栈处理模式的引入栈的逻辑结构栈的存储结构设计栈的操作3.1.5各种栈结构的比较栈的应用举例3.1.63.1栈3.1.13.1.23.1.33.1.4栈处理模式的15

栈（Stack）是一种特殊的线性表，它所有的插入和删除都限制在表的同一端进行。定义栈的逻辑结构15栈（Stack）是一种特殊的线性表，它16要对一个栈的状态进行标示，至少需要几个参数栈顶top

栈底bottom出栈Pop进栈Pusha1anan-1…栈的逻辑结构栈中允许进行插入、删除操作的一端叫做栈顶（Top），另一端则叫做栈底（Bottom）。当栈中没有元素时，称之为空栈。思考&讨论16要对一个栈的状态进行标示，至少需要几个参数栈顶栈底出栈栈的操作示意17栈空：top=-1栈顶指针top指向栈顶元素的位置约定栈的操作示意17栈空：top=-1栈顶指针top指向栈顶元素栈的运算初始化

建立一个空栈判栈空判断栈是否为空取栈顶元素取得栈顶元素的值压栈在栈中插入元素使其成为新的栈顶元素弹栈删除栈S的栈顶元素栈的运算初始化建立一个空栈判栈空判断栈是否为空取栈3.1栈3.1.13.1.23.1.33.1.4栈处理模式的引入栈的逻辑结构栈的存储结构设计栈的操作3.1.5各种栈结构的比较栈的应用举例3.1.63.1栈3.1.13.1.23.1.33.1.4栈处理模式的特殊线性表栈栈的存储结构设计运算限定在线性表一端存储结构采用线性表的各种方案逻辑关系线性栈既然是一种特殊的线性表，其存储结构可采用线性表的存储形式——顺序结构和链式结构。特殊栈栈的存储结构设计运算限定在线性表一端存储结构采顺序栈21顺序表顺序栈用一块连续空间顺序存放线性表元素用一块连续空间顺序存放栈元素顺序栈21顺序表顺序用一块连续空间顺序存放线性表元素用一块连22#defineSTACK_SIZE64；//栈容量设置typedefstructStack{datatypestack[STACK_SIZE];//栈空间inttop;//栈顶指针}SeqStack;顺序栈topSTACK_SIZE-1…nn-1ann-2an-1……1a20a1顺序栈的图示栈空：top=-1栈满top=STACK_SIZE-1数据结构设计约定22#defineSTACK_SIZE64；//栈容量设23typedefintdatatype;typedefstructnode//结点{datatypedata;structnode*next;//链指针}LinkStack; //链栈结点结构类型定义LinkStack*top;//栈顶指针datanexttop栈顶栈底an-1a1an∧链式栈数据结构设计23typedefintdatatype;datan3.1栈3.1.13.1.23.1.33.1.4栈处理模式的引入栈的逻辑结构栈的存储结构设计栈的操作3.1.5各种栈结构的比较栈的应用举例3.1.63.1栈3.1.13.1.23.1.33.1.4栈处理模式的顺序栈的基本操作25初始化判断栈空进栈出栈取栈顶元素顺序栈的基本操作25初始化判断栈空进栈出栈取栈顶元素顺序栈的基本操作26初始化判断栈空进栈出栈取栈顶元素顺序栈的基本操作26初始化判断栈空进栈出栈取栈顶元素顺序栈的基本操作——初始化27问题对栈初始化，将栈顶指针置为-1。测试情形输入预期结果正常情形顺序栈地址栈顶指针置为栈空位置边界及异常情形无无测试样例设计顺序栈的基本操作——初始化27问题对栈初始化，将栈顶指针置为顺序栈的基本操作——初始化28功能描述输入输出栈初始化initialize_SqStack顺序栈地址SeqStack*无函数名形参函数类型函数框架设计/*=======================================函数功能：顺序栈置空栈函数输入：顺序栈地址函数输出：无=========================================*/voidinitialize_SqStack(SeqStack*s){s->top=-1;}顺序栈的基本操作——初始化28功能描述输入输出栈初始化ini顺序栈的基本操作29初始化判断栈空进栈出栈取栈顶元素顺序栈的基本操作29初始化判断栈空进栈出栈取栈顶元素顺序栈的基本操作——判断栈空30问题判断栈空，查看栈中是否有元素。测试情形栈状态预期结果一般情况栈非空返回栈非空标志栈空返回栈空标志测试样例设计顺序栈的基本操作——判断栈空30问题判断栈空，查看栈中是否有顺序栈的基本操作——判断栈空31功能描述输入输出判栈空StackEmpty_SqStack顺序栈地址Seqstack*栈状态标志int（栈空：1；非空：0）函数名形参函数类型/*=======================================函数功能：判断顺序栈是否为空函数输入：顺序栈地址函数输出：1——栈空；0——栈非空=========================================*/intStackEmpty_SqStack(SeqStack*s){return(s->top==-1);}函数框架设计顺序栈的基本操作——判断栈空31功能描述输入输出判栈空Sta顺序栈的基本操作32初始化判断栈空进栈出栈取栈顶元素顺序栈的基本操作32初始化判断栈空进栈出栈取栈顶元素33顺序栈的基本操作——进栈问题将值为x的元素放入栈中。33顺序栈的基本操作——进栈问题将值为x的元素放入栈中。顺序栈的基本操作——进栈34测试情形栈状态预期结果正常情形栈未满返回正常进栈操作标志异常情形栈满返回上溢标志功能描述输入输出进栈Push_SqStack顺序栈地址

SeqStack*新元素值datatype操作状态int（正常：1；上溢：0）函数名形参函数类型测试样例设计函数框架设计顺序栈的基本操作——进栈34测试情形栈状态预期结果正常情形栈顺序栈的基本操作——进栈35顶部伪代码描述第一步细化在顺序栈栈顶位置插入新元素x若栈满则returnFALSE修改栈顶指针top++在栈顶指针指向位置放入xreturnTRUE算法设计顺序栈的基本操作——进栈35顶部伪代码描述第一步细化在顺序栈顺序栈的基本操作——进栈/*=======================================函数功能：顺序栈进栈操作函数输入：顺序栈地址，进栈元素值函数输出：0——栈上溢，操作失败；1——操作正常=========================================*/intPush_SqStack(SeqStack*s,datatypex){if(s->top==STACK_SIZE-1)returnFALSE;//栈上溢else{s->top++;s->stack[s->top]=x;}returnTRUE;}36顺序栈的基本操作——进栈/*================进栈函数结构设计讨论37功能描述输入输出压栈push顺序栈内容正常栈结构地址新元素值上溢NULL函数名形参函数类型功能描述输入输出压栈push顺序栈内容操作状态1：正常新元素值0：上溢函数名形参函数类型【结论】在函数的结构设计中，要注意所用实现语言的特点，参数传递的单向与双向限制，根据函数功能的要求，选用合适的信息传递方式，切不可随意确定函数的参数。12下面两种函数结构设计是否能完成进栈的功能？思考&讨论进栈函数结构设计讨论37功能描述输入输出压栈push顺序栈内顺序栈的基本操作38初始化判断栈空进栈出栈取栈顶元素顺序栈的基本操作38初始化判断栈空进栈出栈取栈顶元素顺序栈的基本操作——出栈3939为什么出栈操作后不真正删除an问题删除栈顶数据元素思考&讨论顺序栈的基本操作——出栈3939为什么出栈操作后不真正删除a顺序栈的基本操作——出栈40测试情形状态输入预期结果正常情形栈非空栈顶指针>0返回栈顶元素值返回出栈操作正常标志边界情况栈顶指针=0异常情形栈空栈顶指针=-1返回出栈操作异常标志功能描述输入输出出栈Pop_SqStack顺序栈地址SeqStack*(出栈元素值datatype*)操作状态int(正常：1；下溢：0)出栈元素值datatype*函数名形参函数类型测试样例设计函数框架设计顺序栈的基本操作——出栈40测试情形状态输入预期结果正常情形顺序栈的基本操作——出栈41顶部伪代码描述第一步细化删除栈顶数据元素若栈空，则returnFALSE;记录栈顶元素值x修改栈顶指针：top--returnTRUE算法设计顺序栈的基本操作——出栈41顶部伪代码描述第一步细化删除栈顶顺序栈的基本操作——出栈42/*=====================================函数功能：顺序栈出栈操作函数输入：顺序栈地址，（出栈元素地址）函数输出：0——栈下溢，操作失败；1——操作正常=========================================*/intPop_SqStack(SeqStack*s,datatype*x){if(s->top==-1)returnFALSE;else{*x=s->stack[s->top];s->top--;}returnTRUE;}顺序栈的基本操作——出栈42/*==============出栈函数设计的讨论

下面的出栈函数设计上有什么问题？datatypepop(SeqStack*s){datatypetemp;if(StackEmpty(s)){return(-1)；}else{s->top--;return(s->stack[s->top+1]);}}//POPS43输出中栈元素的类型datatype不一定是整型，无论是正常还是异常情形的返回，对函数类型而言都只能是一种类型，故在“下溢”这种异常情形时，设计返回“-1”是不恰当的。功能描述输入输出出栈pop顺序栈地址SeqStack*正常：出栈元素值datatype下溢：-1函数名形参函数类型函数框架设计思考&讨论出栈函数设计的讨论下面的出栈函数设计顺序栈的基本操作44初始化判断栈空进栈出栈取栈顶元素顺序栈的基本操作44初始化判断栈空进栈出栈取栈顶元素顺序栈操作——取栈顶元素45问题取栈顶元素的值，而不改变栈顶指针。/*=======================================函数功能：顺序栈取栈顶元素函数输入：顺序栈地址，（栈元素地址）函数输出：0——栈下溢，操作失败；1——操作正常=========================================*/intGet_SqStack(SeqStack*s,datatype*x){if(s->top==-1)returnFALSE;else{*x=s->stack[s->top];}returnTRUE;}与出栈函数类似，只是不修改栈顶指针顺序栈操作——取栈顶元素45问题取栈顶元素的值，而不改变栈顶链栈46链表链栈离散的方式存储线性表元素离散的方式存储栈元素顺序栈存在栈满以后就不能再进栈的问题，这是因为用了定长的数组存储栈的元素。解决的方法，可以使用链式存储结构，让栈空间可以动态扩充。链栈46链表链离散的方式存储离散的方式存储顺序栈存在栈满以链栈47栈顶指针就是链表的头指针栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行链栈47栈顶指针就是链表的头指针栈的链式存储结构称为链栈，它链栈数据结构的描述48typedefintdatatype;typedefstructnode //结点{datatypedata;structnode*next; //链指针}LinkStack;LinkStack*top; //栈顶指针链栈数据结构的描述48typedefintdatatyp链栈的基本操作49进栈出栈链栈的基本操作49进栈出栈链栈的基本操作——进栈50问题在链栈栈顶位置插入值为x的新结点链栈的基本操作——进栈50问题在链栈栈顶位置插入值为x的新结链栈的基本操作——进栈51测试情形状态预期结果一般情况链栈非空压栈成功返回栈顶指针特例情况链栈为空功能描述输入输出进栈PushLStack(栈顶指针LinkStack*)栈顶指针LinkStack*进栈元素值datatype函数名形参函数类型返回栈的结构指针是否有必要？必须的（可做现场调试）思考&讨论测试样例设计函数框架设计链栈的基本操作——进栈51测试情形状态预期结果一般情况链栈非链栈的基本操作——进栈顶部伪代码第一步细化在链栈栈顶位置插入值为x的新结点申请新结点p，并赋值为x；将p结点链在栈顶修改栈顶指针返回栈顶指针52算法设计链栈的基本操作——进栈顶部伪代码第一步细化在链栈栈顶位置申请链栈的基本操作——进栈/*==================================================函数功能：链栈的进栈操作函数输入：(栈顶指针)、进栈元素函数输出：栈顶指针===================================================*/LinkStack*PushLStack(LinkStack*top,datatypex){LinkStack*p;p=malloc(sizeof(LinkStack));p->data=x;p->next=top;top=p;returntop;}53传址调用是在同地址下的内容传递，若子函数中修改了传递的地址，则此被修改的地址是无法通过“传址”传送的。top的指向发生了变化链栈的基本操作——进栈/*=================链栈的基本操作——出栈54问题在链栈栈顶位置删除结点仍然要判断栈空链栈的基本操作——出栈54问题在链栈栈顶位置删除结点仍然要判链栈的基本操作——出栈55测试情形输入/状态预期结果正常情形栈非空返回栈顶指针、栈顶元素值异常情形栈空返回NULL功能描述输入输出出栈PopLStack栈顶指针LinkStack*(栈顶元素值datatype*)栈顶指针LinkStack*栈顶元素值datatype*函数名形参函数类型测试样例设计函数框架设计链栈的基本操作——出栈55测试情形输入/状态预期结果正常情形链栈的基本操作——出栈56顶部伪代码第一步细化在链栈栈顶位置删除结点若栈非空记录栈顶结点地址p，元素值datap修改栈顶指针top释放结点p算法设计链栈的基本操作——出栈56顶部伪代码第一步细化在链栈栈顶位置链栈的基本操作——出栈/*==================================================函数功能：链栈的出栈操作函数输入：栈顶指针、（出栈元素）函数输出：栈顶指针===================================================*/LinkStack*PopLStack(LinkStack*top,datatype*datap){LinkStack*p;if(top!=NULL){*datap=top->data;p=top;top=top->next;free(p);}returntop;}57PopLStack函数中栈空的情形可以一并处理吗？链栈的基本操作——出栈/*=================3.1栈3.1.13.1.23.1.33.1.4栈处理模式的引入栈的逻辑结构栈的存储结构设计栈的操作3.1.5各种栈结构的比较栈的应用举例3.1.63.1栈3.1.13.1.23.1.33.1.4栈处理模式的顺序栈的讨论595959

时间效率空间效率顺序栈所有操作都只需常数时间顺序栈须长度固定链式栈链式栈在栈顶操作，效率很高

链式栈的长度可扩展，但增加结构性开销说明顺序栈和链式栈在时间效率上难分伯仲实际应用中，顺序栈比链式栈用得更广泛些

顺序栈的缺点是栈满后不能再进栈，链栈无栈满问题（系统资源足够时）。顺序栈的讨论595959

时间效率空间效率顺序栈所有操作都只3.1栈3.1.13.1.23.1.33.1.4栈处理模式的引入栈的逻辑结构栈的存储结构设计栈的操作3.1.5各种栈结构的比较栈的应用举例3.1.63.1栈3.1.13.1.23.1.33.1.4栈处理模式的凡应用问题求解的过程具有"后进先出"的天然特性的话，则求解的算法中也必然需要利用"栈"。由于栈的操作具有后进先出的固有特性，致使栈成为程序设计中的有用工具STACK栈凡应用问题求解的过程具有"后进先出"的天然特性的话，则求解的栈的应用1——数制转换62有人可能会说，这个题目用数组直接实现不也很简单吗？可以试一下利用数组重新写这个算法，那么就能体会到在这个算法中用栈的好处了。

思考&讨论

(1348)10=(2504)8顺序栈与顺序表实现数制转换的区别是什么？栈的应用1——数制转换62有人可能会说，这个题目用数组直接实栈的应用1——数制转换63//对于输入的任意一个非负十进制整数n，打印输出与其等值的八进制数voidconversion(SeqStack*S,intn){ inte; while(n) { Push_SqStack(S,n%8);//"余数"入栈

n=n/8;//非零"商"继续运算

} while(!StackEmpty_SqStack(S))//栈非空，显示结果

{ Pop_SqStack(S,&e); printf("%d",e); }}栈的应用1——数制转换63//对于输入的任意一个非负十进制整64栈的应用2——栈实现函数的递归递归的实现方法(1)递归边界条件：iterate=value当value=1(2)递归继续条件

iterate=value+iterate(value-1)当value>1函数功能：实现等差级数1+2+3+...+value的求和问题intiterate(intvalue){if(value==1)return1;returnsum=value+iterate(value-1);}64栈的应用2——栈实现函数的递归递归的实现方法函数功能：实65Exp=1+(5-6/2)*3栈的应用3——表达式求值机器遇到表达式有括号时如何方便处理？在源程序编译中，若要把一个含有表达式的赋值语句翻译成正确求值的机器语言，首先应正确地解释表达式，它的实现方法是栈的一个典型的应用实例。通过对处理表达式的讨论，可以帮助我们进一步了解栈的性能。65Exp=1+(5-6/2)*3栈的应用3——表达式解决算数运算关键问题不需要括号——按照表达式顺序求值，由栈记录中间结果括号操作符的优先级操作符优先级解决算数运算关键问题不需要括号——按照表达式顺序求值，由栈记67栈的应用3——表达式求值算数表达式示例表示方法求值方向中缀式

a*b+(cd/e)*fS1OPS2从左至右前缀式+*ab

*

c/defOPS1

S2从右至左后缀式

ab*

cde/f*+S1

S2OP从左至右算数表达式表示方法在计算机中，用前缀和后缀表达式，可以简化运算过程。前缀式运算规则：连续出现的两个操作数和在它们之前且紧靠它们的运算符

构成一个最小表达式；后缀式运算规则：每个运算符和在它之前出现且紧靠它的两个操作数

构成一个最小表达式。67栈的应用3——表达式求值算数表达式示例表示方法求值方向中后缀表达式计算68后缀式的运算规则从左至右扫描，每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。后缀表达式（PostfixNotation）

———运算符在操作数之后运算符紧跟在两个操作数之后的表达式叫后缀表达式如：中缀表达式A*B/C对应的后缀表达式为AB*C/后缀表达式计算68后缀式的运算规则后缀表达式（Postfix后缀表达式计算69后缀表达式的计算方法例为算法简单起见，只考虑操作数为一位整数的情形。表达式：1+(5-6/2)*3后缀表达式：1562/-3*+#注：为运算方便在后缀表达式最后加一个结束标志‘#’运算符操作数结果后缀表达式变化说明/626/2=3153–3*+#5后面的3是6/2的结果-535-3=2123*+#1后面的2是5-3的结果*232*3=616+#1后面的6是2*3的结果+1677#7是1+6的结果后缀表达式计算69后缀表达式的计算方法例为算法简单起见，只考后缀表达式计算70从左到右扫描后缀表达式遇到操作数压栈遇到运算符，弹栈两次取数运算，结果压栈遇到#，弹栈取出运算结果，结束功能描述输入输出后缀表达式求值Value后缀表达式数组char运算结果int*(运算结果int*)函数名形参函数类型函数框架设计算法设计后缀表达式计算70从左到右扫描后缀表达式遇到操作数压栈遇到运后缀表达式计算71/*==================================================函数功能：后缀表达式求值函数输入：后缀表达式数组、（运算结果）函数输出：无===================================================*/后缀表达式计算71/*===================表达式计算归结72后缀表达式求值法，基于栈的操作特性，无需括号也很容易区分运算的顺序，因此这种后缀表达式法被大量使用。（1）后缀表达式没有括号。（2）不存在优先级的差别。（3）计算过程完全按照运算符出现的先后次序进行。表达式计算归结72后缀表达式求值法，基于栈的操作特性，无需括中缀转后缀规则将结束标志#压栈从左至右扫描中缀表达式遇到元素操作处理操作数保存至表达式数组suffix左括号进栈S运算符栈空或栈顶为左括号进栈S优先级>栈顶的进栈S优先级<=栈顶的（1）弹栈，保存到suffix（2）进栈S右括号弹栈直到匹配的右括号弹出#栈内元素全部弹出保存至数组，结束若弹栈的元素为左括号则继续扫描表达式73中缀转后缀规则将结束标志#压栈从左至右遇到元素操作处理操作数中缀转后缀例子3-2【例3-2】将中缀表达式“1+2-3#”转换为后缀表达式74扫描到的元素表达式数组suffix运算符栈S说明11空操作数保存+1+栈空，运算符直接入栈212+操作数保存-12+-‘-’优先级与栈顶的‘+’号同级‘+’弹栈至表达式数组；‘-’入栈312+3-操作数保存#12+3-空全部弹栈中缀转后缀例子3-2【例3-2】将中缀表达式“1+2-3#”中缀转后缀例子3-3扫描到的元素表达式数组suffix运算符栈S说明11空操作数保存+1+栈空，运算符直接入栈(1+(左括号，直接入栈(1+((左括号，直接入栈212+((操作数保存+12+((+栈顶为左括号，运算符直接入栈3123+((+操作数保存)123++(遇右括号，弹栈直到匹配的右括号弹出×123++(×栈顶为左括号，运算符直接入栈4123+4+(×操作数保存)123+4×+右括号，弹栈直到匹配的右括号弹出-123+4×+--与+优先级相同，因此弹出+，再压入-5123+4×+5-操作数保存#123+4×+5-空弹出S中剩余运算符结果123+4×+5-

75【例3-3】将中缀表达式“1+((2+3)×4)-5#”转换为后缀表达式中缀转后缀例子3-3扫描到的元素表达式数组suffix运算符前缀表达式76前缀式的运算规则连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式前缀表达式（PrefixNotation）

———运算符在操作数之前运算符位于操作数之前的表达式称为前缀表达式如：中缀表达式“A-B*C+D”转换为前缀表达式为：“+-A*BCD”前缀表达式76前缀式的运算规则前缀表达式（PrefixNo中缀转前缀将结束标志#压栈从右至左扫描中缀表达式遇到元素操作处理操作数保存至数组右括号压栈运算符栈空或栈顶为右括号压栈优先级>=栈顶的压栈优先级<栈顶的（1）弹栈，保存到数组（2）压栈左括号弹栈#栈内元素全部弹出保存，结束若弹栈的元素为右括号则继续扫描表达式77中缀转前缀将结束标志#压栈从右至左扫描中缀表达式遇到元素操作中缀转前缀例子扫描到的元素表达式数组运算符栈S说明55空操作数保存-5-栈空，运算符直接入栈)5-)右括号直接入栈454-)操作数直接入栈×54-)×栈顶是右括号，直接入栈)54-)×)右括号直接入栈3543-)×)操作数+543-)×)+栈顶是右括号，直接入栈25432-)×)+操作数(5432+-)×左括号，弹栈直到匹配的右括号弹出(5432+×-左括号，弹栈直到匹配的右括号弹出+5432+×-+优先级与-相同，入栈15432+×1-+操作数#5432+×1+-空弹出栈中剩余的运算符结果-+1×+2345

78【例3-4】将中缀表达式“#1+((2+3)×4)-5”转换为前缀表达式中缀转前缀例子扫描到的元素表达式数组运算符栈S说明55空操作3.1CONTENTS栈——按照先入后出的方式管理的线性表队列——按照先入先出的方式管理的线性表3.23.3本章小结3.1CONTENTS栈——按照先入后出的方式管理的线性表队80先入先出生活中的队列80先入先出生活中的队列3.2队列3.2.13.2.23.2.33.2.4队列处理模式的引入队列的逻辑结构队列的顺序存储结构顺序队列的基本操作3.2.5队列的链式存储结构链队列的基本操作3.2.63.2.7各种队列结构的比较队列的应用举例3.2.83.2队列3.2.13.2.23.2.33.2.4队列处理3.2队列3.2.13.2.23.2.33.2.4队列处理模式的引入队列的逻辑结构队列的顺序存储结构顺序队列的基本操作3.2.5队列的链式存储结构链队列的基本操作3.2.63.2.7各种队列结构的比较队列的应用举例3.2.83.2队列3.2.13.2.23.2.33.2.4队列处理队列引例1——计算机中数据的异步处理电子商务系统中的缓冲队列不能实时处理邮件服务器中的邮件队列

客户机/服务器系统中的用户请求队列123对数据资源的请求将严格按照先后顺序进行,用于对事件的调度并可起到I/O缓冲的作用队列引例1——计算机中数据的异步处理电子商务系统中的缓冲队列电子商务系统中的缓冲队列84电子商务系统中的缓冲队列84客户机/服务器系统85客户机/服务器系统85客户机/服务器响应模式86客户机/服务器响应模式86队列引例2——杨辉三角形87111121133114641二项式(a+b)的n（n=1,2,3...）次方展开后各项的系数排成的三角形输出n行杨辉三角形队列引例2——杨辉三角形871二项式(a+b)的n（n=1队列引例2——杨辉三角88queue[]0110121013310…

f

r

queue[]01101

111121133114641queue[rear]=queue[front-1]+queue[front]若(queue[front]==0)queue[++rear]=0队列引例2——杨辉三角88queue[]011012101队列引例2——杨辉三角89queue[]0110121013310…

f

r

queue[]011012

111121133114641queue[rear]=queue[front-1]+queue[front]若(queue[front]==0)queue[++rear]=0队列引例2——杨辉三角89queue[]011012101队列引例2——杨辉三角90queue[]0110121013310…

fr

queue[]011012

1

0

1

3

3

1

0

111121133114641queue[rear]=queue[front-1]+queue[front]若(queue[front]==0)queue[++rear]=0队列引例2——杨辉三角90queue[]011012101队列引例2——杨辉三角91queue[]0110121013310…

fr

queue[]011012

1

0

1

3

3

1

0

111121133114641queue[rear]=queue[front-1]+queue[front]若(queue[front]==0)queue[++rear]=0队列引例2——杨辉三角91queue[]011012101队列引例2——杨辉三角92queue[]0110121013310…

f

r

queue[]011012

1

0

1

3

3

1

0

111121133114641queue[rear]=queue[front-1]+queue[front]若(queue[front]==0)queue[++rear]=0队列引例2——杨辉三角92queue[]0110121013.2队列3.2.13.2.23.2.33.2.4队列处理模式的引入队列的逻辑结构队列的顺序存储结构顺序队列的基本操作3.2.5队列的链式存储结构链队列的基本操作3.2.63.2.7各种队列结构的比较队列的应用举例3.2.83.2队列3.2.13.2.23.2.33.2.4队列处理队列的逻辑结构94队列规则排列顺序：结点排成一队，后来的排在队尾。处理过程：在队头处理事件；队列中有元素则一直处理，直

至队空或发生中断事件。数据结构中的队列，即是把一个一个的结点按照某种顺序排列，对其处理的过程和日常生活中的队列是一样的。队列的逻辑结构94队列规则数据结构中的队列，即是把一个一个的95(插入)(删除)

a1

a2

a3

……an入队列队头队尾出队列队列只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

定义

95(插入)(删除)a1a2a3…队列的基本操作96置空队列将已有队列置空判空操作若队列为空，则返回的值为1，否则为0出队操作队列非空，返回队头元素值，修改队头指针入队操作将数据x插入到队尾，修改队尾指针取队头元素

队列非空，返回队列头元素值，不删队头元素队列的基本操作96置空队列将已有队列置空判空操作若队列为3.2队列3.2.13.2.23.2.33.2.4队列处理模式的引入队列的逻辑结构队列的顺序存储结构顺序队列的基本操作3.2.5队列的链式存储结构链队列的基本操作3.2.63.2.7各种队列结构的比较队列的应用举例3.2.83.2队列3.2.13.2.23.2.33.2.4队列处理特殊线性表队列队列的存储结构设计运算限定在线性表一端输入，

另一端输出存储结构采用线性表的各种方案逻辑关系线性队列既然是一种特殊的线性表，其存储结构可采用线性表的存储形式——顺序结构和链式结构。特殊队列队列的存储结构设计运算限定在线性表一端输入，存储顺序队列99顺序表顺序队列用一块连续空间顺序存放线性表元素用一块连续空间顺序存放队列元素顺序队列sequentialqueue顺序队列99顺序表顺序用一块连续空间顺序存放线性表元素用一块队头队尾a1a2a3…an队列状态要对一个队列的变化状态进行标示，至少需要几个参数？问题1队列结构设计问题顺序队列结构设计讨论队头队尾a1a2a3…an队列状态要对一个队列的变化状态进行a1a2a3…ai队列满队列空非空非满012…MAX-1a1a2a3…ai…an队列各种可能的状态顺序队列结构设计讨论队头指针、队尾指针究竟指向什么位置合适？问题2设计的方案要适用所有可能的情况a1a2a3…ai队列满队列空非空非满012…MAX-1a1012…MAX-1a1a2a3…aifrontrear队列状态1顺序队列结构设计讨论队列元素出队情形012…MAX-1a1a2a3…aifrontrear队列状012…MAX-1a1a2a3…aifrontrear队列状态2顺序队列结构设计讨论队列元素出队情形a1出队012…MAX-1a1a2a3…aifrontrear队列状012…MAX-1a1a2a3…aifrontrear队列状态3顺序队列结构设计讨论已经出队的元素是否需要删除？问题3a2出队结论1顺序队列中已经出队的元素不需要删除012…MAX-1a1a2a3…aifrontrear队列状队列状态4a1a2a3…aiai+1012…MAX-1顺序队列结构设计讨论队列元素入队情形frontrear队列状态4a1a2a3…aiai+1012…MAX-1顺序队a1a2a3…aiai+1...012…MAX-1顺序队列结构设计讨论队列元素入队情形frontrear队列状态4a1a2a3…aiai+1...012…MAX-1顺序队列结a1a2a3…aiai+1...am012…MAX-1顺序队列结构设计讨论队列元素入队情形frontreara1a2a3…aiai+1...am012…MAX-1顺序队a1a2a3…aiai+1...am012…MAX-1顺序队列结构设计讨论队列元素出队情形frontreara1a2a3…aiai+1...am012…MAX-1顺序队a1a2a3…aiai+1...am012…MAX-1顺序队列结构设计讨论队列元素出队情形frontreara1a2a3…aiai+1...am012…MAX-1顺序队队列状态5aiai+1...am012…MAX-1顺序队列结构设计讨论队列元素出队情形frontrear此时还能让新元素入队吗？问题4队列状态5aiai+1...am012…MAX-1顺序队列结队列状态5aiai+1...am012…MAX-1顺序队列结构设计讨论队列元素在数组0位置入队情形frontrearam+1队列状态5aiai+1...am012…MAX-1顺序队列结队列状态6aiai+1...am012…MAX-1顺序队列结构设计讨论frontrearam+1rear队列元素在数组0位置入队情形队列状态6aiai+1...am012…MAX-1顺序队列结队列状态6aiai+1...am012…MAX-1顺序队列结构设计讨论frontrearam+1rear队列循环使用如何由MAX-1位置“翻转”指向到0位置问题5顺序队列应是循环使用的结论2rear=(rear+1)mod表长front=(front+1)mod表长结论3循环队列头尾指针计算规则队列状态6aiai+1...am012…MAX-1顺序队列结aiai+1...am012…MAX-1顺序队列结构设计讨论frontam+1rear继续入队直至队满aiai+1...am012…MAX-1顺序队列结构设计讨论aiai+1...am012…MAX-1顺序队列结构设计讨论frontam+1rearam+2继续入队直至队满aiai+1...am012…MAX-1顺序队列结构设计讨论aiai+1...am012…MAX-1顺序队列结构设计讨论frontam+1rearam+2…am+4继续入队直至队满aiai+1...am012…MAX-1顺序队列结构设计讨论队列状态7aiai+1...am012…MAX-1顺序队列结构设计讨论frontam+1rear队满情形am+2…am+4队满队满条件rear+1=front满状态队列状态7aiai+1...am012…MAX-1顺序队列结aiai+1...am012…MAX-1顺序队列结构设计讨论frontam+1rear出队至队空情形am+2…am+4aiai+1...am012…MAX-1顺序队列结构设计讨论ai+1...am012…MAX-1顺序队列结构设计讨论frontam+1rear出队至队空情形am+2…am+4ai+1...am012…MAX-1顺序队列结构设计讨论fram012…MAX-1顺序队列结构设计讨论frontam+1rear出队至队空情形am+2…am+4am012…MAX-1顺序队列结构设计讨论frontam+1012…MAX-1顺序队列结构设计讨论frontam+1rear出队至队空情形am+2…am+4012…MAX-1顺序队列结构设计讨论frontam+1re012…MAX-1顺序队列结构设计讨论frontrear出队至队空情形am+2…am+4012…MAX-1顺序队列结构设计讨论frontrear出队顺序队列结构设计讨论frontrear出队至队空情形am+2…am+4顺序队列结构设计讨论frontrear出队至队空情形am+2顺序队列结构设计讨论frontrear出队至队空情形am+2…am+4顺序队列结构设计讨论frontrear出队至队空情形am+2队列状态8顺序队列结构设计讨论frontrear出队至队空情形am+4队空前队列状态8顺序队列结构设计讨论frontrear出队至队空情队列状态9顺序队列结构设计讨论frontrear出队至队空情形am+4队空队空也是下面这个条件吗？rear+1=front空状态队空与队满条件不能一样队列状态9顺序队列结构设计讨论frontrear出队至队空情aifrontai+1…amam+1rear…am+4队满条件:rear+1=frontam+4队空条件:rear=frontrearfrontam+3队列状态10队列状态11队满队空顺序队列结构设计讨论试改队空条件为rear=front空与满队空与队满条件不能一样aifrontai+1…amam+1rear…am+4队满条frontrear队满条件:rear+1=frontam+4队空条件:rear=frontrearfront队列状态10队列状态11顺序队列结构设计讨论试改队空条件为rear=front空与满队空与队满条件不能一样am+4不能入队aiai+1…amam+1…am+4am+3frontrear队满条件:rear+1=frontamaifrontrearam+4rearfront队列状态10队列状态11顺序队列结构设计讨论试改队空条件为rear=front空与满队空与队满条件不能一样am+4不能入队ai+1…amam+1…am+4am+3aifrontrearam+4rearfront队列状态10aifrontrearam+4rearfront队列状态10队列状态11顺序队列结构设计讨论试改队空条件为rear=front空与满队空与队满条件不能一样am+4不能入队ai+1…amam+1…am+4am+3aifrontrearam+4rearfront队列状态10aifrontrearam+4rearfront队列状态10队列状态11顺序队列结构设计讨论试改队空条件为rear=front空与满队空与队满条件不能一样am+4不能入队ai+1…amam+1…am+4am+3aifrontrearam+4rearfront队列状态10frontrearrearfront队列状态10队列状态11顺序队列结构设计讨论试改队空条件为rear=front空与满队空与队满条件不能一样am+4不能入队aiai+1…amam+1…am+4am+3frontrearrearfront队列状态10队列状态11frontrearam+4rearfront队列状态12队列状态13队满队空am+4不能入队图3.77问题7队空队满情形讨论2顺序队列结构设计讨论少入队一个元素以使队空队满条件不一样空与满aiai+1…amam+1…am+3队满条件:rear+1=front队空条件:rear=frontfrontrearam+4rearfront队列状态12队列am+3rearfront队列状态14队空前顺序队列结构设计讨论少入队一个元素以使队空队满条件不一样测试am+3rearfront队列状态14队空前顺序队列结构设计135顺序循环队列的规则结论1顺序队列中已经出队的元素不需要删除顺序队列应是循环使用的结论2rear=(rear+1)mod表长front=(front+1)mod表长结论3循环队列头尾指针的计算规则：结论41、循环队列头指针指向队列第一个元素的前一个位置；2、尾指针指向队列的最后一个元素的位置；3、队列少用一个元素的空间，以达到使队空、队满条件不一样的目的。135顺序循环队列的规则结论1顺序队列中已经出队的元素不需要136循环队列结构及操作规则队列初始化：front=rear=QUEUE_SIZE-1;队头指针进1:front=(front+1)%QUEUE_SIZE;队尾指针进1:rear=(rear+1)%QUEUE_SIZE;队满条件：(rear+1)%QUEUE_SIZE=front;队空条件：front=rear;#defineQUEUE_SIZE128typedefstruct{datatypedata[QUEUE_SIZE];intfront,rear;}SeqQueue;要记住的结论哦凡循环队列未做特别声明，均按以上规则操作136循环队列结构及操作规则队列初始化：front队列的例子【例3-5】杨辉三角的循环队列解法在队列引例2——杨辉三角形的队列解法中，队列没有循环使用，当queue[]与循环次数之间设置不当，则数组queue有越界的危险。下面我们先来通过跟踪观察这种越界的情形。【结论】循环队列在使用的过程中，因为队长有限，当入队的速度大于出队速度时，会产生队尾元素覆盖队头元素的现象，即队列“溢出”。137队列的例子【例3-5】杨辉三角的循环队列解法1373.2队列3.2.13.2.23.2.33.2.4队列处理模式的引入队列的逻辑结构队列的顺序存储结构顺序队列的基本操作3.2.5队列的链式存储结构链队列的基本操作3.2.63.2.7各种队列结构的比较队列的应用举例3.2.83.2队列3.2.13.2.23.2.33.2.4队列处理队列的基本操作置队空判队空取队头元素入队出队队列的基本操作置队空判队空取队头元素入队出队队列的基本操作置队空判队空取队头元素入队出队队列的基本操作置队空判队空取队头元素入队出队顺序队列的基本操作——置队空问题顺序队列置队空测试情形状态预期结果一般情况队列空或非空队列头尾指针置相等功能描述输入输出置队空initialize_SqQueue队列起始地址SeqQueue*无函数名形参函数类型测试样例设计函数框架设计顺序队列的基本操作——置队空问题顺序队列置队空测试情形状态预顺序队列的基本操作——置队空按队空初始化条件front=rear=QUEUE_SIZE-1设置头尾指针。/*======================================函数功能：顺序队列置队空函数输入：队列起始地址函数输出：无========================================*/voidinitialize_SqQueue(SeqQueue*sq){sq->front=QUEUE_SIZE-1;sq->rear=QUEUE_SIZE-1;}算法设计顺序队列的基本操作——置队空按队空初始化条件front=队列的基本操作置队空判队空取队头元素入队出队队列的基本操作置队空判队空取队头元素入队出队顺序队列的基本操作——判队空测试情形状态/输入预期结果一般情况队列空输出队空标志队列非空输出队非空标志问题顺序队列判队空功能描述输入输出判队空Empty_SqQueue队列起始地址SeqQueue*队列状态标志int（队空：1；队非空：0）函数名形参函数类型测试样例设计函数框架设计顺序队列的基本操作——判队空测试情形状态/输入预期结果一般情顺序队列的基本操作——判队空/*======================================函数功能：顺序队列判队空函数输入：队列起始地址函数输出：1——队空；0——队非空========================================*/intEmpty_SqQueue(SeqQueue*sq){if(sq->rear==sq->front)returnTRUE;elsereturnFALSE;}算法设计根据队空条件rear=front，判断队列是否为空：队空返回1；队非空返回0。顺序队列的基本操作——判队空算法设计根据队空条件rear=队列的基本操作置队空判队空取队头元素入队出队队列的基本操作置队空判队空取队头元素入队出队顺序队列的基本操作——取队头元素测试情形状态预期结果正常情形队列非空返回队头元素位置异常情形队列为空返回队空标志147功能描述输入输出取队头元素get_SqQueue队列起始地址SeqQueue*队头元素位置int（队空：-1，队非空：队头元素位置）函数名形参函数类型

问题

顺序队列取队头元素测试样例设计函数框架设计顺序队列的基本操作——取队头元素测试情形状态预期结果正常情形顺序队列的基本操作——取队头元素148/*======================================函数功能：顺序队列取队头元素函数输入：队列起始地址函数输出：-1——队空标志；其他值——队头元素位置========================================*/intget_SqQueue(SeqQueue*sq){if(!Empty_SqQueue(sq))//队非空return(sq->front+1)%QUEUE_SIZE;return-1;//队空}时间复杂度O(1)算法设计若队列非空，返回队头元素所在位置下标；否则返回-1。顺序队列的基本操作——取队头元素148/*=========队列的基本操作置队空判队空取队头元素入队出队队列的基本操作置队空判队空取队头元素入队出队顺序队列的基本操作——入队测试情形状态预期结果正常情形队非满返回入队成功标志异常情形队满返回入队失败标志150功能描述输入输出入队Insert_SqQueue队列起始地址SeqQueue*入队是否成功标志int（队满：0队非满:1）入队元素值datatype函数名形参函数类型

问题

顺序队列的入队测试样例设计函数框架设计顺序队列的基本操作——入队测试情形状态预期结果正常情形队非满顺序队列的基本操作——入队/*======================================函数功能：顺序队列元素入队函数输入：队列起始地址，入队元素值函数输出：0——队满，操作不成功；1——队非满，操作成功========================================*/151时间复杂度O(1)若队满，返回FALSE；否则，队尾指针rear向后移一位，在rear指向处插入入队元素值。算法设计顺序队列的基本操作——入队151时间复杂度O(1)若队满，返队列的基本操作置队空判队空取队头元素入队出队队列的基本操作置队空判队空取队头元素入队出队顺序队列的基本操作——出队测试情形状态预期结果正常情形队列非空返回新的队头元素位置异常情形队列为空返回队空标志153功能描述输入输出出队Delete_SqQueue队列起始地址SeqQueue*队头指针

int（队空：-1；

队非空：队头元素位置）函数名形参函数类型问题顺序队列队头元素出队测试样例设计函数框架设计顺序队列的基本操作——出队测试情形状态预期结果正常情形队列非顺序队列的基本操作——出队顶部伪代码第一步细化顺序队列出队若队非空头指针front向后移一位返回front；否则返回队空标记-1154时间复杂度O(1)/*======================================函数功能：顺序队列出队函数输入：队列起始地址函数输出：-1——队空标志；其他值——队头元素位置========================================*/出队操作注意和取队头元素的区别。算法设计顺序队列的基本操作——出队顶部伪代码第一步细化顺序队列出队若3.2队列3.2.13.2.23.2.33.2.4队列处理模式的引入队列的逻辑结构队列的顺序存储结构顺序队列的基本操作3.2.5队列的链式存储结构链队列的基本操作3.2.63.2.7各种队列结构的比较队列的应用举例3.2.83.2队列3.2.13.2.23.2.33.2.4队列处理链队列——问题引入156

用循环队列实现杨辉三角形时，若没有队满的限制，将会面临数组溢出问题，这使得计算结果的规模会相应受限。在线性表一章已经学习了线性表的存储方式除了顺序存储外，还有链式存储的方法，队列既然是运算特殊的线性表，那么它也应该可以用链表方式存储。下面来讨论链表队列——链队列。除了循环队列外，还有什么好的解决办法吗？链队列——问题引入156用循环队列实现杨辉三角形时，157链队列用链表表示的队列（队列的链式存储结构），是限制仅在表头删除和表尾插入的单链表定义一个链队列由一个头指针和一个尾指针唯一地确定

157链队列用链表表示的队列（队列的链式存储结构），是限制仅链队列的结构设计158设置链队列lq指针的目的是什么？思考&讨论讨论：设置lq指针指向链队列头尾指针的组合结构，这样方便队列信息的完整传递。链队列的结构设计158设置链队列lq指针的目的是什么？思考&159链队列的结构设计typedefstructnode{datatypedata;structnode*next;}LinkListNode;typedefstruct{LinkListNode*front,*rear;}LinkQueue;lq*LinkQueue;链结点的描述链中头尾指针的描述数据结构设计159链队列的结构