数据结构 第三章 栈和队列.ppt

1、第三章 栈和队列 Stack and Queue,线性表,栈和队列都是,特殊的,线性表：表中数据元素之间存在着线性关系,特殊性：对表的插入和删除操作受到了限制,第3章 栈和队列 目录 3.1 栈(Stack) 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列(Queue),普通线性表: 插入位置有n+1个(1.n+1) 删除位置有n个(1.n) 栈: 插入位置和删除位置均只有一个， 限制在表的同一端进行。,a1,a2,a3,a4,栈模型：,输入序列,输出序列,特点：后进先出LIFO(Last In First Out), 哎呀， 出不来！,举例：A, B, C, D依次进栈，出栈序列

2、是：,D,C,B,A,D,C,A,B,D,B,C,A,D,B,A,C,D,B,C,A,D,B,A,C,A,B,C,D,A,B,D,C,A,C,B,D,A,C,D,B,A,D,C,B,A,D,B,C,B,C,D,A,B,C,A,D,B,D,C,A,B,D,A,C,B,A,C,D,B,A,D,C,C,D,B,A,C,D,A,B,C,B,D,A,C,B,A,D,C,A,B,D,C,A,D,B,一、顺序栈 #define STACK_INIT_SIZE 100 /存储空间初始分配量 #define STACKINCREMENT 10 /存储空间分配增量 typedef struct SElemType

