数据结构-栈和队列课件

1、第第3 3章章 栈和队列栈和队列1.1. 掌握栈和队列的掌握栈和队列的特点特点，并能在相应的应用问，并能在相应的应用问题中正确选用题中正确选用2.2. 熟练掌握栈的熟练掌握栈的两种存储结构两种存储结构的基本操作实现的基本操作实现算法，特别应注意算法，特别应注意栈满和栈空栈满和栈空的条件的条件3.3. 熟练掌握熟练掌握循环队列和链队列循环队列和链队列的基本操作实现的基本操作实现算法，特别注意算法，特别注意队满和队空队满和队空的的条件条件4.4. 理解理解递归算法递归算法执行过程中栈的状态变化过程执行过程中栈的状态变化过程 栈（栈（Stack）1. 1. 定义定义2. 2. 逻辑结构逻辑结构3.

2、3. 存储结构存储结构4. 4. 运算规则运算规则5. 5. 实现方式实现方式队列（队列（Queue）1. 1. 定义定义2. 2. 逻辑结构逻辑结构3. 3. 存储结构存储结构4. 4. 运算规则运算规则5. 5. 实现方式实现方式3.13.1栈栈定定 义义只能在只能在表的一端表的一端（栈顶栈顶）进行插入和删除运算）进行插入和删除运算的的线性表线性表逻辑结构逻辑结构与线性表相同，仍为与线性表相同，仍为一对一一对一关系关系存储结构存储结构用用顺序栈顺序栈或或链栈链栈存储均可，但以顺序栈更常见存储均可，但以顺序栈更常见运算规则运算规则只能在只能在栈顶栈顶运算，且访问结点时依照运算，且访问结点时依

3、照后进先出后进先出（LIFOLIFO）或或先进后出先进后出（FILOFILO）的原则的原则实现方式实现方式关键是编写关键是编写入栈入栈和和出栈出栈函数，具体实现依顺序函数，具体实现依顺序栈或链栈的不同而不同栈或链栈的不同而不同基本操作有基本操作有入栈、出栈、读栈顶元素值、建栈、入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空判断栈满、栈空等等栈是一种特殊的线性表，它只能在表的一端（栈顶）栈是一种特殊的线性表，它只能在表的一端（栈顶）进行插入和删除运算进行插入和删除运算栈与一般线性表的区别：仅在于栈与一般线性表的区别：仅在于运算规则运算规则不同不同一般线性表一般线性表 逻辑结构：一对一逻辑结构：一

4、对一 存储结构：顺序表、链表存储结构：顺序表、链表 运算规则：随机运算规则：随机、顺序存取顺序存取栈栈逻辑结构：一对一逻辑结构：一对一存储结构：顺序存储结构：顺序栈栈、链、链栈栈运算规则：运算规则：后进先出后进先出栈与一般线性表的区别栈与一般线性表的区别“进进” 压入压入=PUSH=PUSH（) )“出出” 弹出弹出=POP( )=POP( ) a a1 1 a a2 2 a an n顺序栈顺序栈S S a ai i表头表头表尾表尾栈底栈底basebase栈顶栈顶toptop低地址低地址高地址高地址写入：写入：vi= vi= a ai i读出：读出：x= vix= vi压入：压入：PUSH (

5、PUSH (a an+1n+1) )弹出：弹出：POP (x)POP (x)前提：一定要预设栈顶指针前提：一定要预设栈顶指针toptop！低地址低地址高地址高地址vivi a a1 1 a a2 2 a ai i a an n 顺序表顺序表VnVn a an+1n+1顺序栈与顺序表顺序栈与顺序表顺序栈的表示顺序栈的表示空栈空栈base = topbase = top 是栈空标志是栈空标志stacksize = 4stacksize = 4topAbasebasetopABABCtopbasetopbaseABCDbasetop3120top top 指示真正的指示真正的栈顶元素之上栈顶元素之上

