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

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

2、的规则进行操作。 和线性表相比，它们的插入和删除操作受更多的 约束和限定，故又称为限定性的线性表结构。,插 入 删 除线性表： 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),第三章 栈和队列 3.1 栈,1 、栈（stack) ：是一种特殊的线性表（数据元素之间的关系是线性关系），其插入、删除只能在表的一端进行，另一端固定不动。,栈顶（top ) ：插入、删除的一端；栈底（bottom ) ：固定不动的一端；入栈（push ) ：又称压入，即插

3、入一个元素； 出栈（pop) ：又称弹出，即删除一个元素；,一、抽象数据类型栈的定义,2 、说明：设（a1, a2, a3, , an ） 是一个栈,（a1, a2, . , ai -1, ai , ai+1, , an ）,栈底,栈顶,进栈,出栈,1）表尾称为栈顶，表头称为栈底 ，即a1为栈底元素，an为栈顶元素;,2）在表尾插入元素的 操作称进栈操作，在表头删除元素的操作称为出栈操作;,3）元素按a1, a2, a3, , an 的次序进栈, 第一个进栈的元素一定在栈底，最后一个进栈的元素一定在栈顶, 第一个出栈的元素为栈顶元素；,栈的示意图,栈特点：由于限制了插入删除只能在一端进行，那么

4、元素的操作顺序有“先进后出”或“后进先出”的特点(Last In First out-LIFO First In Last out -FILO ),第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素,课堂练习,假设有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 ) A C B D ( 6 ) D B A C ( 7 ) A D C B ( 8 )

5、C A B D,3 、 栈的基本操作 1）初始化操作InitStack( 4）判空栈操作StackEmpty(S) 功能：若栈为空栈，返回TRUE，否则FALSE 5）取长度操作StackLength(S) 功能：返回栈S的元素个数,6）取栈顶元素操作GetTop(S, 7）栈遍历StackTraverse(S) 功能：从栈底到栈顶依次调用函数visit().,4、栈的ADT描述,栈的抽象数据类型定义为： ADT Stack 数据对象：Dai|aiElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1 , ai D, i=2,.,n 约定an端为栈顶,a1端为栈底。 基本操

6、作： . ADT Stack,二 栈的存储表示和操作的实现,和线性表类似，栈也有两种存储表示，其顺 序存储结构简称为顺序栈。 和顺序表类似，对顺序栈也需要事先为它分 配一个可以容纳最多元素的存储空间。,顺序存储方式：同一般线性表的顺序存储结构完全相同。是利用一组连续的内存单元依次存放自栈底到栈顶的数据元素，栈顶元素的位置由一个称为栈顶指针的变量指示 。,实际是栈中元素的个数,顺序栈类型的定义 / 结构定义： typedef struct ElemType *base; / 存储空间基址 int top; / 栈顶指针 int stacksize; / 允许的最大存储空间 Stack;,栈顶指针

7、总是指在栈顶元素的后面一个位置上,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为stacksize top=0,栈空，此时出栈，则下溢（underflow) top= stacksize,栈满，此时入栈，则上溢（overflow),特点：简单、方便，但易产生溢出。 上溢（Overflow ) 栈已经满，又要压入元素； 下溢（Underflow ) 栈已经空，还要弹出元素；,注：上溢是一种错误，使问题的处理无法进行下去； 而下溢一般认为是一种结束条件，即问题处理结束。,#define STACK_INIT_SIZE 100/栈存储空间的初始分配量 #define STACKINCREME

