第3章　栈和队列n2

nullnull第三章 栈和队列null通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。 线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1≤i≤n栈和队列是两种常用的数据类型null3.1 栈的类型定义3.3 栈的应用举例3.2 栈类型的实现3.4 队列的类型定义3.5 队列类型的实现null3.1 栈的类型定义栈（Stack)：是一种特殊的线性表（数据元素之间的关系是线性关系），其插入、删除只能在表的一端进行，另一端固定不动。栈顶（top):插入、删除一端； 栈底（bottom):固定不动的一端； 入栈（push):又称压入，即插入一个元素； 出栈（pop):又称弹出，即删除一个元素；null栈顶 (top) 栈底 (bottom)出栈 进栈 栈底元素 栈顶元素 null例、一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？解：可以通过穷举所有可能性来求解： ① 1入1出， 2入2出，3入3出， 即123； ② 1入1出， 2、3入，3、2出， 即132； ③ 1、2入，2出， 3入3出， 即231； ④ 1、2入，2、1出，3入3出， 即213； ⑤ 1、2、3入，3、2、1出， 即321； 合计有5种可能性。null例题：假设有A,B,C,D四个元素，它们的入栈的次序为：A-B-C-D,出栈次序任意，请问不可能得到下面那些出栈序列？(2) (6) (8)null 设有四个数据元素a1,a2,a3和a4，对它们进行栈操作。在进栈操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈的初始状态都是空。现要进行栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到的元素是 B 经操作后，最后在栈中的元素还有 C 个。 供选择的 A：1）a1 2）a2 3）a3 4）a4 B：1）a1 2）a2 3）a3 4）a4 C：1）1 2）2 3）3 4）0水平考试试题null3.1 栈的类型定义 ADT Stack { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ | ai-1, ai∈D, i=2,...,n } 约定an 端为栈顶，a1 端为栈底。 基本操作： } ADT StacknullInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit()) InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。 InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。 StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。 StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。 StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数，即栈的长度。 StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数，即栈的长度。 GetTop(S, &e) 初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。 GetTop(S, &e) 初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。a1a2an… … ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。 ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。 Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。 Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。 a1a2ane … …Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。a1a2anan-1 … …3.2 栈类型的实现3.2 栈类型的实现顺序栈链栈null//----- 栈的顺序存储表示 ----- #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack; 类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。null栈顶指针top,指向栈底 位置入栈A出栈栈满BCDEF栈空顺序栈的入栈与出栈null栈不存在的条件： base=NULL; 栈为空 的条件 ： base==top; 栈满的条件 ： top-base=MaxSize;入栈口诀：堆栈指针top “先压后加” : S[top++]=an 出栈口诀：堆栈指针top “先减后弹” : e=S[--top]约定栈顶指针指向 栈顶元素的下一个位置null Status InitStack (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; return OK; }null Status Push (SqStack &S, SElemType 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; return OK; }nullStatus Pop (SqStack &S, SElemType &e) { // 若栈不空，则删除S的栈顶元素， // 用e返回其值，并返回OK； // 否则返回ERROR if (S.top == S.base) return ERROR; e = *--S.top; return OK; } null设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少应为______。3null由于栈底位置是固定不变的，所以可以将栈底位置设置在数组两端的任何一端；而栈顶位置是随着入栈和出栈操作而变化的.附加知识点：(1)顺序栈栈的存储结构null顺序存储结构 Const StackMaxSize 50; typedef struct { ElemType elem[StackMaxSize]; int top; //栈顶指针 } Stack; top的值为0表示栈空栈空: s.top==0 栈满: s.top== StackMaxSize栈运算的实现1.初始化栈 void InitStack(Stack &S) { S.top=0; } 2.栈清除操作 void ClearStack(Stack &S) { S.top=0; }栈运算的实现3.判定栈是否为空bool StackEmpty(Stack &S) { return （S.top==0）; } 4.判定栈是否已满 bool StackFull(Stack &S) { return （S.top==StackMaxSize）； }3.判定栈是否为空5.进栈Status Push(Stack& S,ElemType& item) { if (S.top==StackMaxSize) { cerr<<"Stack overflow!"<next; delete cp;cp=np;HS3.清除链栈为空void ClearStack(LNode *& HS) { LNode *cp, *np; cp=HS; //cp指向栈顶 while(cp!=NULL) { np=cp->next; delete cp; cp=np; } HS=NULL; //置链栈为空 }void ClearStack(LNode *& HS)4.进栈向链栈顶插入一个元素itemHsa1anan-1newptrHsnewptr=new LNode;newptr->data=item;newptr->next=Hs;Hs=newptr;4.进栈void Push(LNode*& HS, ElemType& item) { LNode* newptr= new LNode; if (newptr==NULL) { cerr<<"failare!"<data=item; //赋值 newptr->next=HS; HS=newptr; //向栈顶插入新结点 } void Push(LNode*& HS, ElemType& item)5.出栈 从链栈顶取出一个元素p=Hs; item=Hs->data;特殊情况: 空表pHs=Hs->next;delete p;5.出栈Hsa1anan-1HsElemType Pop(LNode*& HS) { if (HS==NULL) { cerr<<“Stack is empty!"<next; //栈顶后移 ElemType temp=p->data; //取值 delete p; //释放结点 return temp; } ElemType Pop(LNode*& HS)null3.3 栈的应用举例例一、 数制转换例二、 括号匹配的检验例三、 行编辑程序问题例四、 迷宫求解例五、 表达式求值 例一、 数制转换 算法基于原理： N = (N div d)×d + N mod d 例一、 数制转换 算法基于原理： N = (N div d)×d + N mod d 例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计算顺序输出顺序nullvoid conversion () { InitStack(S); scanf ("%d",N); while (N) { Push(S, N % 8); N = N/8; } while (!StackEmpty(S)) { Pop(S,e); printf ( "%d", e ); } } // conversionnull 4 0 5 2 1348 168 void conversion () { int stack[4]; int top=0; int N; scanf(“%d”, N); while (N) { stack[top]=N%8; top++; N=N/8; } for(top=top-1; top>=0; top--) printf(“%d”,stack[top]); } 21 2 0 2504 InitStack(S) Push(S, N%S) While (!Stackempty(S)) { Pop(S, e); printf(“%d”, e); } null例二、 括号匹配的检验 假设在表达式中 （［］（））或［（［ ］［ ］）］ 等为正确的格式， ［（ ］）或（［（ ））或 （（）］) 均为不正确的格式。则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述。分析可能出现的不匹配的情况:分析可能出现的不匹配的情况:到来的右括弧并非是所“期待”的；例如：考虑下列括号序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8到来的是“不速之客”；直到结束，也没有到来所“期待”的括弧。null算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余， 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” ， 否则表明不匹配。3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括弧”有余。nullStatus matching(string& exp) { int state = 1; while (i<=Length(exp) && state) { switch of exp[i] { case 左括弧:{Push(S,exp[i]); i++; break;} case”)”: { if(NOT StackEmpty(S)&&GetTop(S)=“(“ {Pop(S,e); i++;} else {state = 0;} break; } … … } if (StackEmpty(S)&&state) return OK; …...null例三、行编辑程序问题如何实现？“每接受一个字符即存入存储器” ? 并不恰当！null 设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“@”为退行符。 在用户输入一行的过程中，允许 用户输入出差错，并在发现有误时 可以及时更正。合理的作法是：null假设从终端接受了这样两行字符： whli##ilr#e（s#*s) outcha@putchar(*s=#++);则实际有效的是下列两行： while (*s) putchar(*s++);w h l i i l e null while (ch != EOF && ch != '\n') { switch (ch) { case '#' : Pop(S, c); break; case '@': ClearStack(S); break;// 重置S为空栈 default : Push(S, ch); break; } ch = getchar(); // 从终端接收下一个字符 }ClearStack(S); // 重置S为空栈 if (ch != EOF) ch = getchar();while (ch != EOF) { //EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的 数据区；null例四、 迷宫求解通常用的是“穷举求解”的方法null1 1 11 2 22 2 23 2 13 3 13 4 42 4 12 5 12 6 41 6 31 5 31 4 43$$$$$$$$0 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9求迷宫路径算法的基本思想是：求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。null设定当前位置的初值为入口位置； do｛ 若当前位置可通， 则｛将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为 新的当前位置； ｝ 否则 { ｝ ｝while (栈不空）；求迷宫中一条从入口到出口的路径的算法： … …null若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通， 则｛删去栈顶位置；// 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； ｝若栈空，则表明迷宫没有通路。null 限于二元运算符的表达式定义: 表达式 ::= (操作数) + (运算符) + (操作数) 操作数 ::= 简单变量 | 表达式 简单变量 :: = 标识符 | 无符号整数例五、 表达式求值null例如：3*（7 – 2 ） （1）算术四则运算的规则： a. 从左算到右 b. 先乘除，后加减 c. 先括号内，后括号外 由此，此表达式的计算顺序为： 3*（7 – 2 ）= 3 * 5 = 15null（2）根据上述三条运算规则，在运算的每一步中，对任意相继出现的运算符1和2 ，都要比较优先权关系。 运算符优先法所依据的算符间的优先关系见教材P53表3.1由表可看出，右括号 ) 和井号 # 作为2时级别最低； 由规则得出： * ，/， + ，-为1时的优先权低于‘（’，高于‘）’ 由规则得出：‘（’==‘）’ 表明括号内运算，已算完。‘ # ’==‘ # ’ 表明表达式求值完毕。 令OP={+，-，*，/，（，），#}null3）算法思想： 设两个栈：操作符栈 OPTR ，操作数栈 OPND 栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底元素为表达式起始符 ‘#’； 依次读入字符：是操作数则入OPND栈，是运算符则要判断： if 操作符(2)< 栈顶元素(1)，则出栈、计算，结果压入OPND栈 操作符== 栈顶元素且不为‘#’，脱括号（弹出左括号）； if 操作符(2) > 栈顶元素(1) ，压入OPTR栈。 null 例 求表达式#3*(7-2)#nullStatus EvaluateExpression( OperandType &result) { InitStack(OPND); InitStack(OPTR); Push(OPTR ,’#’); c=getchar( ); while((c!=‘#’)||(GetTop(OPTR)!=‘#’)) { if (!In(c,OP) { Push(OPND,c); c=getchar( );} else switch(compare(GetTop(OPTR) ,c)) { case ‘<’ : Push(OPTR , c); c=getchar( ); break; case ‘=’: Pop(OPTR,x); c=getchar( ); break; case ‘>’ : Pop(OPTR,tem); Pop(OPND,b ); Pop(OPND,a ); result=Operate(a,tem,b); Push(OPND,result); c=getchar( ); break; } //switch }//while result=GetTop(OPND);}//End EvaluateExpressionnull 附加知识：表达式的三种标识方法：设 Exp = S1 + OP + S2则称 OP + S1 + S2 为前缀表示法 S1 + OP + S2 为中缀表示法 S1 + S2 + OP 为后缀表示法 null例如: Exp = a  b + (c  d / e)  f 前缀式: +  a b   c / d e f 中缀式: a  b + c  d / e  f 后缀式: a b  c d e /  f  + 结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;3）中缀式丢失了括弧信息， 致使运算的次序不确定;4)前缀式的运算规则为: 连续出现的两个操作数和在它们 之前且紧靠它们的运算符构成一 个最小表达式; 5)后缀式的运算规则为: 运算符在式中出现的顺序恰为 表达式的运算顺序; 每个运算符和在它之前出现 且 紧靠它的两个操作数构成一个最小 表达式。如何从后缀式求值？如何从后缀式求值？先找运算符， 再找操作数例如： a b  c d e /  f  +abd/ec-d/e(c-d/e)fnull如何从原表达式求得后缀式？ 每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。分析 “原表达式” 和 “后缀式”中的运算符: 原表达式: a + b  c  d / e  f 后缀式: a b c  + d e / f  null从原表达式求得后缀式的规律为：1) 设立运算符栈；2) 设表达式的结束符为“#”， 予设运算符栈的栈底为“#”；3) 若当前字符是操作数， 则直接发送给后缀式。null4) 若当前运算符的优先数高于栈顶运算符，则进栈；5) 否则，退出栈顶运算符发送给后缀式； 6) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为：null计算机编译程序分两步处理表达式： （1）将中缀形式的表达式转换为后缀形式的表达式（逆波兰表示） （2）根据后缀表达式生成的有关的机器指令，对后缀表达式求值。 【例】中缀表达式#(1+2)*((8-2)/(7-4)) #变成等价的后缀表达式。  现在用栈来实现该运算，栈的变化及输出结果如下:null#(1+2)*((8-2)/(7-4)) #null#(1+2)*((8-2)/(7-4)) #null后缀表达式的求值 将中缀表达式转换成等价的后缀表达式后，求值时，不需要再考虑运算符的优先级，只需从左到右扫描一遍后缀表达式即可。具体求值步骤为：设置一个栈，开始时，栈为空，然后从左到右扫描后缀表达式，若遇操作数，则进栈；若遇运算符，则从栈中退出两个元素，先退出的放到运算符的右边，后退出的放到运算符左边，运算后的结果再进栈，直到后缀表达式扫描完毕。此时，栈中仅有一个元素，即为运算的结果。null例，求后缀表达式：1 2 + 8 2 - 7 4 - / *的值，栈的变化情如下：null从上可知，最后求得的后缀表达式之值为6，与用中缀表达式求得的结果一致，但后缀式求值要简单得多。例，求后缀表达式：1 2 + 8 2 - 7 4 - / *的值，栈的变化情如下：nullvoid transform(char suffix[ ], char exp[ ] ) { InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty(S)) { if (!IN(ch, OP)) Pass( Suffix, ch); else { } if ( ch!= # ) { p++; ch = *p; } else { Pop(S, ch); Pass(Suffix, ch); } } // while } // CrtExptree… …nullswitch (ch) { case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) { Pass( Suffix, c); Pop(S, c) } break; defult : while(Gettop(S, c) && ( precede(c,ch))) { Pass( Suffix, c); Pop(S, c); } if ( ch!= # ) Push( S, ch); break; } // switchnull ADT Queue { 数据对象： D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0} 数据关系： R1＝{ | ai-1, ai ∈D, i=2,...,n} 约定其中a1 端为队列头， an 端为队列尾基本操作：3.4 队列的类型定义} ADT Queuenull队列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit())InitQueue(&Q) 操作结果：构造一个空队列Q。 DestroyQueue(&Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁， 不再存在。 InitQueue(&Q) 操作结果：构造一个空队列Q。 DestroyQueue(&Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁， 不再存在。 QueueEmpty(Q) 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。 QueueEmpty(Q) 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。 QueueLength(Q) 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。 QueueLength(Q) 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。 GetHead(Q, &e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头元素。 GetHead(Q, &e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头元素。a1a2an… … ClearQueue(&Q) 初始条件：队列Q已存在。 操作结果：将Q清为空队列。 ClearQueue(&Q) 初始条件：队列Q已存在。 操作结果：将Q清为空队列。 EnQueue(&Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。 EnQueue(&Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。a1a2ane … … DeQueue(&Q, &e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。 DeQueue(&Q, &e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。a1a2an… … null3.5 队列类型的实现链队列——链式映象循环队列——顺序映象null typedef struct QNode {// 结点类型 QElemType data; struct QNode *next; } QNode, *QueuePtr; Struct QNode x; QNode x QNode *y =>QueuePtr y链队列——链式映象nulla1∧an…Q.front Q.rearQ.front Q.rear∧空队列typedef struct { // 链队列类型 QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 } LinkQueue;null Status InitQueue (LinkQueue &Q) { // 构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit (OVERFLOW); //存储分配失败 Q.front->next = NULL; return OK; }null Status EnQueue (LinkQueue &Q, QElemType e) { // 插入元素e为Q的新的队尾元素 p = (QueuePtr) malloc (sizeof (QNode)); if (!p) exit (OVERFLOW); //存储分配失败 p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; }∧rear…front∧e∧e2p p null Status DeQueue (LinkQueue &Q, QElemType &e) { // 若队列不空，则删除Q的队头元素， //用 e 返回其值，并返回OK；否则返回ERROR if (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; free (p); return OK; }∧frontrearyep p ∧null循环队列——顺序映象队列的顺序存储结构：存储方式：同一般的顺序存储结构完全相同，但是由于在两端操作，设两个指示器（rear和front）分别指示队列的尾和首。null空队列：rear=front=0 入队：rear=rear+1 出队：front=front+1 队列空：front=rear约定：队头指针始终 指向队列头元素，队 尾始终指向队尾元素 的下一个位置null 在顺序队列中，当尾指针已经指向了队列的最后一个 位置的下一位置时，若再有元素入队，就会发生“溢出”。 “假溢出”——队列的存储空间未满，却发生了溢出。 null如何解决顺序队列的假溢出问题？ 　　可采取四种方法： 　1)采用循环队列； 2)按最大可能的进队操作次数设置顺序队列的最大元素个数； 3)修改出队算法，使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置； 　４)修改入队算法，增加判断条件，当假溢出时，把队列中的数据元素向对头移动，然后方完成入队操作。顺序循环队列的表示和实现顺序循环队列的表示和实现１、顺序循环队列的基本原理 把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到MaxQueueSize-1后，再前进一个位置就自动到０。 　　　null2、顺序循环队列的队空和队满判断问题 新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决

