数据结构课件 栈和队列

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) ：是一种特殊的线性表（数：是一种特殊的线性表（数据元素之间的关系是线性关系），据元素之间

3、的关系是线性关系），其插入、其插入、删除只能在表的一端进行，另一端固定不动。删除只能在表的一端进行，另一端固定不动。栈顶（栈顶（top ) ：插入、删除的一端；：插入、删除的一端；栈底（栈底（bottom ) ：固定不动的一端；：固定不动的一端；入栈（入栈（push ) ：又称压入，即插入一个元素；：又称压入，即插入一个元素；出栈（出栈（pop) ：又称弹出，即删除一个元素；：又称弹出，即删除一个元素； 一、抽象数据类型栈的定义一、抽象数据类型栈的定义2 、说明：设（说明：设（a1, a2, a3, , an ） 是一个栈是一个栈 （a1, a2, . , ai -1, ai , ai+1,

4、, an ）栈栈底底栈栈顶顶进栈进栈出栈出栈1）表尾称为栈顶，表头称为栈底）表尾称为栈顶，表头称为栈底 ，即，即a1为栈底元素，为栈底元素，an为栈顶元素为栈顶元素;2）在表尾插入元素的）在表尾插入元素的 操作称进栈操作，在表头删除元素的操作称为操作称进栈操作，在表头删除元素的操作称为出栈操作出栈操作;3）元素按）元素按a1, a2, a3, , an 的次序进栈的次序进栈, 第一个进栈的元素一定在第一个进栈的元素一定在栈底，最后一个进栈的元素一定在栈顶栈底，最后一个进栈的元素一定在栈顶, 第一个出栈的元素为栈顶元素；第一个出栈的元素为栈顶元素；栈的示意图栈的示意图栈特点：由于限制了插入删除只

5、能在一端进行，那栈特点：由于限制了插入删除只能在一端进行，那么元素的操作顺序有么元素的操作顺序有“先进后出先进后出”或或“后进先出后进先出”的特点的特点(Last In First out-LIFO First In Last out -FILO ) 第一个进栈的元素在第一个进栈的元素在栈底，最后一个进栈栈底，最后一个进栈的元素在栈顶，第一的元素在栈顶，第一个出栈的元素为栈顶个出栈的元素为栈顶元素，最后一个出栈元素，最后一个出栈的元素为栈底元素的元素为栈底元素课堂练习课堂练习假设有假设有A ， B , C , D 四个元素；它们入栈次四个元素；它们入栈次序为序为A一一 B 一一C 一一D 出栈

6、次序任意，出栈次序任意，请问不可能得到下面哪些出栈序列？请问不可能得到下面哪些出栈序列？( 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 ) C A B D 3 、 栈的基本操作栈的基本操作 1） 初始化操作初始化操作InitStack(&S) 功能：构造一个空栈功能：构造一个空栈S； 2） 销毁栈操作销毁栈操作DestroyStack(&S) 功能：销毁一个已存在的栈功能：销毁一个已存在的栈; 3） 置空栈操作置空栈操作Cle

7、arStack(&S) 功能：将栈功能：将栈S置为空栈置为空栈; 4）判空栈操作）判空栈操作StackEmpty(S) 功能：若栈为空栈，返回功能：若栈为空栈，返回TRUE，否则，否则FALSE 5）取长度操作）取长度操作StackLength(S) 功能：返回栈功能：返回栈S的元素个数的元素个数 6）取栈顶元素操作）取栈顶元素操作GetTop(S, &e) 功能：取栈顶元素，并用功能：取栈顶元素，并用e 返回返回;7）进栈操作）进栈操作Push(&S, e)功能：元素功能：元素e进栈进栈;8）退栈操作）退栈操作Pop(&S, &e) 功能：栈顶元素退栈