6、的下标地址的下标地址栈满时的处理方法：栈满时的处理方法：1 1、报错报错, ,返回操作系统。返回操作系统。2 2、分配更大的空间分配更大的空间，作为栈的存储空，作为栈的存储空间间, ,将原栈的内容移入新栈。将原栈的内容移入新栈。#define MAXSIZE 100typedef structSElemType *base;SElemType *top;int stacksize;SqStack;顺序栈的表示顺序栈的表示 构造一个空栈构造一个空栈 步骤：步骤：(1)(1)分配空间并检查空间分配空间并检查空间是否分配失败，若失是否分配失败，若失败则返回错误败则返回错误顺序栈初始化顺序栈初始化ba

7、sestacksizetops(2)(2)设置栈底和栈顶指针设置栈底和栈顶指针 S.top = S.base;(3)(3)设置栈大小设置栈大小Status InitStack( SqStack &S )S.base =new SElemTypeMAXSIZE；if( !S.base ) return OVERFLOW;S.top = S.base;S.stackSize = MAXSIZE;return OK;顺序栈初始化顺序栈初始化判断顺序栈是否为空判断顺序栈是否为空bool StackEmpty( SqStack S )if(S.top = S.base) return true;

8、 else return false;basetop3120求顺序栈的长度求顺序栈的长度int StackLength( SqStack S )return S.top S.base;basetopABStatus ClearStack( SqStack S )if( S.base ) S.top = S.base;return OK;清空顺序栈清空顺序栈basetop3120Status DestroyStack( SqStack &S )if( S.base )delete S.base ;S.stacksize = 0;S.base = S.top = NULL; return

9、OK;销毁顺序栈销毁顺序栈(1)(1)判断是否栈满，若满则出错判断是否栈满，若满则出错(2)(2)元素元素e e压入栈顶压入栈顶(3)(3)栈顶指针加栈顶指针加1 1顺序栈进栈顺序栈进栈Status Push( SqStack &S, SElemType e) if( S.top - S.base= S.stacksize ) / 栈满栈满 return ERROR; *S.top+=e;return OK;*S.top=e;S.top+;ABCtopbase(1)(1)判断是否栈空，若空则出错判断是否栈空，若空则出错(2)(2)获取栈顶元素获取栈顶元素e e(3)(3)栈顶指针减栈顶

10、指针减1 1顺序栈出栈顺序栈出栈Status Pop( SqStack &S, SElemType &e) if( S.top = S.base ) / 栈空栈空 return ERROR; e *-S.top;return OK; -S.top; e=*S.top;ABCtopbase(1)(1) 判断是否空栈，若空则返回错误判断是否空栈，若空则返回错误(2)(2) 否则通过栈顶指针获取栈顶元素否则通过栈顶指针获取栈顶元素取顺序栈栈顶元素取顺序栈栈顶元素Status GetTop( SqStack S, SElemType &e) if( S.top = S.base

11、 ) return ERROR; / 栈空栈空 e = *( S.top 1 ); return OK;e = *( S.top - ); ?ABCtopbase435612435612中到了中到了1212顺序不能实现；顺序不能实现；135426135426可以实现。可以实现。1.1.如果一个栈的输入序列为如果一个栈的输入序列为123456123456，能否得到，能否得到435612435612和和135426135426的出栈序列？的出栈序列？练习练习练习练习i n-in-i+1不确定不确定2.2.若已知一个栈的入栈序列是若已知一个栈的入栈序列是1 1，2 2，3 3，n n，其，其输出序列

12、为输出序列为p1p1，p2p2，p3p3，pnpn，若，若p1=np1=n，则，则pipi为为练习练习 top不变不变 top=0 top+ top-D3.3.在一个具有在一个具有n n个单元的顺序栈中，假设以地址高端作个单元的顺序栈中，假设以地址高端作为栈底，以为栈底，以toptop作为栈顶指针，则当作进栈处理时，作为栈顶指针，则当作进栈处理时，toptop的变化为的变化为b0 t0 t1 b10 m-1V双栈共享一个栈空间双栈共享一个栈空间优点：互相调剂，灵活性强，减少溢出机会优点：互相调剂，灵活性强，减少溢出机会 将编号为将编号为0 0和和1 1的两个栈存放于一个数组空间的两个栈存放于一