方案

气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载

有三： ①使用一个计数器

记录

混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载

队列中元素个数（即队列长度）； 　　判队满：count>0 && rear==front 判队空：count==0 ②加设标志位，出队时置０,入队时置１,则可识别当前front=rear属于何种情况 　　判队满：tag==1 && rear==front 判队空：tag==0 && rear==front ③ 少用一个存储单元 　　判队满： front=＝(rear+1)%MaxQueueSize 判队空： rear==frontnull循环意义下的加 1 操作可以描述为： if (rear + 1 > MAXQSIZE) rear = 0; else rear ++; 0 1 2 3 4 5 J5 J4 J3 rear front 利用模运算可简化为：rear = (rear + 1)% MAXQSIZE null例： 一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置? 解：由图可知，队头和队尾指针的初态分别为front=1和rear=0。删除4个元素后f=5；再插入4个元素后，r=(0+4)%6=4 rear=4null#define MAXQSIZE 100 //最大队列长度 typedef struct { QElemType *base; // 动态分配存储空间 int front; // 头指针，若队列不空， // 指向队列头元素 int rear; // 尾指针，若队列不空，指向 // 队列尾元素 的下一个位置 } SqQueue;队列的顺序存储结构：null Status InitQueue (SqQueue &Q) { // 构造一个空队列Q Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType)); if (!Q.base) exit (OVERFLOW); // 存储分配失败 Q.front = Q.rear = 0; return OK; }null Status QueueLength (SqQueue Q) { // 返回队列 Q 的元素个数 return (Q.rear - Q.front); } Status QueueLength (SqQueue Q) { // 返回队列 Q 的元素个数 return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE; }求循环队列的长度 nullStatus EnQueue (SqQueue &Q, ElemType e) { // 插入元素e为Q的新的队尾元素 if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; //队列满 Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; }J5 null Status DeQueue (SqQueue &Q, ElemType &e) { /* 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK; 否则返回ERROR*/ if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front+1) % MAXQSIZE; return OK;}附加:顺序循环队列的实现(使用一个计数器)附加:顺序循环队列的实现(使用一个计数器)采用对顺序循环队列的分析，其结构体定义为： typedef struct { DataType queue[MaxQueueSize]; int rear; /*队尾指针*/ int front; /*队头指针*/ int count; /*计数器*/ } SeqCQueue; null讨论：循环队列的基本操作如何实现？ 以建队、入队和出队三种基本操作为例1）初始化一个顺序循环队列算法

要求

对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗

：生成一空队列 算法操作： 设置队列为空队列，其特征即： front=rear=0，count=0null具体算法：void QueueInitiate(SeqCQueue *Q) /*初始化顺序循环队列Q*/ { Q->rear = 0; /*定义初始队尾指针下标值*/ Q->front = 0; /*定义初始队头指针下标值*/ Q->count = 0; /*定义初始计数器值*/ }null2） 入队操作算法说明：向循环队列的队尾插入一个元素. 分