8、，并用功能：栈顶元素退栈，并用e返回返回;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端为栈底。基本操作：基本操作：. ADT Stack 二 栈的存储表示和操作的实现和线性表类似，栈也有两种存储表示，其顺序存储结构简称为顺序栈顺序栈。和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最多元素的存

9、储空间。 顺序存储方式：顺序存储方式：同一般线性表的顺序存储结构同一般线性表的顺序存储结构完全相同。完全相同。是利用一组连续的内存单元依次存放是利用一组连续的内存单元依次存放自栈底到栈顶的数据元素自栈底到栈顶的数据元素，栈顶元素的位置由一，栈顶元素的位置由一个称为栈顶指针的变量指示个称为栈顶指针的变量指示 。 实际是栈中元素的个数 顺序栈类型的定义 / 结构定义： typedef struct ElemType *base; / 存储空间基址 int top; / 栈顶指针 int stacksize; / 允许的最大存储空间 Stack; 栈顶指针总是指在栈顶元素的后面一个位置上 top=0

10、123450栈空top123450进栈Atop出栈栈满BCDEF设数组维数为stacksizetop=0,栈空，此时出栈，则下溢（underflow)top= stacksize,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptop特点：简单、方便，但易产生溢出。特点：简单、方便，但易产生溢出。上溢（上溢（Overflow ) 栈已经满，又要压入元素；栈已经满，又要压入元素； 下溢（下溢（Underflow ) 栈已经空，还要弹出元素；栈已经空，还要弹出元素；注：上溢是一种错误，使问题的处理无法进行下去；注：上溢是一种错误，使问题的处理无

11、法进行下去；而下溢一般认为是一种结束条件，即问题处理结束。而下溢一般认为是一种结束条件，即问题处理结束。# #define STACK_INIT_SIZE 100define STACK_INIT_SIZE 100/栈存储空间的初始分配量栈存储空间的初始分配量# #define STACKINCREMENT 10define STACKINCREMENT 10/ / 栈存储空间的分配增量栈存储空间的分配增量typedef structtypedef structSElemType SElemType * *base;base;/栈空间基址栈空间基址称为栈底指针，指向栈底位置称为栈底指针，指向栈

12、底位置SElemType SElemType * *top top /栈顶指针栈顶指针, ,约定栈顶指针指向栈顶元素的约定栈顶指针指向栈顶元素的 /下（后面）一个位置；下（后面）一个位置； int stacksize; int stacksize; /当前分配的栈空间大小当前分配的栈空间大小 / /（以（以sizeof(SElemType)sizeof(SElemType)为单位为单位） SqStackSqStack;/ ;/ SqStack:：结构类型名结构类型名顺序栈的存储表示顺序栈的存储表示 n nn-1n-1i-1i-1i-2i-2 1 1 0 0S.topS.topS.stacksi

13、zeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE初始化操作图示初始化操作图示顺序栈基本操作的算法顺序栈基本操作的算法1）初始化操作）初始化操作InitStack_Sq(SqStack &S) 参数：参数：S是存放栈的结构变量；是存放栈的结构变量； 功能：建一个空栈功能：建一个空栈S；Status InitStack_Sq(SqStack &S) /构造一个空栈构造一个空栈S S.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType); /为顺序栈动态

14、分配存储空间为顺序栈动态分配存储空间 if (! S. base) exit(OVERFLOW); /存储分配失败存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; /InitStack_SqStatus DetroyStack_Sq ( SqStack &S) If (!S.base) return ERROR; /若栈未建立（尚未分配栈空间）若栈未建立（尚未分配栈空间） free (S.base); / 回收栈空间回收栈空间 S.base = S.top = null; S.stacksize = 0; retu

15、rn OK; / DetroyStack_Sq2） 销毁栈操作销毁栈操作 DestroyStack_Sq(SqStack &SSqStack &S ) 功能：销毁一个已存在的栈功能：销毁一个已存在的栈;S.top = nullS.top = nullS.stacksizeS.stacksizeS.base = nullS.base = null 0 0 n nn-1n-1i-1i-1i-2i-2 1 1 0 0a an na ai ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_IN