3、 *base; /数组首地址,在栈构造之前和销毁之后，base的值为NULL SElemType *top; /栈顶指针 int stacksize; /当前已分配的存储空间，以元素为单位 SqStack,a1,a2,a3,a4,Top指在栈顶元素的下一个位置,空栈：S.base = S.top 栈长：S.topS.base 入栈：*S.top + = e 出栈：e = *-S.top,a1,栈满！,栈满： S.top - S.base = S.stacksize,a2,a3,a4,基本运算在顺序栈上的实现 读栈顶： Status GetTop(SqStack S, SElemType /Ge

4、tTop,判栈空： Status StackEmpty(SqStack S) /若栈空，返回TRUE；否则返回FALSE。 if(S.top=S.base) return TRUE； /栈空 else return FALSE; /StackEmpty,进栈： Status Push(SqStack /Push,基本运算在顺序栈上的实现 出栈： status Pop(SqStack /Pop,二、链栈-不带头结点的单链表,进栈Push： p-next=S; S=p;,基本运算在链栈上的实现 进栈： status Push(LinkStack /Push,基本运算在链栈上的实现 出栈： stat

5、us Pop(LinkStack /Pop,3.2 栈的应用举例,数制转换 括号匹配的检验 行编辑程序 背包问题求解 迷宫求解 表达式求值,十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理： N = (N div d)d + N mod d (其中：div为整除运算，mod为求余运算),N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,计算顺序,输出顺序,例如：（1348)10 = (2504)8 ，,void conversion () InitStack(S); / 构造空栈 scan

6、f (%d, / conversion,假设在表达式中 （）或（ ） 等为正确的格式， （ ）或（ ）或 （） 均为不正确的格式。,检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。,即后出现的“左括弧”，它等待与其匹配的“右括弧”出现的“急迫”心情要比先出现的左括弧高。换句话说，对“左括弧”来说，后出现的比先出现的“优先”等待检验，对“右括弧”来说，每个出现的右括弧要去找在它之前“最后”出现的那个左括弧去匹配。显然，必须将先后出现的左括弧依次保存，为了反映这个优先程度，保存左括弧的结构用栈最合适。这样对出现的右括弧来说，只要“栈顶元素”相匹配即可。如果在栈顶的那个左括弧正好和它匹配

7、，就可将左括弧从栈顶删除,到来的右括弧不是所“期待”的；,分析可能出现的不匹配的情况:,到来的是“不速之客”；,直到结束，也没有到来所“期待” 的括弧。, ( ), ( ) ), ( ),这三种情况对应到栈的操作即为： 1和栈顶的左括弧不相匹配； 2栈中并没有左括弧等在那里； 3栈中还有左括弧没有等到和它 相匹配的右括弧。,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余， 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” ， 否则表明不匹配。,3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括弧”有余。,s

8、tatus matching(char *exp) /检验表达式中所含括弧是否正确嵌套，若是则返回OK,否则返回ERROR char *p=exp; InitStack(S); /初始化栈S while(ch=*p)!=0) /当字符串exp未扫描完 if(is_left(ch) push(S,ch); /左括号进栈 else if(is_right(ch) Pop(S,left）； if(!left) return -1;/缺左括号 if(！peidui(left,ch)return -2;/左右不配 /else p+; /继续扫描下一个字符 if(!StackEmpty(S) return

9、 -3; /有多余的左括号 else return TRUE; /matching,Status is_left(char ch) /判断左括号函数 if(ch=( | ch= | ch= ) return TRUE; else return FALSE; /is_left Status is_right(char ch) /判断右括号函数 if(ch=) | ch= | ch=) return TRUE; else return FALSE; /is_right,Status peidui(char a, char b) /判断是否配对 if(a=( /peidui,一个简单的行编辑程序的功

10、能是：接受用户从终端输入的程序或数据，并存入用户的数据区。 “每接受一个字符即存入用户数据区”-不恰当！ 较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时及时更正。 例如：可用一个退格符“#”表示前一个字符无效；可 用一个退行符“”表示当前行中的字符均无效。 Whli#ilr#e(s#*s)- outchaputchar(*s=#+) -,while(*s),putchar(*s+),行输入处理程序 处理规则：遇#退一格；遇退一行 算法思想：引入栈，保存终端输入的一行字符（逐行处理）； 遇#退一格出栈一次 遇退一行清栈 步

11、骤（p50 算法3.2）1）初始化栈S2）读入字符ch3）ch!=EOF 3.1) ch!=EOF / 重置S为空栈 if (ch != EOF) ch = getchar( ); DestroyStack(S); /LineEdit,void LineEdit() /利用字符栈S,从终端接收一行并传送至调用过程的数据区 InitStack(S); ch=getchar(); / 从终端接收下一个字符 while (ch != EOF) /EOF为全文结束符,将从栈底到栈顶的字符传送至调用过程的数据区；,数据组织： 用一维数组W0.n-1存放n个物体的体积值 用一个栈S，记录当前背包内装载物体

12、的序号 变量T记录当前背包的剩余体积,W,void knapsack(int w, int T, int n) InitStack(S); k=0; do while(T0 /knapsack,严演示,(1,1),(1,2),(2,2),(2,3),(3,3),(3,4),(3,5),(2,5),(2,6),(1,5),(1,4),(4,3),(4,2),(4,1),(5,1),(6,1),迷宫问题,“穷举求解法” 从入口出发，顺某一方向向前探索，若 能走通，则继续往前走；否则沿原路退回， 换一个方向再继续探索，直至所有可能的通 路都探索到为止。 为了保证在任何位置上都能沿原路退 回，显然需要

13、用一个后进先出的结构来保存 从入口到当前位置的路径。 因此，在求迷宫通路的算法中应用“栈”也 就是自然而然的事了。,假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个 方块位置”，则求迷宫中一条路径的算法的基本思想是： 若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口； 若“当前位置”不可通，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。 所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西 、北）上相邻的

14、方块。 假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上 最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入 栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。,算法描述 （p51 算法3.3） 设定当前位置的初值为入口位置； do 若当前位置可通， 则 将当前位置插入栈顶； / 纳入路径 若该位置是出口位置，则结束； /求得路径存放栈中 否则切换当前位置的东邻方块为新的当前位置； 否则， 若栈不空且栈顶位置尚有且他方向未经探索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位 置的下一相邻块； 若栈不空但栈顶位置的四周均不通， 则 删去栈顶位置；/从路径中删去该通道块

15、 若栈不空，则重新测试新的栈顶位置，直至找到 一个可通的相邻块或出栈至栈空； while (栈不空)；,若栈空，则表明迷宫没有通路。,看演示,任何一个表达式都是由操作数(operand)、 运算符(operator)和界限符(delimiter)组成。 操作数可以是常数也可以是被说明为变量 或常量的标识符； 运算符可以分为算术运算符、关系运算符 和逻辑运算符等三类； 基本界限符有左右括弧和表达式结束符等。,限于二元运算符的表达式定义: 表达式 := (操作数) + (运算符) + (操作数) 操作数 := 简单变量 | 表达式 简单变量 : = 标识符 | 无符号整数,注：二元表达式是由（第一

16、）操作数（S1）、 运算符（OP）和（第二）操作数（S2）三部分依次 联接而成；其中的操作数可以是简单变量，也可以 是表达式；而简单变量可以是标识符，也可以是无 符号整数。,由于算术运算的规则是：先乘除后加减、先左后右和先括弧内后括弧外，则对表达式进行运算不能按其中运算符出现的先后次序进行 那么怎么办？ 其中一个方法是先将它转换成另一种形式。,表达式的三种标识方法：,设 Exp = S1 + OP + S2,则称 OP + S1 + S2 为前缀表示法,S1 + OP + S2 为中缀表示法,S1 + S2 + OP 为后缀表示法,例如: Exp = a b + (c d / e) f 前缀式

17、: + a b c / d e f 中缀式: a b + c d / e f 后缀式: a b c d e / f +,结论:,1）操作数之间的相对次序不变;,2）运算符的相对次序不同;,3）中缀式丢失了括弧信息，致使 运算的次序不确定;,4)前缀式的运算规则为: 连续出现的两个操作数和在它们之 前且紧靠它们的运算符构成一个最小表 达式;,5)后缀式的运算规则为: 运算符在式中出现的顺序恰为表达 式的运算顺序;每个运算符和在它之前出 现且紧靠它的两个操作数构成一个最小 表达式。,ab,d/e,c-d/e,(c-d/e)f,a b c d e / f +,如何从后缀式求值？,先找运算符，后找操作

18、数,运算过程为: 对后缀式从左向右扫描，遇见操作数则暂时保存，遇见运算符即可进行运算；此时参加运算的两个操作数应该是在它之前刚刚碰到的两个操作数，并且先出现的是第一操作数，后出现的是第二操作数。,ab+(c-d/e)f,由此可见，在运算过程中保存的操作数结构应该是个栈,建一个栈用来存放后缀表达式中的操作数。 扫描后缀表达式，若遇到操作数，则将其压进栈；若遇到运算符，则从栈顶连续取出两个操作数进行运算，然后将结果压进栈中。如此继续，直到最后一个运算符执行完毕，这时送入栈中的值就是结果。,看flash,算法描述,如何从原表达式求得后缀式？,每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中

19、，优先数高的运算符领先于优先数低的运算符,分析 “原表达式” 和 “后缀式”中的运算符: 原表达式: a b + (c d / e) f 后缀式: a b c d e / f +,给每个运算符赋以一个优先数的值： 运算符 # （ + - * / * 优先数 -1 0 1 1 2 2 3 其“*”为乘幂运算，“#”为结束符。容易看出， 优先数反映了算术运算中的优先关系，即优先数“高” 的运算符应优先于优先数低的运算符进行运算。 显然，保存运算符的结构应该是个栈，从栈底到 栈顶的运算符的优先数是从低到高的，因此它们运算 的先后应是从栈顶到栈底的。,从原表达式求得后缀式的规律为：,1) 设立运算符栈

20、；,2) 设表达式的结束符为“#”， 予设运算符栈的栈底为“#”；,3) 若当前字符是操作数， 则直接发送给后缀式。,4)若当前运算符的优先数高于栈 顶运算符，则进栈；否则，退 出栈顶运算符发送给后缀式；,5)若当前字符是结束符，则自栈 顶至栈底依次将栈中所有运算 符发送给后缀式；,6) “(”对它之前后的运算符起隔离 作用，则若当前运算符为“(”时 进栈；7) “)”可视为自相应左括弧开始的 表达式的结束符，则从栈顶起， 依次退出栈顶运算符发送给后缀 式直至栈顶字符为(止。,void transform(char suffix ,char exp ) InitStack(S); Push(S

21、, #); p = exp; ch = *p; while (!StackEmpty(S) if (!IN(ch, OP) Pass( Suffix, ch); else if ( ch!= # ) p+; ch = *p; / while / transform O (n), ,OP为运算符的集合，若 ch是运算符，则函数 IN(ch,OP)的值为“TRUE”,函数Pass(suffix,ch) 的功能是将字符ch复 制到数组 suffix 中,switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= (

22、) Pass( Suffix, c); Pop(S, c) /while break; default : while(Gettop(S,c) /defult / switch,若c(栈顶运算符)的优先数大于或等于ch(当前运算符)的优先数，则函数precede(c,ch)值为TRUE,看flash,表达式求值的规则： 设立运算符栈和操作数栈； 设表达式的结束符为“#”，予设运算符栈的栈底为“#”； 若当前字符是操作数，则进操作数栈； 若当前运算符的优先数高于栈顶运算符，则进栈； 否则，退出栈顶运算符,同时从操作数栈顶连续取出两个操作数与刚退出的运算符进行运算，然后将运算结果压进操作数栈； “

23、（”对它之前后的运算符起隔离作用，“）”可视为自相应左括弧开始的表达式的结束符。 （ p53 算法3.4）,OperandType EvaluateExpression() /算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和操作数栈， /OP为运算符集合。 InitStack(OPTR); Push(OPTR, #); InitStack(OPND); c=getchar(); while(c!=# | GetTop(OPTR)!=#) if(!In(c,OP) Push(OPND,c); c=getchar(); /不是运算符则进操作数栈 else switch( prec

24、ede(GetTop(OPTR),c) ) case : /退栈并将运算结果入栈 Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND, Operate(a,theta,b) ); break; /switch /while return(GetTop(OPND); / EvaluateExpression,严算法演示,递归与递推的关系 递归算法的执行过程分递推与回归两个阶段 在递推阶段: 把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。 在回归阶段: 当获得最简单的情况后，逐级返回，依次获得稍复杂问题的解。

25、递推是递归的一个阶段，递归包含着递推。,递归(recursion)：直接或间接地调用自身,递归的对象： 一个对象部分地包含它自己，或它自己给自己定义。 如线性表的另一种定义: 若元素个数为0，则称为空表 若元素个数大于0，则有且仅有一个第一个元素(即表头)，剩余元素形成一个表(即表尾) 递归的过程： 一个过程直接或间接地调用自己。 如：0!=1，n!=n*(n-1)!,实现递归,当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：,将所有的实在参数、返回地址等信息传递 给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。,从被调用

26、函数返回调用函数之 前，应该完成下列三项任务：,保存被调函数的计算结果； 释放被调函数的数据区； 依照被调函数保存的返回地址 将控制转移到调用函数。,多个函数嵌套调用的规则是：,后调用先返回 ！,此时的内存管理实行“栈式管理”,例如： void main( ) void a( ) void b( ) a( ); b( ); /main / a / b,函数a的数据区,Main的数据区,函数b的数据区,递归函数的实现 一个递归函数的运行过程类似于多个函数的嵌套调用，差别仅在于“调用函数和被调用函数是同一个函数”。 为了保证“每一层的递归调用”都是对“本层”的数据进行操作，在执行递归函数的过程中需

27、要一个“递归工作栈”。 它的作用是: 一、将递归调用时的实在参数和函数返回地址传递给 下一层执行的递归函数； 二、保存本层的参数和局部变量，以便从下一层返回 时重新使用它们。,在此，称调用递归函数的主函数为第0层，则从主函数调用递归函数被称为进入递归函数的 第1层 ，从递归函数的第i层递归调用本函数被称为进入递归函数的第 i+1 层。显然，当递归函数执行到第 i 层时，从第1层到第 i-1 层的数据都必须被保存下来，以便一层一层退回时继续使用。递归函数执行过程中每一层所占用的内存数据区合起来就是一个 递归工作栈。,主程序,主程序,main( ): fact(4),结,果,返,回,回,回,归,归

28、,求,求,值,值,结,果,返,回,回,回,归,归,求,求,值,值,fact(,4):,fact(,4):,fact(,3):,fact(,3):,fact(,2):,fact(,2):,fact(,1):,fact(,1):,fact(,0):,fact(,0):,1,1,直接定值为,1,计算,4*,fact(3),计算,3*,fact(2),计算,2*,fact(1),计算,1*,fact(0),1,1,2,2,6,6,24,24,参,数,传,递,递,递,归,归,调,调,用,用,参,数,传,递,递,递,归,归,调,调,用,用,递归工作栈 ：递归过程执行过程中占 用的数据区。 递归工作记录：每

29、一层的递归参数合 成一个记录。 当前活动记录：栈顶记录指示当前 层的执行情况。 当前环境指针：递归工作栈的栈顶 指针。,递归的应用 递归定义：如阶乘、Fibonacci数列等 数据结构：如表、树、二叉树等 问题求解：如Hanoi塔,定义是递归的,求解阶乘函数的递归算法 long fact ( long n ) if ( n = 0 ) return 1;/递归结束条件 else return n * fact (n-1); /递归的规则 ,数据结构是递归的线性表 空表 非空表:(表头元素+除表头元素以外的剩余元素) 查找表L中是否有元素值e LinkList search(LinkList L

30、, ElemType e) / L为不带头结点的单链表 if ( L=NULL ) return NULL; else if ( L-data=e ) return L; else return search(L-next, e); ,问题求解是递归的Hanoi塔void hanoi(int n, char a, char b, char c)n-圆盘数a-源塔座b-中介塔座 c-目标塔座 搬动方法 n=1, a-c n1:hanoi(n-1, a, c, b)a-chanoi(n-1, b, a, c) 注意用递归调用的结果，不关注该结果如何获得的细节,动画演示,递归与回溯N皇后问题 回溯是

31、按照某种条件往前试探搜索,若前进中遭到失败,则回过头来另择通路继续搜索. N皇后问题 在n行n列的国际象棋棋盘上，若两个皇后位于同一行、同一列或同一对角线上，则称为它们为互相攻击。n皇后问题是指： 找到这 n 个皇后的互不攻击的布局,6#主对角,皇后问题,（1,1）,（1,2）,（2,2）,（3,2）,（1,3）,（2,3）,（3,3）,（4,3）,（5,3）,（1,4）,（2,4）,（1,5）,（2,5）,（3,5）,（4,5）,基本思路：依次为每一行确定该行皇后的合法位置 安放第 i 行皇后时，需要在列的方向从 0 到 n-1 试探 ( j = 0, , n-1 ) 在第 j 列安放一个皇

32、后后 如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第 j 列安放的皇后： 如果没有出现攻击，在第 j 列安放的皇后不动递归安放第 i+1行皇后 如果第 i 行不能安放皇后，则回溯到第 i-1 行，从下一个列(j+1)继续试探,数据结构设计 标识每一列是否已经安放了皇后线性表，表长为N 标识各条主对角线是否已经安放了皇后 线性表，表长为2N-1 标识各条次对角线是否已经安放了皇后 线性表，表长为2N-1 记录当前各行的皇后在第几列布局状况 线性表，表长为N 存储结构的选择表长固定，有随机存取的要求顺序表,数据结构设计 标识每一列是否已经安放了皇后 顺序表col，表长为N 标识各

33、条主对角线是否已经安放了皇后 顺序表md，表长为2N-1 标识各条次对角线是否已经安放了皇后 顺序表sd，表长为2N-1 记录当前各行的皇后在第几列布局状况 顺序表q，表长为N,算法void Queen( int i, int n ) for ( int j = 0; j n; j+ ) if ( 第 i 行第 j 列没有攻击 ) 在第 i 行第 j 列安放皇后; if ( i = n-1 ) 输出一个布局; else Queen ( i+1, n ); 撤消第 i 行第 j 列的皇后; ,!colj mdn+i-j-1=1; sdi+j=1; qi = j;,输出q,colj= 0; mdn

34、+i-j-1=0; sdi+j=0; qi = 0;,动画演示,3.4 队列(Queue) 3.4.1 队列的定义 3.4.2 队列的链式表示和实现-链队列 3.4.3 队列的顺序表示和实现-循环队列,3.3.1 队列的定义 队列是一种特殊的线性表; 插入位置只有1个，限制在表尾进行； 删除位置也只有1个，限制在表头进行。,a1,a2,a3,a4,FIFO(First In First Out),队头端,队尾端,队列模型,队列的基本运算:,初始化空队列：InitQueue( struct QNode *next; QNode, *QueuePtr; typedef struct QueuePt

35、r front, rear; /队头指针和队尾指针 LinkQueue;,队元素,Q.front,Q.rear,队头元素,队尾元素,Q.front,Q.rear,队空条件： Q.front=Q.rear,Q,.,Q.front,Q.rear,s-next = NULL,Q.rear-next = s,Q.rear = s,Q.front-next=Q.front-next-next,链队列操作的示意,p= Q.front-next,free(p),队头元素,队尾元素,rear,带尾指针的循环链队列也是一种不错的选择,3.4 队列(Queue) 3.4.1 队列的定义 3.4.2 队列的链式表示

36、和实现-链队列 3.4.3 队列的顺序表示和实现-循环队列,a1,a2,a3,a4,maxsize,a5,#define maxsize 100 /队列数组的大小 typedef struct QElemType *base; /队列数组的基地址 int front; /队头指示器,若队列不空，指向队列头元素 int rear; /队尾指示器，若队列不空，指向队列尾元素的 /下一个位置 SqQueue；,指在队尾元素的 下一个位置,指在队头元素位置,a5,a7,a6,a8,maxsize,假上溢 rear=maxsize else rear=0; 这个if语句可等价地写成: rear=(rea

37、r+1) mod maxsize 出队： if(frontmaxsize-1) front+; else front=0; 这个if语句可等价地写成: front=(front+1) mod maxsize,判队空的条件：front = rear,a6,a5,初态：front=rear=0,a5、a6出队后front=rear=6,rear,front,a8,a7,a6,a5,a9,a10,问题来了队满的条件也是 front = rear,a11和a12相继入队后，rear追上了front,a11,a12,解决队满与队空条件一样的方案：,牺牲一个结点的空间约定, maxsize的空间中最多只放

38、maxsize1个结点,队列已经 装满了,rear所指的单元里不放任何元素,在这种约定下，当rear在顺时针方向距front相差一个单元时，队列就满了。 队满条件：front = (rear+1) mod maxsize,队列长度： (rear front + maxsize) mod maxsize,front=2, rear=5 length = (5 2 + 8) mod 8 = 3,front=5, rear=2 length = (2 5 + 8) mod 8 = 5,总结：,队列Q0.maxsize-1 初态：rear = front = 0 入队：rear = (rear+1)

39、mod maxsize 出队：front = (front+1) mod maxsize 队空条件：front = rear 队满条件：front = (rear+1) mod maxsize 队列长度：(rearfront+maxsize) mod maxsize,想一想： 对于Q1.maxsize的数组，入队、出队和求队列长度的公式该如何变化呢？,当队列数组的下界为1时，计算公式为： 队列Q1.maxsize 初态：rear = front = 1 入队：rear = rear mod maxsize + 1 出队：front = front mod maxsize + 1 队空条件：front = rear 队满条件：front = rear mod maxsize + 1 队列长度：(rearfront+maxsize) mod maxsize,循环队列的类型定义： #define MAXQSIZE 100;/队列数组的大小 typedef struct QElemType*base;/队列数组首地址 intfront;/队头指针，指向队头元素 intrear;/队尾指针，指向 /队尾元素的下一个位置 SqQ