8、NT 10/ 栈存储空间的分配增量typedef structSElemType *base;/栈空间基址称为栈底指针，指向栈底位置SElemType *top /栈顶指针,约定栈顶指针指向栈顶元素的 /下（后面）一个位置； int stacksize; /当前分配的栈空间大小 /（以sizeof(SElemType)为单位）SqStack;/ SqStack:：结构类型名,顺序栈的存储表示,STACK_INIT_SIZE,初始化操作图示,顺序栈基本操作的算法1）初始化操作InitStack_Sq(SqStack struct LNode *next; * SLink;,typedef str

9、uct SLink top; /栈顶指针 int length; /栈中元素个数 LStack;,链栈的基本操作和顺序栈操作基本相同，只 需修改两处： 初始化时不需要maxsize的参数 在进行入栈操作时不需要顾忌栈的空间 是否已经被填满。,void InitStack ( LStack / 空栈中元素个数为0 / InitStack,void Push ( LStack / 栈的长度增1 / Push,bool Pop ( LStack / Pop,小 结,1.栈是限定仅能在表尾一端进行插入、 删除操作的线性表； 2. 栈的元素具有后进先出的特点； 3. 栈顶元素的位置由一个称为栈顶指针的变

10、量表示，进栈、出栈操作要修改栈顶指针；,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 mod d (其中：div 为整除运算，mod 为求余运算) 例如：(1348)10 = (2504)8,由上述求解过程可以看出，在计算过程中是从低位到高位顺序产生八进制数的各个数位，而显示时按照我们的习惯是高位在前，低位在后，即按从高位到低位的顺序输出, 即后计

11、算出的（高）位数先输出，具有后进先出的特点，因此可将计算过程中得到的八进制数顺序进栈，出栈序列打印输出的就是对应的八进制数。,3） 算法 void conversion( ) /对于输入的任意一个非负十 /进制整数，打印输出与其等值的八进制数 InitStack(S); /建空栈 scanf(“%d”, N); /输入一个非负十进制整数 while(N) / N不等于零，循环 Push(S, N % 8); / N/8第一个余数进栈 N=N/8 ; /整除运算 while(! StackEmpty) /输出存放在栈中的八进制数。 Pop(S, e); Printf(“%d”, e); /con

12、version,2 表达式求值 1） 表达式的构成 操作数+运算符+界符（如括号） 2） 表达式的求值： 例 5+6 (1+2)- 4 按照四则运算法则，上述表达式的计算过程为： 5+6 (1+2)- 4=5+6 3- 4 = 5+18-4= 23-4=19 表达式中运算符的运算顺序为： + ， ， +， - 如何确定运算符的运算顺序？,3） 算符优先关系表 表达式中任何相邻运算符1、2的优先关系有： 12：1的优先级高于2由四则运算法则，可得到如下的算符优先关系表：,算符间的优先关系表,注： 1 2是相邻算符，1在左 2在右,4) 算符优先算法 我们再来分析一下表达式5+4 (1+2)- 6

13、 计算过程：,从左向右扫描表达式： 遇操作数保存； 遇运算符号j与前面的刚扫描过的运算符i比较 若ij 则说明i是已扫描的运算符中优先级最高者，可进行运算； 若i = j 则i为（，j 为 ），说明括号内的式子已计算完，需要消去括号；,5+4 (1+2)- 6,后面也许有优先级更大的算符,算法思想：,(1) 设置两个栈：运算符栈（OPTR)和操作数栈（OPND) (2)设置数据栈为空栈，表达式起始符“#”为算符栈的栈底元素。 (3)自左向右，依次扫描表达式中的基本符号，若扫描的基本符号为操作数，则将操作数入OPND栈。 (4)若基本符号为运算符，则和OPTR栈顶元素的优先级比较（栈顶元素为C1

14、,读到的算符为C2）： （a）c1c2，c1出栈，从OPND栈取出两个元素（a和b），按c1进行运算，并把运算结果放入OPND栈。 (5)重复上述过程，直到表达式求值完毕（OPTR栈为空栈）,表达式求值示意图：5+6(1+2)-4,#,5,+,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 栈的应用举例,在算符优先算法中，建立了两个工作栈。一个是OPTR栈，用以保存运算符,一个是OPND栈，用以保存操作数或运算结果。operandType EvaluateEx

15、pression( ) /算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。 InitStack(OPTR); Push (OPTR, #); InitStack(OPND); c=qetchar( ); While(c!= # | GetTop(OPTR)!=#) if (! In (c, OP) Push(OPND, c); c=getchar( ) /不是运算符则进栈,In(c, OP)判断c是否是运算符的函数 else,续 switch (Precede(GetTop(OPTR), c) case : /新输入的算符c优先级低，即栈顶算符优先

16、权 /高,出栈并将运算结果入栈OPND Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch /while return GetTop(OPND); /EvaluateExpression,3括弧匹配检验 假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（ （）或（ ）等为正确的匹配，（ ）或（ （ ）或 ( ( ) ) ）均为错误的匹配。 问题：如何检验一个给定表达式中的括弧是否正确匹配？ 解决办法：用期待的急迫程度这个概念来描述。,对于后

17、出现的左括号,它等待与其匹配的右括号出 现的急迫心情要比先出现的左括号高,也就是说,对 左括号来说,后出现的比先出现的优先等待检测. 对右括号来说,每个出现的右括号要去找在它之前最后出现的那个左括号去匹配.,例如考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8,显然,必须将先后出现的左括号依次保存,为了反映这个优先程度,保存左括号的结构应该使用栈 对于出现的右括号来说,只要栈顶元素相匹配即可.如果栈顶的左括号正好和它匹配,就可将它从栈顶删除.,什么样的情况是“不匹配”的情况呢？ 1和栈顶的左括弧不相匹配； 2栈中并没有左括弧等在那里； 3栈中还有左括弧没有等到和它相匹配的右括弧。,B

18、ool match() InitStack(S); /初始化栈 ch=getchar(); /接收第一个括号 while(ch!=#) /不是结束符 if(ch=(|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(

19、S); /if else return false; /匹配失败 /if /else ch=getchar(); /while If(!StackEmpty(S) return false; /栈中还有没有匹配 /成功的左括号 else return true; /match,算法实现,4.迷宫求解问题计算机解迷宫时，通常用的是“穷举求解”的方法. 1进入迷宫之后，不管在迷宫的哪一个位置上，都先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北方向，从一个走得通的方向继续往前直到出口为止； 2如果某个位置上四个方向都走不通的话，就退回到前一个位置，换一个

20、方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通；,为了保证在任何位置上都能沿原路退回，需要用 一个“后进先出”的结构即栈来保存从入口到当前 位置的路径。并且在走出出口之后，栈中保存的 正是一条从入口到出口的路径。,算法的基本思想是： 若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置” 探索； 若当前位置“不可通”，则应顺着“来的方向”退回到“前一通道 块”，然后朝着除“来向”之外的其他方向继续探索； 若该通道块的四周四个方块均“不可通”，则应从“当前路径”上 删除该通道块。,伪码算法

21、： 设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； / 纳入路径 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为新的当前位置； 否则 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置 的下一相邻块；若栈不空但栈顶位置的四周均不可通， 则 删去栈顶位置； / 从路径中删去该通道块若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； while (栈不空)；,没有路径存在,3.3 栈与递归,由上看到：应用中如果处理数据处理过程具有后进先出的特性，可利用栈来实现数据处理过程。下面我们

22、将看到可以用栈来实现递归。 1什么是递归 递归是一个很有用的工具，在数学和程序设计等许多领域中都用到了递归。递归定义：简单地说，一个用自己定义自己的概念,称为递归定义。 例 n!= 1 2 3 4 (n-1) n n!递归定义 n!= 1 当 n=0时 n!= n (n-1)! 当n 0时,用(n-1)!定义n!,栈与递归,2.递归函数：一个直接调用自己或通过一系列调用 间接调用自己的函数称为递归函数。,A（ ） A( ) ; ,B( ) C( ) C( ); B( ); ,A 直接调用自己,B间接调用自己,栈与递归,递归是程序设计中的有用工具，下面举例说明递归算法的编写和执行过程。 2递归算

23、法的编写 1）将问题用递归的方式描述（定义） 2）根据问题的递归描述（定义）编写递归算法 问题的递归描述（定义） 递归定义包括两项 基本项（终止项）：描述递归终止时问题的求解； 递归项：将问题分解为与原问题性质相同，但规模较小 的问题；,栈与递归,例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

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

25、从X移至Z; 将Y上1n-1号圆盘从Y移至Z;,将规模为n的问题的求解归结为规模为n-1的问题的求解,有了问题的递归定义，很容易写出对应的递归算法：,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,

26、y, x, z)； /将y上编号为1至n-1的圆盘移到z，x作辅助塔 ,栈与递归,3 递归函数的实现 先看一般函数的调用机制如何实现的。,A( ) B( ); ,C( ) ,B( ) C( ); ,后调用的函数先返回,函数调用机制可通过栈来实现,计算机正是利用栈来实现函数的调用和返回的,栈与递归,我们看一下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),返回地址 实参,注意递归调用中 栈的变化,2 、队列的特点：由于限制了插入、删除分

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

28、元素在队头，最后一个入队的元素在队尾， 第一个出队的元素为队头元素， 最后一个出队的元素为队尾元素,队列类似于日常的排队，新来的人站在队尾，队头的人进 行事务处理后离队。 队列通常设置两个变量分别指示队头元素位置和队尾元素 的位置，这两个变量分别称为队头指针、队尾指针；,2. 队列的基本操作 1）初始化操作InitQueue( (2）入队Q .baseQ .reare ; Q .rear + + ; (3）出队Q .front + + ; (4）判空Q .front = = Q .rear ; (5）求队长Q .rear-Q .front,思考：顺序队列存在的问题及解决方案,可以看出：当入队一

29、个元素时，可能会出现假 溢出现象.即：空间并没有使用完，但不能入队！ 解决的办法：,( 1 ）平移，一旦发生假溢出，把队列中所有元素移到队列开头效率低( 2 ）使用动态数组，当产生假溢出或真溢出时，都重新分配一个更大的空间（不可取） ( 3 ）使用环数组，即将顺序存储的空间视为一个环空间。,3.4.3 循环队列存储结构及操作实现,方式：将顺序队列臆造为一个环状的空间，如图所示，称之为循环队列.指针和队列元素之间的关系不变,这种循环的圈只是一种逻辑上的圈,在物理上还是一组连续的存储单元,仍可利用数组实现.,1.存储结构及操作实现,循环队列可充分利用空间，但仍存在问题： 我们知道：队列为空时front = rear 右图中，继续入队a7 ,