数据结构栈和队列课件.ppt

《数据结构栈和队列课件.ppt》由会员分享，可在线阅读，更多相关《数据结构栈和队列课件.ppt（102页珍藏版）》请在三一办公上搜索。

1、第三章 栈和队列,1,t课件,第三章 栈和队列,本章学习两种特殊的线性数据结构，它们特殊在定义的操作不同，即插入和删除操作只能在线性表的两端进行。 只能在一端进行的- 栈 分别在两端进行的- 队列,2,t课件,重点本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。知识点 顺序栈、链栈、循环队列、链队列,3,t课件,. 你见过餐馆中一叠一叠的盘子吗？如果它 们是按1,2,n 的次序往上叠的，那么使用时候 的次序应是什么样的？. 在日常生活中，为了维持正常的社会秩序 而出现的常见现象是什么？,4,t课件,栈和队列是在程序设计中被广泛使用的两种线性数据结构栈必须按“后进先出”的规则

2、进行操作，而队列必须按“先进先出”的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。,5,t课件,插 入 删 除线性表： Insert(L,i,x) Delete(L,i) (1in+1) (1in)栈：Insert(L,n+1,x) Delete(L,n)队列：Insert(L,n+1,x) Delete(L,1),6,t课件,第三章 栈和队列 3.1 栈,1 、栈（stack) ：是一种特殊的线性表（数据元素之间的关系是线性关系），其插入、删除只能在表的一端进行，另一端固定不动。,栈顶（top ) ：插入、删除的一端；栈底（bottom )

3、：固定不动的一端；入栈（push ) ：又称压入，即插入一个元素；出栈（pop) ：又称弹出，即删除一个元素；,一、抽象数据类型栈的定义,7,t课件,2 、说明：设（a1, a2, a3, , an ） 是一个栈,（a1, a2, . , ai -1, ai , ai+1, , an ）,栈底,栈顶,进栈,出栈,1）表尾称为栈顶，表头称为栈底 ，即a1为栈底元素，an为栈顶元素;,2）在表尾插入元素的 操作称进栈操作，在表头删除元素的操作称为出栈操作;,3）元素按a1, a2, a3, , an 的次序进栈, 第一个进栈的元素一定在栈底，最后一个进栈的元素一定在栈顶, 第一个出栈的元素为栈顶元

4、素；,8,t课件,栈的示意图,栈特点：由于限制了插入删除只能在一端进行，那么元素的操作顺序有“先进后出”或“后进先出”的特点(Last In First out-LIFO First In Last out -FILO ),第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素,9,t课件,课堂练习,假设有A ， B , C , D 四个元素；它们入栈次序为A一 B 一C 一D 出栈次序任意，请问不可能得到下面哪些出栈序列？( 1 ) A B C D ( 2 ) D B C A ( 3 ) C D B A ( 4 ) C B A D (5 )

5、 A C B D ( 6 ) D B A C ( 7 ) A D C B ( 8 ) C A B D,10,t课件,3 、 栈的基本操作 1）初始化操作InitStack( 4）判空栈操作StackEmpty(S) 功能：若栈为空栈，返回TRUE，否则FALSE 5）取长度操作StackLength(S) 功能：返回栈S的元素个数,11,t课件,6）取栈顶元素操作GetTop(S, 7）栈遍历StackTraverse(S) 功能：从栈底到栈顶依次调用函数visit().,12,t课件,4、栈的ADT描述,栈的抽象数据类型定义为： ADT Stack 数据对象：Dai|aiElemSet, i

6、=1,2,.,n, n0 数据关系：R1 | ai-1 , ai D, i=2,.,n 约定an端为栈顶,a1端为栈底。基本操作：. ADT Stack,13,t课件,二 栈的存储表示和操作的实现,和线性表类似，栈也有两种存储表示，其顺序存储结构简称为顺序栈。和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最多元素的存储空间。,14,t课件,顺序存储方式：同一般线性表的顺序存储结构完全相同。是利用一组连续的内存单元依次存放自栈底到栈顶的数据元素，栈顶元素的位置由一个称为栈顶指针的变量指示 。,15,t课件,实际是栈中元素的个数,顺序栈类型的定义 / 结构定义： typedef struct

7、 ElemType *base; / 存储空间基址 int top; / 栈顶指针 int stacksize; / 允许的最大存储空间 Stack;,栈顶指针总是指在栈顶元素的后面一个位置上,16,t课件,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为stacksizetop=0,栈空，此时出栈，则下溢（underflow)top= stacksize,栈满，此时入栈，则上溢（overflow),17,t课件,特点：简单、方便，但易产生溢出。上溢（Overflow ) 栈已经满，又要压入元素； 下溢（Underflow ) 栈已经空，还要弹出元素；,注：上溢是一种错误，使问题的处理无