13、个数组空间VmVm中，栈底分别处于数组的两端。当第中，栈底分别处于数组的两端。当第0 0号栈的栈顶号栈的栈顶指针指针top0top0等于等于-1-1时该栈为空，当第时该栈为空，当第1 1号栈的栈顶号栈的栈顶指针指针top1top1等于等于m m时该栈为空。两个栈均从两端向时该栈为空。两个栈均从两端向中间增长（如下图所示）中间增长（如下图所示） 。bot0 top0 top1 bot10 m-1Vtypedef structint top2, bot2; /栈顶和栈底指针栈顶和栈底指针SElemType SElemType * *V; V; /栈数组栈数组 int m; int m; /栈最大可

14、容纳元素个数栈最大可容纳元素个数DblStack;DblStack;数据结构定义如下数据结构定义如下void Dblpush(DblStack &s,SElemType x,int i) ；/把把x插入到栈插入到栈i的栈的栈int Dblpop(DblStack &s,int i,SElemType &x) ； /退掉位于栈退掉位于栈i栈顶的元素栈顶的元素int IsEmpty(DblStack s,int i) ；/判栈判栈i空否空否, 空返回空返回1, 否则返回否则返回0int IsFull(DblStack s) ；/判栈满否判栈满否, 满返回满返回1, 否则返回