16、IT_SIZESTACK_INIT_SIZE 销毁前销毁前 销毁后销毁后销毁栈操作图示销毁栈操作图示3）置空栈操作置空栈操作ClearStack_Sq(SqStack &S) 功能：将栈功能：将栈S置为空栈置为空栈 算法算法 Status ClearStack_Sq ( SqStack &S) If (!S.base) return ERROR; / 若栈未建立（尚未分若栈未建立（尚未分 /配栈空间）配栈空间） S.top = S.base ; return OK; / ClearStack_Sq n nn-1n-1i-1i-1i-2i-2 1 1 0 0a an na ai

17、ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE n nn-1n-1i-1i-1i-2i-2 1 1 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEa an na ai ia ai-1i-1a a2 2a a1 1置空栈操作图示置空栈操作图示S.base=S.topS.base=S.top表明栈为空表明栈为空置空前置空前置空后置空后Status

18、GetTop_Sq(SqStack S, SelemType &e) / 若栈不空，则用若栈不空，则用e返回返回S的栈顶元素，并返回的栈顶元素，并返回/OK；否则返回否则返回ERROR if (S.top= =S.base) return ERROR; /若栈为空若栈为空 e = * (S.top-1); return OK;/GetTop_Sq4） 取栈顶元素操作取栈顶元素操作GetTop_Sq(SqStack S, SElemType &e) 功能：取栈顶元素，并用功能：取栈顶元素，并用e返回返回; n nn-1n-1i-1i-1i-2i-2 1 1 0 0a an na

19、ai ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEe ea an n 取栈顶元素操作图示取栈顶元素操作图示5）进栈操作进栈操作Push(SqStack &S, SElemType eSqStack &S, SElemType e) 功能：元素功能：元素e 进栈进栈; 进栈操作主要步骤：进栈操作主要步骤： 1）S是否已满，是否已满， 若若栈栈满，重新分配存储空间；满，重新分配存储空间； 2）将元素将元素e 写入栈顶；写入栈顶； 3）修

20、改栈顶指针，使栈顶指针指向栈顶元素的）修改栈顶指针，使栈顶指针指向栈顶元素的下（后面）一个位置；下（后面）一个位置； n nn-1n-1i-1i-1i-2i-2 0 0n+1n+1n nn-1n-1i-1i-1i-2i-2 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEe ea an na ai ia ai-1i-1a a1 1anana ai ia ai-1i-1a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_S