8、法进行下去；而下溢一般认为是一种结束条件，即问题处理结束。,18,t课件,#define STACK_INIT_SIZE 100/栈存储空间的初始分配量#define STACKINCREMENT 10/ 栈存储空间的分配增量typedef structSElemType *base;/栈空间基址称为栈底指针，指向栈底位置SElemType *top /栈顶指针,约定栈顶指针指向栈顶元素的 /下（后面）一个位置； int stacksize; /当前分配的栈空间大小 /（以sizeof(SElemType)为单位）SqStack;/ SqStack:：结构类型名,顺序栈的存储表示,19,t课件

9、,STACK_INIT_SIZE,初始化操作图示,顺序栈基本操作的算法1）初始化操作InitStack_Sq(SqStack &S) 参数：S是存放栈的结构变量； 功能：建一个空栈S；,20,t课件,Status InitStack_Sq(SqStack /InitStack_Sq,21,t课件,Status DetroyStack_Sq ( SqStack / DetroyStack_Sq,2） 销毁栈操作 DestroyStack_Sq(SqStack ,22,t课件,S.top = null,S.stacksize,S.base = null,0,销毁前,销毁后,销毁栈操作图示,23,t

10、课件,3）置空栈操作ClearStack_Sq(SqStack / ClearStack_Sq,24,t课件,置空栈操作图示,S.base=S.top表明栈为空,置空前,置空后,25,t课件,Status GetTop_Sq(SqStack S, SelemType /GetTop_Sq,4） 取栈顶元素操作GetTop_Sq(SqStack S, SElemType ,26,t课件,取栈顶元素操作图示,27,t课件,5）进栈操作Push(SqStack 进栈操作主要步骤： 1）S是否已满， 若栈满，重新分配存储空间； 2）将元素e 写入栈顶； 3）修改栈顶指针，使栈顶指针指向栈顶元素的下（后

11、面）一个位置；,28,t课件,nn-1i-1i-2 0,anaiai-1a1,S.top,S.stacksize,S.base,e 进栈前,e 进栈后,进栈操作图示,29,t课件,Status Push(SqStack /Push,进栈操作算法：,30,t课件,Status Pop(SqStack /Pop,6）出栈操作Pop(SqStack ,31,t课件,出栈操作前,出栈操作图示,32,t课件,链栈,链栈即为栈的链式存储结构。 链栈的结点结构和单链表中的结点结构相同。由于栈只在栈顶作插入和删除操作，因此链栈中不需要头结点，但是链栈中指针的方向是从栈顶指向栈底的，这正好和单链表是相反的。,3

12、3,t课件,链栈中结点的定义：链栈结构定义：,typedef struct LNode ElemType data; struct LNode *next;* SLink;,typedef struct SLink top; /栈顶指针 int length; /栈中元素个数LStack;,34,t课件,链栈的基本操作和顺序栈操作基本相同，只需修改两处：初始化时不需要maxsize的参数在进行入栈操作时不需要顾忌栈的空间是否已经被填满。,35,t课件,void InitStack ( LStack / 空栈中元素个数为0 / InitStack,36,t课件,void Push ( LStac

13、k / 栈的长度增1 / Push,37,t课件,bool Pop ( LStack / Pop,38,t课件,小 结,1.栈是限定仅能在表尾一端进行插入、 删除操作的线性表；2. 栈的元素具有后进先出的特点；3. 栈顶元素的位置由一个称为栈顶指针的变量表示，进栈、出栈操作要修改栈顶指针；,39,t课件,3.2 栈的应用举例,N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,输出顺序,计算顺序,数制转换 十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：N = (N div d)d + N

14、 mod d (其中：div 为整除运算，mod 为求余运算)例如：(1348)10 = (2504)8,40,t课件,由上述求解过程可以看出，在计算过程中是从低位到高位顺序产生八进制数的各个数位，而显示时按照我们的习惯是高位在前，低位在后，即按从高位到低位的顺序输出, 即后计算出的（高）位数先输出，具有后进先出的特点，因此可将计算过程中得到的八进制数顺序进栈，出栈序列打印输出的就是对应的八进制数。,41,t课件,3） 算法void conversion( ) /对于输入的任意一个非负十/进制整数，打印输出与其等值的八进制数 InitStack(S); /建空栈 scanf(“%d”, N);

15、 /输入一个非负十进制整数 while(N) / N不等于零，循环 Push(S, N % 8); / N/8第一个余数进栈 N=N/8 ; /整除运算 while(! StackEmpty) /输出存放在栈中的八进制数。 Pop(S, e); Printf(“%d”, e); /conversion,42,t课件,2 表达式求值1） 表达式的构成 操作数+运算符+界符（如括号）2） 表达式的求值： 例 5+6 (1+2)- 4 按照四则运算法则，上述表达式的计算过程为： 5+6 (1+2)- 4=5+6 3- 4 = 5+18-4= 23-4=19 表达式中运算符的运算顺序为： + ， ，

16、+， -如何确定运算符的运算顺序？,43,t课件,3） 算符优先关系表 表达式中任何相邻运算符1、2的优先关系有： 12：1的优先级高于2由四则运算法则，可得到如下的算符优先关系表：,44,t课件,算符间的优先关系表,注： 1 2是相邻算符，1在左 2在右,45,t课件,4) 算符优先算法 我们再来分析一下表达式5+4 (1+2)- 6 计算过程：,从左向右扫描表达式： 遇操作数保存；遇运算符号j与前面的刚扫描过的运算符i比较 若ij 则说明i是已扫描的运算符中优先级最高者，可进行运算； 若i = j 则i为（，j 为 ），说明括号内的式子已计算完，需要消去括号；,5+4 (1+2)- 6,后

17、面也许有优先级更大的算符,46,t课件,算法思想：,(1) 设置两个栈：运算符栈（OPTR)和操作数栈（OPND)(2)设置数据栈为空栈，表达式起始符“#”为算符栈的栈底元素。(3)自左向右，依次扫描表达式中的基本符号，若扫描的基本符号为操作数，则将操作数入OPND栈。(4)若基本符号为运算符，则和OPTR栈顶元素的优先级比较（栈顶元素为C1,读到的算符为C2）： （a）c1c2，c1出栈，从OPND栈取出两个元素（a和b），按c1进行运算，并把运算结果放入OPND栈。(5)重复上述过程，直到表达式求值完毕（OPTR栈为空栈）,47,t课件,表达式求值示意图：5+6(1+2)-4,#,5,+,

18、6,(,1,+,2,3,18,23,-,4,19,5,读入表达式过程：,+,6,(,1,+,2,),-,4,#,=19,1+2=3,63=18,5+18=23,23-4=19,3.4 栈的应用举例,48,t课件,在算符优先算法中，建立了两个工作栈。一个是OPTR栈，用以保存运算符,一个是OPND栈，用以保存操作数或运算结果。operandType EvaluateExpression( ) /算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。 InitStack(OPTR); Push (OPTR, #); InitStack(OPND); c=qe

19、tchar( ); While(c!= # | GetTop(OPTR)!=#) if (! In (c, OP) Push(OPND, c); c=getchar( ) /不是运算符则进栈,In(c, OP)判断c是否是运算符的函数 else,49,t课件,续 switch (Precede(GetTop(OPTR), c) case : /新输入的算符c优先级低，即栈顶算符优先权 /高,出栈并将运算结果入栈OPND Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; /

20、switch /while return GetTop(OPND); /EvaluateExpression,50,t课件,3括弧匹配检验 假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（ （）或（ ）等为正确的匹配，（ ）或（ （ ）或 ( ( ) ) ）均为错误的匹配。问题：如何检验一个给定表达式中的括弧是否正确匹配？解决办法：用期待的急迫程度这个概念来描述。,51,t课件,对于后出现的左括号,它等待与其匹配的右括号出 现的急迫心情要比先出现的左括号高,也就是说,对 左括号来说,后出现的比先出现的优先等待检测. 对右括号来说,每个出现的右括号要去找在它之前最后出现的那个

21、左括号去匹配.,52,t课件,例如考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8,显然,必须将先后出现的左括号依次保存,为了反映这个优先程度,保存左括号的结构应该使用栈 对于出现的右括号来说,只要栈顶元素相匹配即可.如果栈顶的左括号正好和它匹配,就可将它从栈顶删除.,53,t课件,什么样的情况是“不匹配”的情况呢？1和栈顶的左括弧不相匹配；2栈中并没有左括弧等在那里；3栈中还有左括弧没有等到和它相匹配的右括弧。,54,t课件,Bool match()InitStack(S); /初始化栈 ch=getchar(); /接收第一个括号 while(ch!=#) /不是结束符 if(c

22、h=(|ch=) /左括号时进栈 push(S,ch); /if else if(ch=) /) 时检测匹配 if(!StackEmpty(S) gettop(S,e); /取栈顶元素 if(e=() /匹配成功 pop(S); /if else return false; /匹配失败 /if /else,Else /时检测匹配 if(!StackEmpty(S) gettop(S,e); /取栈顶元素 if(e=) /匹配成功 pop(S); /if else return false; /匹配失败 /if /else ch=getchar();/whileIf(!StackEmpty(S)

23、 return false; /栈中还有没有匹配 /成功的左括号 else return true;/match,算法实现,55,t课件,4.迷宫求解问题计算机解迷宫时，通常用的是“穷举求解”的方法. 1进入迷宫之后，不管在迷宫的哪一个位置上，都先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北方向，从一个走得通的方向继续往前直到出口为止；2如果某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通；,5

24、6,t课件,为了保证在任何位置上都能沿原路退回，需要用 一个“后进先出”的结构即栈来保存从入口到当前 位置的路径。并且在走出出口之后，栈中保存的 正是一条从入口到出口的路径。,57,t课件,算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索；若当前位置“不可通”，则应顺着“来的方向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。,58,t课件,伪码算法 ：设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； / 纳入路径 若该位置是出口位置，则算法

25、结束； 否则切换当前位置的东邻方块为新的当前位置； 否则 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通， 则 删去栈顶位置； / 从路径中删去该通道块若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； while (栈不空)；,没有路径存在,59,t课件,3.3 栈与递归,由上看到：应用中如果处理数据处理过程具有后进先出的特性，可利用栈来实现数据处理过程。下面我们将看到可以用栈来实现递归。1什么是递归 递归是一个很有用的工具，在数学和程序设计等许多领域中都用到了递归。递归定

26、义：简单地说，一个用自己定义自己的概念,称为递归定义。例 n!= 1 2 3 4 (n-1) n n!递归定义 n!= 1 当 n=0时 n!= n (n-1)! 当n 0时,用(n-1)!定义n!,60,t课件,栈与递归,2.递归函数：一个直接调用自己或通过一系列调用间接调用自己的函数称为递归函数。,A（ ） A( ) ; ,B( ) C( ) C( ); B( ); ,A 直接调用自己,B间接调用自己,61,t课件,栈与递归,递归是程序设计中的有用工具，下面举例说明递归算法的编写和执行过程。2递归算法的编写1）将问题用递归的方式描述（定义）2）根据问题的递归描述（定义）编写递归算法问题的递

27、归描述（定义） 递归定义包括两项 基本项（终止项）：描述递归终止时问题的求解； 递归项：将问题分解为与原问题性质相同，但规模较小 的问题；,62,t课件,栈与递归,例1 编写求解 阶乘n! 的递归算法首先给出阶乘n! 的递归定义 n!的递归定义 基本项： n!=1 当 n=1 递归项： n!=n (n-1)! 当 n 1 有了问题的递归定义，很容易写出对应的递归算法：int fact (int n) /算法功能是求解并返回n的阶乘 If（n=1） return（1）； Else return（n*fact (n-1)）；/fact,63,t课件,栈与递归,例2. 编写求解Hanoi塔问题的递归

28、算法 有三个各为X，Y，Z的塔座，在X项有n个大小不同，依小到大编号为1，2n的圆盘。 现要求将X上的n个圆盘移至Z上，并仍以同样顺序叠放， 圆盘移动时必须遵守下列原则：1）每次移动一个盘子；2）圆盘可以放在X，Y，Z中的任一塔座上；3）任何时刻都不能将较大的圆盘压放在较小圆盘之上；例 n=3时圆盘移动的过程如下图所示：,64,t课件,栈与递归,Y,X,Z,65,t课件,栈与递归,首先给出求解Hanoi塔问题 的递归描述（定义） 基本项： n=1时，将n号圆盘从X移至Z； 递归项： n1时， 将X上1n-1号圆盘移至Y； 将X上的n号圆盘从X移至Z; 将Y上1n-1号圆盘从Y移至Z;,将规模为

29、n的问题的求解归结为规模为n-1的问题的求解,有了问题的递归定义，很容易写出对应的递归算法：,66,t课件,void hanoi (int n, char x, char y, char z) /将塔座x上按直径由小到大且自上而下编号为1至n的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。 if (n= =1) move(x,1,z); /将编号为1的圆盘从x移动z else hanoi(n-1, x, z, y); /将x上编号为1至n-1的圆盘移到y, z作辅助塔 move(x, n, z); /将编号为 n的圆盘从x移到z hanoi(n-1, y, x, z)； /将y上编号为1至n-

30、1的圆盘移到z，x作辅助塔 ,67,t课件,栈与递归,3 递归函数的实现先看一般函数的调用机制如何实现的。,A( )B( );,C( ),B( )C( );,后调用的函数先返回,函数调用机制可通过栈来实现,计算机正是利用栈来实现函数的调用和返回的,68,t课件,栈与递归,我们看一下n=3 阶乘函数fact(n)的执行过程,Main( ) int n=3,y;L y= fact(n);,L 3,L1 1,L1 2,1,n*fact (n-1),n*fact (n-1),fact(n),返回地址 实参,注意递归调用中 栈的变化,69,t课件,2 、队列的特点：由于限制了插入、删除分别在两端进行，那

31、么元素的操作顺序有“先进先出”或“后进后出”的特点（First In First Out-FIFO Last In Last Out - LILO）,1 、队列（Queue ) ：是一种特殊的线性表(数据元 之间的关系是线性关系.其插入、删除分别在表的两端进行，一端只能插入、另一端只能删除。),队首（front ) ：进行删除的一端；队尾（rear ) ：进行插入的一端；入队：在队尾插入一个元素；出队：在队首删除一个元素；,3.4队列,3.4.1抽象数据类型队列的定义,70,t课件,a1 a2 a3 an,入队列,队头,队尾,出队列,队列的示意图,队列的特点先进先出,第一个入队的元素在队头，最

32、后一个入队的元素在队尾，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素,队列类似于日常的排队，新来的人站在队尾，队头的人进行事务处理后离队。 队列通常设置两个变量分别指示队头元素位置和队尾元素的位置，这两个变量分别称为队头指针、队尾指针；,71,t课件,2. 队列的基本操作1）初始化操作InitQueue( &Q) 功能：构造一个空队列Q；2）销毁操作DestroyQueue( &Q) 功能：销毁已存在队列Q；3）置空操作ClearQueue(&Q) 功能： 将队列Q置为空队列 ；4）判空操作QueueEmpty(Q) 功能：若队列Q为空，则返回True，否则返回False；,72,

33、t课件,5）取队头元素操作GetHead(Q,&e) 功能：取队头元素，并用e返回；6）入队操作EnQueue( &Q, e ) 功能：将元素e插入Q的队尾；7）出队操作DeQueue( &Q, &e) 功能：若队列不空，则删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR；,73,t课件,队列的抽象数据类型定义： ADT Queue 数据对象：Dai|aiElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1,ai D, i=2,.,n约定其中a1端为队列头，an端为队列尾,74,t课件,基本操作： InitQueue(&Q) DestroyQueue(&Q)

34、 ClearQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)EnQueue(&Q,e) DeQueue(&Q,&e)QueueTraverse(Q,visit( ) ADT Queue,75,t课件,3.队列ADT应用举例,打印机队列管理：在一台打印机共享使用时，任何时刻它只能处理一个用户的打印请求。打印任务的组织就用一个队列来组织（先请求的，先处理）。当用户发出打印请求时，把打印任务入队；当打印机空闲时，从打印队列中出队一个任务；当打印机阻塞时,系统管理员可以清空队列.,76,t课件,1 、存储方式：同一般线性表的顺序存储结构完全相同。但是由

35、于在两端操作，设两个指示器，(rear 和front ）分别指示队列的尾和首。特别约定:头指针始终指向队列头元素，而尾指针 始终指向 队列尾元素的下一位置！ 空队列：rear = front = 0 入队：rear =rear + 1 出队：front = front + 1 队列空：front = rear,3.4.2 队列的顺序存储结构,77,t课件,特点:简单,方便,但是易产生假 溢出.,78,t课件,只是称为指针，实现时不一定用指针变量,79,t课件,2.队列的简单操作的实现,(1）初始化 Q .front = Q.rear =0 ;(2）入队Q .baseQ .reare ; Q .

36、rear + + ;(3）出队Q .front + + ;(4）判空Q .front = = Q .rear ;(5）求队长Q .rear-Q .front,80,t课件,思考：顺序队列存在的问题及解决方案,可以看出：当入队一个元素时，可能会出现假溢出现象.即：空间并没有使用完，但不能入队！解决的办法：,( 1 ）平移，一旦发生假溢出，把队列中所有元素移到队列开头效率低( 2 ）使用动态数组，当产生假溢出或真溢出时，都重新分配一个更大的空间（不可取）( 3 ）使用环数组，即将顺序存储的空间视为一个环空间。,81,t课件,3.4.3 循环队列存储结构及操作实现,方式：将顺序队列臆造为一个环状的空

37、间，如图所示，称之为循环队列.指针和队列元素之间的关系不变,这种循环的圈只是一种逻辑上的圈,在物理上还是一组连续的存储单元,仍可利用数组实现.,82,t课件,1.存储结构及操作实现,循环队列可充分利用空间，但仍存在问题：我们知道：队列为空时front = rear 右图中，继续入队a7 ,a8 ，则front=rear 即：队列为空或队列为满时，都是front = rear ，如何区分？,83,t课件,两种方法1. 设置标志位以区别队列是“空”还是“满” 因出队而相等，则为空； 因入队而相等，则为满；2. 少用一个元素的空间，约定rear+1=front 时，就认为队满,84,t课件,2.循环

38、队列存储结构及操作实现,#define MAXSIZE 100 / 最大队列长度typedef struct QElemType *base; /初始化时动态分配 /存储空间的基址 int front; /队头指针，指向队头元素 int rear; /队尾指针，指向队尾元素的下 /一个位置SqQueue;,85,t课件,1）初始化操作InitQueue_Sq(SqQueue &Q) 参数：Q是存放队列的结构变量； 功能：建一个空队列Q；,循环队列的基本操作算法,建一个空队列Q,86,t课件,Status InitQueue_Sq(SqQueue / InitQueue_Sq,算法：,87,t课

39、件,2) 入队操作EnQueue_Sq(SqQueue &Q, QElemType e ) 功能：将元素e插入队尾 ； 入队操作主要步骤： 1）Q是否已满， 若满，返回ERROR；否则转2）； 2）将元素e 写入队尾； 3）修改队尾指针，使队尾指针指向队尾元素的下一个位置；,元素e入队前,元素e入队后,88,t课件,Status EnQueue_Sq(SqQueue / EnQueue_Sq,入队操作算法,89,t课件,3) 出队操作DeQueue_Sq (SqQueue 出队操作主要步骤： 1）Q是否为空， 若空，返回ERROR；否则转2）； 2）将队头元素赋值给e； 3）修改队头指针，删除

40、队头元素；,出队操作前,出队操作后,90,t课件,Status DeQueue_Sq(SqQueue / EnQueue_Sq,出队操作算法,91,t课件, 3.4.4 链式队列的表示和实现,1 、存储方式：同一般线性表的单链式存储结构完全相同。但是由于插入、删除在两端进行，需要两个指针front 、rear 分别指向队列的两端。有两种不同的链法：,哪个好?,92,t课件,入队都很容易，但是出队差别很大！! 应该用第1 种链法。为了处理空队列，可以加上头结点。,2 、特点：没有假溢出，提高了空间利用率。只有系统没有空间了，才会溢出；,93,t课件,2. 链式存储结构。,设队首、队尾指针fron

41、t和rear,front指向头结点，rear指向队尾,94,t课件,95,t课件,3 链队列的实现,typedef struct QNode /链队列结点的类型定义 QElemType data;/用于存放队列元素 struct QNode *next;/用于存放元素直接后继 /结点的地址QNode,*QueuePtr;typedef struct/链队列的表头结点的的类型定义QueuePtr front; /队头指针，指向链表的头结点QueuePtr rear; /队尾指针，指向队尾结点LinkQueue;,结构类型；,表示链队列的一个结点,指针变量用于存放链队列结点的地址,结构类型用于存放

42、队头指针、队尾指针,96,t课件,设Q为LinkQueue类型的变量，Q为链队列的表头结点，用于存储队列队头指针和队尾指针；初始建队时，令Q.front=Q.rear=null;,空链队列,链队列的表头结点,链队列的表头结点,链队列图示,链队列的头结点,97,t课件,4.操作实现,1）初始化操作InitQueue_L(LinkQueue /InitQueue_L,空链队列,链队列的表头结点,链队列的头结点,98,t课件,2) 销毁操作DestroyQueue_L(LinkQueue /DestroyQueue_L,Q.front,Q.rear,nullnull,销毁前,销毁后,99,t课件,e入队前,e入队后,3）入队操作EnQueue_L(LinkQueue &Q, QElemType )入队操作图示,100,t课件,Status EnQueue_L(LinkQueue ,Q.front,Q.rear,在链队列Q队尾，插入新的元素e,101,t课件,4）出队操作DeQueue_L(LinkQueue ,Q.front,Q.rear,102,t课件,