15、否则返回0试编写判断栈空、栈满、进栈和出栈四个算试编写判断栈空、栈满、进栈和出栈四个算法的函数法的函数(函数定义方式如下）函数定义方式如下）b0 t0 t1 b10 m-1V栈空：栈空：topi = boti itopi = boti i表示栈的编号表示栈的编号 栈满：栈满：top0+1=top1 top0+1=top1 或或top1-1=top0top1-1=top0提示提示链栈的表示链栈的表示运算是受限的单链表，只能在链表头部进行操作，故运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针没有必要附加头结点。栈顶指针就是链表的头指针 typedef s

16、truct StackNode SElemType data; struct StackNode *next; StackNode, *LinkStack;LinkStack S; data next 栈顶栈顶栈底栈底S链栈的初始化链栈的初始化void InitStack(LinkStack &S ) S=NULL;S判断链栈是否为空判断链栈是否为空Status StackEmpty(LinkStack S) if (S=NULL) return TRUE; else return FALSE;链栈进栈链栈进栈Status Push(LinkStack &S , SElemTy

17、pe e) p=new StackNode; /生成新结点生成新结点p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return OK; 链栈出栈链栈出栈Status Pop (LinkStack &S,SElemType &e) if (S=NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; 取链栈栈顶元素取链栈栈顶元素SElemType GetTop(LinkStack S) if (S=NULL) exit(1)； else

18、 return Sdata; 3.2 3.2 栈的应用栈的应用例例1 1：数制转换（十转：数制转换（十转N N）用栈暂存低位值用栈暂存低位值例例2 2：括号匹配的检验括号匹配的检验用栈暂存左括号用栈暂存左括号例例3 3：表达式求值表达式求值用栈暂存运算符用栈暂存运算符例例4 4：迷宫求解：迷宫求解 用栈实现递归调用用栈实现递归调用简化了程序设计的问题简化了程序设计的问题迷宫求解迷宫求解从入口出发，按某一方向向未走过的前方探索从入口出发，按某一方向向未走过的前方探索若能走通，则到达新点，否则试探下一方向若能走通，则到达新点，否则试探下一方向 ; ; 若所有的方向均没有通路，则沿原路返回前一点，若

19、所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探换下一个方向再继续试探直到所有可能的通路都探索到，或找到一条通路，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。或无路可走又返回到入口点。求解思想：求解思想：回溯法回溯法迷宫求解迷宫求解需要解决的问题：需要解决的问题：1、表示迷宫的数据结构、表示迷宫的数据结构2、试探方向、试探方向3、栈的设计、栈的设计4、防止重复到达某点，避免发生死循环、防止重复到达某点，避免发生死循环迷宫求解迷宫求解1、表示迷宫的数据结构、表示迷宫的数据结构表示一个表示一个m行行n列迷宫：列迷宫：用用mazemn表示，表示，0im,0j

20、x=xx表表3.13.1算符间的优先关系算符间的优先关系【算法思想算法思想】（1）初始化）初始化OPTR栈和栈和OPND栈，将栈，将 “#”压入压入OPTR（2）依次读入字符）依次读入字符ch，循环执行（，循环执行（3）至（）至（5） （3）取出）取出OPTR的栈顶元素，当的栈顶元素，当OPTR的栈顶元素和的栈顶元素和ch均为均为“#”时，表达式求值完毕，时，表达式求值完毕，OPND栈顶元素为表达式的值栈顶元素为表达式的值设定两栈设定两栈 ：OPND-OPND-操作数或运算结果操作数或运算结果OPTR-OPTR-运算符运算符（4） if (ch是操作数是操作数) 则则ch进进OPND，读入下一

21、字符，读入下一字符ch（5） else 比较比较OPTR栈顶元素和栈顶元素和ch的优先级的优先级case : 运算符运算符ch 进进OPTR，读入下一字符，读入下一字符chcase=: 脱括号（弹出左括号），读入下一字符脱括号（弹出左括号），读入下一字符chcase : 栈顶运算符退栈、计算，结果进栈顶运算符退栈、计算，结果进OPNDOperandType EvaluateExpression( ) InitStack (OPND); ch = getchar( ); while (ch!= # | GetTop(OPTR)! = #) if (! In(ch,OP)Push(OPND,ch)

22、; ch = getchar(); / ch不是运算符则进栈不是运算符则进栈 else switch (Precede(GetTop(OPTR),ch) /比较优先权比较优先权 case : /弹出弹出OPTR栈顶的运算符运算，并将运算结果入栈栈顶的运算符运算，并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; case = : /脱括号并接收下一字符脱括号并接收下一字符 Pop(OPTR,x); ch = getchar(); break; / switc

23、h / while return GetTop(OPND); / EvaluateExpressionOPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*,(37-2)#Push(opnd,7)#,*,(3,7-2)#Push(optr,-)#,*,(,3,72)#Push(opnd,2)#,*,(,3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)3.3 3.3 栈与递归栈与

24、递归n递归的定义递归的定义 若一个对象部分地包含它若一个对象部分地包含它自己自己, , 或用它自己给自己定义或用它自己给自己定义, , 则称这个对则称这个对象是递归的；若一个过程象是递归的；若一个过程直接地或间接地调用直接地或间接地调用自己自己, , 则称这个过程是递归的过程。则称这个过程是递归的过程。当多个函数构成嵌套调用时当多个函数构成嵌套调用时, , 遵循遵循后调用先返回后调用先返回栈栈n以下三种情况常常用到递归方法以下三种情况常常用到递归方法递归定义的数学函数递归定义的数学函数具有递归特性的数据结构具有递归特性的数据结构可递归求解的问题可递归求解的问题1. 递归定义的数学函数递归定义的

25、数学函数: 阶乘函数阶乘函数: 0n ) 1(0n 1)(若若nFactnnFact 2阶阶Fibonaci数列数列: )2() 1(1n 10n 0)(其它若若nFibnFibnFib 树树 2. 2. 具有递归特性的数据结构具有递归特性的数据结构: :RootRootLchildLchildRchildRchild 广义表广义表 A=(a,A)A=(a,A)3. 3. 可递归求解的问题可递归求解的问题: : 迷宫问题迷宫问题HanoiHanoi塔问题塔问题 分治法：分治法：对于一个较为复杂的问题，能够分解成几对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解个相

26、对简单的且解法相同或类似的子问题来求解1 1、能将一个问题转变成一个新问题，而新问题与、能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的且这些处理对象是变化有规律的2 2、可以通过上述转化而使问题简化、可以通过上述转化而使问题简化3 3、必须有一个明确的递归出口，或称递归的边界、必须有一个明确的递归出口，或称递归的边界用分治法求解递归问题用分治法求解递归问题必备的三个条件必备的三个条件分治法求解递归问题算法的一般形式：分治法求解递归问题算法的一般形式： void p (参数表参数表)

27、 if （递归结束条件）可直接求解步骤；（递归结束条件）可直接求解步骤；-基本项基本项 else p（较小的参数）；（较小的参数）；-归纳项归纳项 long Fact ( long n ) if ( n = 0) return 1;/基本项基本项 else return n * Fact (n-1); /归纳项归纳项返回返回 2参数参数 2 计算计算 2*Fact(1)返回返回 1参数参数 1 计算计算 1*Fact(0)返回返回 1参数参数 0 直接定值直接定值 = 1if ( n = 0 ) return 1;else return n * Fact (n-1); 求解阶乘求解阶乘 n!

28、n! 的过程的过程 main : Fact(4)返回返回 24 参数参数 4 计算计算 4*Fact(3)返回返回 6参数参数 3 计算计算 3*Fact(2)设有一个递归算法如下设有一个递归算法如下:int X(int n) if(n=3) return 1; else return X(n-2)+X(n-4)+1则计算则计算X(X(8)时需要计算时需要计算X函数函数 次次.D练习练习A. 8 B.9 C.16 D.18规则规则: :(1) (1) 每次只能移动一个圆盘每次只能移动一个圆盘(2) (2) 圆盘可以插在圆盘可以插在A,BA,B和和C C中的任一塔座上中的任一塔座上(3) (3)

29、 任何时刻不可将较大任何时刻不可将较大圆盘压在较小圆盘之上圆盘压在较小圆盘之上Hanoi塔问题塔问题ABCHanoi塔问题塔问题 n = 1n = 1，则直接从，则直接从 A A 移到移到 C C。否则。否则 (1)用用 C 柱做过渡，将柱做过渡，将 A 的的(n-1)个移到个移到 B(2)将将 A 最后一个直接最后一个直接移到移到 C (3)用用 A 做过渡，将做过渡，将 B 的的 (n-1) 个移到个移到 C#includeint c=0;void move(char x,int n,char z)cout+c,n,x,zc调用前调用前, , 系统完成系统完成: :(1)(1)将将实参实参

30、, ,返回地址返回地址等传递给被调用函数等传递给被调用函数(2)(2)为被调用函数的为被调用函数的局部变量局部变量分配存储区分配存储区(3)(3)将控制转移到被调用函数的将控制转移到被调用函数的入口入口调用后调用后, , 系统完成系统完成: :(1)(1)保存被调用函数的计算保存被调用函数的计算结果结果(2)(2)释放被调用函数的释放被调用函数的数据区数据区(3)(3)依照被调用函数保存的依照被调用函数保存的返回地址返回地址将控制转移到将控制转移到调用函数调用函数“层次层次”主函数主函数第第1 1次调用次调用第第 i i 次调用次调用0 0层层1 1层层i i 层层“递归工作栈递归工作栈”“工

31、作记录工作记录”实在参数实在参数, ,局部变量局部变量, ,返回地址返回地址递归函数调用的实现递归函数调用的实现空间效率空间效率时间效率时间效率O(2n)与递归树的结点数成正比与递归树的结点数成正比与递归树的深度成正比与递归树的深度成正比O(n)递归算法的效率分析递归算法的效率分析 1 2 3 4f(1)=1 f(1)+1+f(1)=3 f(2)+1+f(2)=7 f(3)+1+f(3)=15f(n) = 2f(n-1)+1f(n-1) = 2f(n-2)+1f(n-2) = 2f(n-3)+1.f(3) = 2f(2)+1f(2) = 2f(1)+120f(n) = 21f(n-1)+202

32、1f(n-1) = 22f(n-2)+2122f(n-2) = 23f(n-3)+22.2n-3f(3) = 2n-2f(2)+ 2n-32n-2f(2) = 2n-1f(1)+ 2n-2f(n) = 20+21+2n-2+ 2n-1f(1) = 2n-1递归算法的效率分析递归算法的效率分析6464片金片移动次数：片金片移动次数：假如每秒钟一次，共需多长时间呢？假如每秒钟一次，共需多长时间呢？一年大约有一年大约有31536926秒，移完这些金片需要秒，移完这些金片需要多亿年多亿年世界、梵塔、庙宇和众生都已经灰飞烟灭世界、梵塔、庙宇和众生都已经灰飞烟灭 !优点：结构清晰，程序易读优点：结构清晰，

33、程序易读缺点：每次调用要生成工作记录，保存状缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。态信息。时间开销大。递归的优缺点递归的优缺点递归递归非递归非递归3.4 3.4 队列队列队列是一种先进先出队列是一种先进先出(FIFO) 的线性表的线性表. 它只允许在它只允许在表的一端进行插入表的一端进行插入,而在另一端删除元素而在另一端删除元素),(21naaaqa a1 1a a2 2a a3 3a an n.入队列入队列队头队头队尾队尾),(21naaaqa a1 1a a2 2a a3 3a an n.队头队头队尾队尾

34、出队列出队列),(21naaaqa a1 1a a2 2a a3 3a an n.队头队头队尾队尾出队列出队列),(21naaaqa a1 1a a2 2a a3 3a an n.队头队头队尾队尾出队列出队列设栈设栈S S和队列和队列Q Q的初始状态为空，元素的初始状态为空，元素e1e1、e2e2、e3e3、e4e4、e5e5和和e6e6依次通过依次通过S S，一个元素出栈后即，一个元素出栈后即进入进入Q Q，若，若6 6个元素出队的序列是个元素出队的序列是e2e2、e4e4、e3e3、e6e6、e5e5和和e1e1，则栈，则栈S S的容量至少应该是（）。的容量至少应该是（）。 （A）2 （B

35、）3 （C）4 （D）6练习练习B0n , 2 , 1,|niElemSetaaDii数据对象数据对象:数据关系数据关系:端为队列尾端为队列头约定n1111a ,a , 2 , 1,| ,niDaaaaRiiii基本操作基本操作: (1) InitQueue (&Q) /构造空队列构造空队列 (2) DestroyQueue (&Q) /销毁队列销毁队列 (3) ClearQueue (&S) /清空队列清空队列 (4) QueueEmpty(S) /判空判空. 空空-TRUE,ADT Queue 队列的抽象数据类型队列的抽象数据类型 (5) QueueLength(Q

36、) /取队列长度取队列长度 (6) GetHead (Q,&e) /取队头元素取队头元素, (7) EnQueue (&Q,e) /入队列入队列 (8) DeQueue (&Q,&e) /出队列出队列 (9) QueueTraverse(Q,visit() /遍历遍历ADT Queue队列的抽象数据类型队列的抽象数据类型#define M 100 /最大队列长度最大队列长度Typedef struct QElemType *base; /初始化的动态分配存储空间初始化的动态分配存储空间 int front; /头指针头指针 int rear; /尾指针尾指针Sq

37、Queue; 队列的顺序表示用一维数组队列的顺序表示用一维数组baseM队列的顺序表示用一维数组队列的顺序表示用一维数组baseMQ.frontQ.front0 01 12 23 34 45 5Q.rearQ.rearQ.frontQ.frontQ.rearQ.rearJ J1 1J J2 2J J3 3Q.frontQ.frontQ.rearQ.rearJ J3 3Q.frontQ.frontQ.rearQ.rearJ J5 5J J6 6front=rear=0空队标志：空队标志：front= =rear入队：入队：baserear+=x;出队：出队：x=basefront+;Q.fron

38、tQ.frontQ.rearQ.rearJ5J5J6J6Q.frontQ.front0 01 12 23 34 45 5Q.rearQ.rearJ5J5J6J6J1J1J2J2J3J3J4J4存在的问题存在的问题设数组大小为设数组大小为Mfront=0rear=M时时再入队再入队真溢出真溢出front 0rear=M时时再入队再入队假溢出假溢出解决的方法循环队列解决的方法循环队列1 10 0Q.rearQ.rearQ.frontQ.front.base0接在接在baseM-1之之后后若若rear+1=M则令则令rear=0;实现：利用实现：利用“模模”运算运算入队：入队： baserear=x

39、; rear=(rear+1)%M;出队：出队： x=basefront; front=(front+1)%M; J4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfrontJ9J9J8J8J7J7J7,J8,J9J7,J8,J9入队入队队空：队空：front=rearfront=rear队满：队满：front=rearfront=rear解决方案：解决方案：1.1.另外另外设一个标志设一个标志以区别队空、队满以区别队空、队满2 2. .少用一个元素空间少用一个元素空间： 队空：队空：front=rearfront=rear 队满：队满：( (rear+1)

40、%M=frontrear+1)%M=frontJ4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfront0 01 12 23 34 45 5frontfrontJ4,J5,J6J4,J5,J6出队出队rearrear循环队列循环队列#define MAXQSIZE 100 /最大队列长度最大队列长度Typedef struct QElemType *base; /初始化的动态分配存储空间初始化的动态分配存储空间 int front; /头指针头指针 int rear; /尾指针尾指针SqQueue; Status InitQueue (SqQueue &a

41、mp;Q) Q.base =new QElemTypeMAXQSIZE if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; return OK;循环队列初始化循环队列初始化求循环队列的长度求循环队列的长度int QueueLength (SqQueue Q) return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; Status EnQueue(SqQueue &Q,QElemType e) if(Q.rear+1)%MAXQSIZE=Q.front) return ERROR; Q.baseQ.rear=e; Q.r

42、ear=(Q.rear+1)%MAXQSIZE; return OK;循环队列入队循环队列入队Status DeQueue (LinkQueue &Q,QElemType &e) if(Q.front=Q.rear) return ERROR; e=Q.baseQ.front; Q.front=(Q.front+1)%MAXQSIZE; return OK;循环队列出队循环队列出队naaa,21. . . .datadatanextnext队头队头队尾队尾Q.frontQ.frontQ.rearQ.rear链队列链队列typedef struct QNode QElemType

43、 data; struct Qnode *next;Qnode, *QueuePtr;typedef struct QueuePtr front; /队队头指针头指针 QueuePtr rear; /队尾指针队尾指针LinkQueue; 链队列链队列Q.frontQ.rearxQ.frontQ.rearxyQ.frontQ.rearxy(a) 空队列空队列(b) 元素元素x入入队列队列(d) 元素元素x出出队列队列Q.frontQ.rear(c) 元素元素y入入队列队列链队列链队列Status InitQueue (LinkQueue &Q) Q.front=Q.rear=(Queue

44、Ptr) malloc(sizeof(QNode); if(!Q.front) exit(OVERFLOW); Q.front-next=NULL; return OK;链队列初始化链队列初始化Status DestroyQueue (LinkQueue &Q) while(Q.front) Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; return OK;销毁链队列销毁链队列 Status QueueEmpty (LinkQueue Q) return (Q.front=Q.rear); 判断链队列是否为空判断链队列是否为空S

45、tatus GetHead (LinkQueue Q, QElemType &e) if(Q.front=Q.rear) return ERROR; e=Q.front-next-data; return OK;求链队列的队头元素求链队列的队头元素Status EnQueue(LinkQueue &Q,QElemType e) p=(QueuePtr)malloc(sizeof(QNode); if(!p) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;链队列入队链队列入队Q.frontQ.rearxypStatus DeQueue (LinkQueue &Q,QElemType &e) 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;链队列出队链队列出队Q.frontQ.rearxyp【例例】汽车加油站汽车加油站随着城市里汽车数量的急速增长，汽车加油站