21、IZESTACK_INIT_SIZE e 进栈前进栈前 e 进栈后进栈后 进栈操作图示进栈操作图示Status Push(SqStack &S, SElemType e) /将元素将元素e插入栈成为新的栈顶元素插入栈成为新的栈顶元素,要考虑上溢情况要考虑上溢情况 if (S.top-S.base=S.stacksize) /栈满，追加存储空间栈满，追加存储空间 S.base= (SElemType * )realloc(S.base, (S.stacksize +STACKINCREMENT) sizeof(ElemType); if (! S. base) exit(OVERFLOW

22、); /存储分配失败存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; /元素元素e 插入栈顶，修改栈顶指针插入栈顶，修改栈顶指针 return OK; /Push进栈操作算法：进栈操作算法：Status Pop(SqStack &S, SElemType &e) /若栈不空，则删除若栈不空，则删除S的栈顶元素，用的栈顶元素，用e 返回其值并返回返回其值并返回OK /否则返回否则返回ERROR if (S.top= = S.base) return ERROR; /栈空，返回栈空，返回

23、ERROR e = * -S.top; /删除栈顶元素，用删除栈顶元素，用e 返回其值，并修返回其值，并修 /改栈顶指针改栈顶指针 return OK; /Pop6）出）出栈操作栈操作Pop(SqStack &S, SElemType &e )功能：栈顶元素退栈，并用功能：栈顶元素退栈，并用e 返回返回;S.topS.topS.stacksizeS.stacksizeS.baseS.base n nn-1n-1i-1i-1i-2i-2 0 0a an na ai ia ai-1i-1a a1 1STACK_INIT_SIZESTACK_INIT_SIZE 出栈操作前出栈操作前n

24、 nn-1n-1i-1i-1i-2i-2 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEa an na ai ia ai-1i-1a a1 1 出栈操作后出栈操作后a an ne e出栈操作图示出栈操作图示链栈链栈即为栈的链式存储结构。 链栈的结点结构和单链表中的结点结构相同。由于栈只在栈顶作插入和删除操作，因此链栈中不需要头结点，但是链栈中指针的方向是从栈顶指向栈底的，这正好和单链表是相反的。 链栈中结点的定义： 链栈结构定义：typedef struct LNode ElemType

25、 data; struct LNode *next;* SLink;typedef struct SLink top; /栈顶指针 int length; /栈中元素个数LStack;链栈的基本操作和顺序栈操作基本相同，只需修改两处：初始化时不需要maxsize的参数在进行入栈操作时不需要顾忌栈的空间是否已经被填满。void InitStack ( LStack &S ) / 构造一个空栈构造一个空栈 SS.top = NULL; / 设栈顶指针的初值为空S.length = 0; / 空栈中元素个数为0 / InitStack void Push ( LStack &S, E

26、lemType e )/ 在栈顶之上插入元素在栈顶之上插入元素 e 为新的栈顶元素为新的栈顶元素p = (LNode *)malloc(sizeof(LNode); / 建新的结点if(!p) exit(1);/ 存储分配失败p - data = e;p - next = S.top;/ 链接到原来的栈顶S.top = p; / 移动栈顶指针+S.length; / 栈的长度增1 / Push .栈底toptopxpbool Pop ( LStack &S, ElemType &e ) / 若栈不空，则删除若栈不空，则删除S的栈顶元素，用的栈顶元素，用 e 返回其值，返回其值，

27、/ 并返回并返回 TRUE；否则返回；否则返回 FALSEif ( !S.top )return FALSE; else e = S.top - data; / 返回栈顶元素 q = S.top; S.top = S.top - next;/ 修改栈顶指针 -S.length; / 栈的长度减1 delete q; / 释放被删除的结点空间 return TRUE; / Pop top .栈底topq 小小 结结 1.栈是限定仅能在表尾一端进行插入、 删除操作的线性表；2. 栈的元素具有后进先出的特点；3. 栈顶元素的位置由一个称为栈顶指针的变量表示，进栈、出栈操作要修改栈顶指针；3.2 栈的

28、应用举例栈的应用举例 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 由上述求解过程可以看出，在计算过程中是从低由上述求解过程可以看出，在计算过程中是从低位到高位顺序产生八进制数的各个数位，而显示位到高位顺序产生八进制数的各个数位，而显示时按照我们的习惯是高位

29、在前，低位在后，即按时按照我们的习惯是高位在前，低位在后，即按从高位到低位的顺序输出从高位到低位的顺序输出, 即后计算出的（高）位即后计算出的（高）位数先输出，具有数先输出，具有后进先出后进先出的特点，因此可将计算的特点，因此可将计算过程中得到的八进制数顺序进栈，出栈序列打印过程中得到的八进制数顺序进栈，出栈序列打印输出的就是对应的八进制数。输出的就是对应的八进制数。3） 算法算法void conversion( ) /对于输入的任意一个非负十对于输入的任意一个非负十/进制整数，打印输出与其等值的八进制数进制整数，打印输出与其等值的八进制数 InitStack(S); /建空栈建空栈 scan

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

31、算法则，上述表达式的计算过程为：按照四则运算法则，上述表达式的计算过程为： 5+6 (1+2)- 4=5+6 3- 4 = 5+18-4= 23-4=19 表达式中运算符的运算顺序为：表达式中运算符的运算顺序为： + ， ， +， -如何确定运算符的运算顺序？如何确定运算符的运算顺序？3） 算符优先关系表算符优先关系表 表达式中任何相邻运算符表达式中任何相邻运算符 1、 2的优先关系有：的优先关系有： 1 2： 1的优先级高于的优先级高于 2 由四则运算法则，可得到如下的算符优先关系表：由四则运算法则，可得到如下的算符优先关系表：+ 21- -* */ /( () )# #+ - + - *

32、* / ( ) # / ( ) # = = = 算符间的优先关系表算符间的优先关系表注：注： 1 2是相邻算符，是相邻算符，1在左在左 2在右在右4) 算符优先算法算符优先算法 我们再来分析一下表达式我们再来分析一下表达式5+4 (1+2)- 6 计算过程：计算过程： 从左向右扫描表达式：从左向右扫描表达式： 遇操作数遇操作数保存；保存；遇运算符号遇运算符号 j与前面的刚扫描过的运算符与前面的刚扫描过的运算符 i比较比较 若若 i j 则保存则保存 j，（，（ 因此已保存的运算符的优先关系为因此已保存的运算符的优先关系为 1 2 3 j 则说明则说明 i是已扫描的运算符中优先级最高者，可进行运

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

34、1c2，c1出栈，从OPND栈取出两个元素（a和b），按c1进行运算，并把运算结果放入OPND栈。(5)重复上述过程，直到表达式求值完毕（OPTR栈为空栈）表达式求值示意图：表达式求值示意图：5+65+6 (1+2)-4 (1+2)-4 toptopbasebaseOPTROPTR栈栈# #OPNDOPND栈栈toptopbasebase5 5toptoptoptop+ +toptop6 6toptoptoptop( (toptop1 1toptop+ +toptop2 2toptoptoptoptoptoptoptop3 3toptoptoptoptoptoptoptoptoptop1818

35、toptoptoptoptoptoptoptop2323toptop- -toptop4 4toptoptoptoptoptoptoptop1919toptoptoptoptoptop5 5读入表达式过程：读入表达式过程： + +6 6( (1 1+ +2 2) )- -4 4# #=19=191+2=36 63=183=185+18=235+18=2323-4=1923-4=193.4 栈的应用举例栈的应用举例 在算符优先算法中，建立了两个工作栈。一个是在算符优先算法中，建立了两个工作栈。一个是OPTR栈，用以保存栈，用以保存运算符运算符,一个是一个是OPND栈，用以保存操作数或运算结果。栈

36、，用以保存操作数或运算结果。 operandType EvaluateExpression( ) /算术表达式求值的算符优先算法。设算术表达式求值的算符优先算法。设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, O

37、P)判断判断c是否是运算符的函数是否是运算符的函数 else 续续 switch (Precede(GetTop(OPTR), c) case : /新输入的算符新输入的算符c优先级低，即栈顶算符优先权优先级低，即栈顶算符优先权 /高高,出栈并将运算结果入栈出栈并将运算结果入栈OPND Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch /while return GetTop(OPND); /EvaluateExpression3括弧匹配检验 假设表达式中

38、允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（ （）或（ ）等为正确的匹配，（ ）或（ （ ）或 ( ( ) ) ）均为错误的匹配。问题：如何检验一个给定表达式中的括弧是否正确匹配？解决办法：用期待的急迫程度这个概念来描述。 对于后出现的左括号,它等待与其匹配的右括号出 现的急迫心情要比先出现的左括号高,也就是说,对 左括号来说,后出现的比先出现的优先等待检测. 对右括号来说,每个出现的右括号要去找在它之前最后出现的那个左括号去匹配.例如考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8显然,必须将先后出现的左括号依次保存,为了反映这个优先程度,保存左括号的结构应该使用栈 对

39、于出现的右括号来说,只要栈顶元素相匹配即可.如果栈顶的左括号正好和它匹配,就可将它从栈顶删除.什么样的情况是“不匹配”的情况呢？1和栈顶的左括弧不相匹配；2栈中并没有左括弧等在那里；3栈中还有左括弧没有等到和它相匹配的右括弧。Bool match()InitStack(S); /初始化栈初始化栈 ch=getchar(); /接收第一个括号接收第一个括号 while(ch!=#) /不是结束符不是结束符 if(ch=(|ch=) /左括号时进栈左括号时进栈 push(S,ch); /if else if(ch=) /) 时检测匹配时检测匹配 if(!StackEmpty(S) gettop(S

40、,e); /取栈顶元素取栈顶元素 if(e=() /匹配成功匹配成功 pop(S); /if else return false; /匹配失败匹配失败 /if /elseElse /时检测匹配时检测匹配 if(!StackEmpty(S) gettop(S,e); /取栈顶元素取栈顶元素 if(e=) /匹配成功匹配成功 pop(S); /if else return false; /匹配失败匹配失败 /if /else ch=getchar();/whileIf(!StackEmpty(S) return false; /栈中还有没有匹配栈中还有没有匹配 /成功的左括号成功的左括号 else

41、 return true;/match算法实现算法实现4.迷宫求解问题计算机解迷宫时，通常用的是“穷举求解穷举求解”的方法. 1进入迷宫之后，不管在迷宫的哪一个位置上，都先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北方向，从一个走得通的方向继续往前直到出口为止；2如果某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通； 为了保证在任何位置上都能沿原路退回，需要用 一个“后进先出”的结构即栈来保存从

42、入口到当前 位置的路径。并且在走出出口之后，栈中保存的 正是一条从入口到出口的路径。算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索；若当前位置“不可通”，则应顺着“来的方向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。 伪码算法 ：设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； / 纳入路径 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为新的当前位置； 否则 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为

43、: 沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通， 则 删去栈顶位置； / 从路径中删去该通道块若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； while (栈不空)； 没有路径存在3.3 栈与递归 由上看到：应用中如果处理数据处理过程具有后由上看到：应用中如果处理数据处理过程具有后进先出的特性，可利用栈来实现数据处理过程。下进先出的特性，可利用栈来实现数据处理过程。下面我们将看到可以用栈来实现递归。面我们将看到可以用栈来实现递归。1什么是递归什么是递归 递归是一个很有用的工具，在数学和程序设计等许多递归是一个很有用的工具，在数学和程

44、序设计等许多领域中都用到了递归。递归定义：简单地说，一个领域中都用到了递归。递归定义：简单地说，一个用自己定义自己的概念用自己定义自己的概念,称为递归定义。称为递归定义。例例 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间接调用自

45、己间接调用自己栈与递归递归是程序设计中的有用工具，下面举例说明递归算法的编写递归是程序设计中的有用工具，下面举例说明递归算法的编写和执行过程。和执行过程。2递归算法的编写递归算法的编写1）将问题用递归的方式描述（定义）将问题用递归的方式描述（定义）2）根据问题的递归描述（定义）编写递归算法）根据问题的递归描述（定义）编写递归算法 问题的递归描述（定义）问题的递归描述（定义） 递归定义包括两项递归定义包括两项 基本项（终止项）基本项（终止项）：描述递归终止时问题的求解；：描述递归终止时问题的求解； 递归项：递归项：将问题分解为与原问题性质相同，但规模较小将问题分解为与原问题性质相同，但规模较小

46、的问题；的问题； 栈与递归栈与递归例例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 栈与递归栈与递归例例2. 编写求解编

47、写求解Hanoi塔问题的递归算法塔问题的递归算法 有三个各为有三个各为X，Y，Z的塔座，在的塔座，在X项有项有n个大小不个大小不同，依小到大编号为同，依小到大编号为1，2n的圆盘。的圆盘。 现要求将现要求将X上上的的n个圆盘移至个圆盘移至Z上，并仍以同样顺序叠放，上，并仍以同样顺序叠放， 圆盘移动圆盘移动时必须遵守下列原则：时必须遵守下列原则：1）每次移动一个盘子；）每次移动一个盘子；2）圆盘可以放在）圆盘可以放在X，Y，Z中的任一塔座上；中的任一塔座上；3）任何时刻都不能将较大的圆盘压放在较小圆盘之上；）任何时刻都不能将较大的圆盘压放在较小圆盘之上；例例 n=3时圆盘移动的过程如下图所示时圆

48、盘移动的过程如下图所示：abc321 11213121栈与递归栈与递归Y YX XZ Z栈与递归栈与递归首先给出求解首先给出求解Hanoi塔问题塔问题 的递归描述（定义）的递归描述（定义） 基本项：基本项： n=1时，将时，将n号圆盘从号圆盘从X移至移至Z； 递归项：递归项： n1时，时， 将将X上上1n-1号圆盘移至号圆盘移至Y； 将将X上的上的n号圆盘从号圆盘从X移至移至Z; 将将Y上上1n-1号圆盘从号圆盘从Y移至移至Z; 将规模为将规模为n n的的问题的求解归问题的求解归结为规模为结为规模为n-n-1 1的问题的求的问题的求解解有了问题的递归定义，很容易写出对应的递归有了问题的递归定义

49、，很容易写出对应的递归算法：算法：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的圆盘从的圆盘从

50、x移到移到z hanoi(n-1, y, x, z)； /将将y上编号为上编号为1至至n-1的圆盘移到的圆盘移到z，x作辅助塔作辅助塔 栈与递归栈与递归3 递归函数的实现递归函数的实现先看一般函数的调用机制如何实现的。先看一般函数的调用机制如何实现的。 A( )B( );C( )B( )C( );调用调用返回返回函数调用顺序 A B C函数返回顺序 C B A后调用的函数先返回后调用的函数先返回 函数调用机制可通过栈来实现函数调用机制可通过栈来实现计算机正是利用栈来实现函计算机正是利用栈来实现函数的调用和返回的数的调用和返回的栈与递归栈与递归我们看一下我们看一下n=3 n=3 阶乘函数阶乘函数

51、fact(n)fact(n)的执行过程的执行过程Main( ) int n=3,y;L y= fact(n);调调用用调用调用int fact (n) If（n=1） return（1）； Else L1 return（n*fact (n-1)）；/factn=3int fact (int n) If（n=1） return（1）； Else L1 return（n*fact (n-1)）；/factn=2int fact (int n) If（n=1） return（1）； Else L1 return（n*fact (n-1)）；/factn=1L 3L 3L1 1L1 1L1 2L1 2

52、返回1 1返回2 2返返回回6 61 1n*fact (n-1)n*fact (n-1)fact(n)返回地址 实参 注意递归调用中 栈的变化2 、队列的特点：由于限制了插入、删除分别在两端进行，、队列的特点：由于限制了插入、删除分别在两端进行，那么元素的操作顺序有那么元素的操作顺序有“先进先出先进先出”或或“后进后出后进后出”的特点的特点（First In First Out-FIFO Last In Last Out - LILO） 1 、队列（、队列（Queue ) ：是一种特殊的线性表是一种特殊的线性表(数据元数据元 之间的关系是线性关系之间的关系是线性关系.其插入、删除分别在表的其插

53、入、删除分别在表的两端进行，一端只能插入、另一端只能删除。两端进行，一端只能插入、另一端只能删除。)队首（队首（front ) ：进行删除的一端；：进行删除的一端；队尾（队尾（rear ) ：进行插入的一端；：进行插入的一端；入队：在队尾插入一个元素；入队：在队尾插入一个元素；出队：在队首删除一个元素；出队：在队首删除一个元素；3.4队列3.4.13.4.1抽象数据类型队列的定义抽象数据类型队列的定义 a1 a2 a3 an入队列队头队尾出队列队列的示意图队列的示意图队列的特点队列的特点先进先出先进先出第一个入队的元素在队头，第一个入队的元素在队头，最后一个入队的元素在队尾，最后一个入队的元素

54、在队尾，第一个出队的元素为队头元素，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素最后一个出队的元素为队尾元素 队列类似于日常的排队，新来的人站在队尾，队头的人进队列类似于日常的排队，新来的人站在队尾，队头的人进行事务处理后离队。行事务处理后离队。 队列通常设置两个变量分别指示队头元素位置和队尾元素队列通常设置两个变量分别指示队头元素位置和队尾元素的位置，这两个变量分别称为队头指针、队尾指针；的位置，这两个变量分别称为队头指针、队尾指针；2. 队列的基本操作队列的基本操作1）初始化操作）初始化操作InitQueue( &Q) 功能：构造一个空队列功能：构造一个空队列Q；2）销

55、毁操作销毁操作DestroyQueue( &Q) 功能：销毁已存在队列功能：销毁已存在队列Q；3）置空操作置空操作ClearQueue(&Q) 功能：功能： 将队列将队列Q置为空队列置为空队列 ；4）判空操作）判空操作QueueEmpty(Q) 功能：若队列功能：若队列Q为空，则返回为空，则返回True，否则返回否则返回False； 5）取队头元素操作取队头元素操作GetHead(Q,&e) 功能：取队头元素，并用功能：取队头元素，并用e返回；返回；6）入队操作入队操作EnQueue( &Q, e ) 功能：将元素功能：将元素e插入插入Q的队尾；的队尾；7）出队

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

57、Length(Q)GetHead(Q,&e)EnQueue(&Q,e) DeQueue(&Q,&e)QueueTraverse(Q,visit( ) ADT Queue 3.队列队列ADT应用举例应用举例 打印机队列管理：打印机队列管理：在一台打印机共享使用时，任何在一台打印机共享使用时，任何时刻它只能处理一个用户的打印请求。打印任务的组时刻它只能处理一个用户的打印请求。打印任务的组织就用一个队列来组织（先请求的，先处理）。织就用一个队列来组织（先请求的，先处理）。当用户发出打印请求时，把打印任务当用户发出打印请求时，把打印任务入队入队；当打印机空闲时，从打印队

58、列中当打印机空闲时，从打印队列中出队出队一个任务；一个任务；当打印机阻塞时当打印机阻塞时,系统管理员可以系统管理员可以清空队列清空队列.1 、存储方式：同一般线性表的顺序存储结构完全、存储方式：同一般线性表的顺序存储结构完全相同。但是由于在两端操作，设两个指示器，相同。但是由于在两端操作，设两个指示器，(rear 和和front ）分别指示队列的尾和首。）分别指示队列的尾和首。特别约定特别约定:头指针始终指向队列头元素，而尾指针头指针始终指向队列头元素，而尾指针 始终指向始终指向 队列尾元素的下一位置！队列尾元素的下一位置！ 空队列：空队列：rear = front = 0 入队：入队：rea

59、r =rear + 1 出队：出队：front = front + 1 队列空：队列空：front = rear 3.4.2 队列的顺序存储结构特点特点:简单简单,方便方便,但是易产生但是易产生假假 溢出溢出.只是称为指针，实现时不一定用指针变量2.队列的简单操作的实现队列的简单操作的实现(1）初始化）初始化 Q .front = Q.rear =0 ;(2）入队）入队Q .baseQ .reare ; Q .rear + + ;(3）出队）出队Q .front + + ;(4）判空）判空Q .front = = Q .rear ;(5）求队长）求队长Q .rear-Q .front思考：顺序

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