1,第 三 章 栈 和 队 列,2,栈和队列是重要的数据结构 栈和队列是线性表的子集 （是插入和删除受限的线性表）,前言,3,【学习目标】 1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。 2. 熟练掌握栈类型的两种实现方法。 3. 熟练掌握循环队列和链队列的基本操作实现算法。 4. 理解递归算法执行过程中栈的状态变化过程。 【重点和难点】 栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。,4,【学习指南】 在这一章中，主要是学习如何在求解应用问题中适当地应用栈和队列，栈和队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。,5,【课前思考】 1. 什么是线性结构？ 简单地说，线性结构是一个数据元素的序列。 2. 你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,n 的次序往上叠的, 那么使用时候的次序应是什么样的？ 必然是依从上往下的次序，即n,2,1。它们遵循的是“后进先出“的规律，这正是本章要讨论的“栈“的结构特点。 3. 在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？ 是“排队“。在计算机程序中，模拟排队的数据结构是“队列“。,6,栈必须按“后进先出”的规则进行操作 队列必须按“先进先出”的规则进行操作 和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构 从“数据结构”的角度看: 它们都是线性结构，即数据元素之间的关系相同。 但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的“限定“。,7,通常称，栈和队列是限定插入 和删除只能在表的“端点”进行的 线性表。,线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in,栈和队列是两种常用的数据类型,8,3.1 栈,9,3.1.1 栈的类型定义 栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。在表中，允许插入和删除的一端称作“栈顶(top)”，不允许插入和删除的一端称作“栈底(bottom)“ 。,10,通常称往栈顶插入元素的操作为“入栈“，称删除栈顶元素的操作为“出栈“。因为后入栈的元素先于先入栈的元素出栈，故被称为是一种“后进先出“的结构，因此又称LIFO（Last In First Out的缩写）表。很多书上都以如下图所示的铁路调度站形象地表示栈的这个特点。,11,栈的类型定义,12,InitStack(&S) DestroyStack(&S) ClearStack(&S) StackEmpty(S) StackLength(S) GetTop(S, &e) Push(&S, e) Pop(&S, &e) StackTravers(S, visit(),13,InitStack(&S) 操作结果：构造一个空栈S。,DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。,14,StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALSE。 判定栈是否为空栈是栈在应用程序 中经常使用的操作，通常以它作为循环结束的条件。,15,StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数， 即栈的长度。,16,GetTop(S, &e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回 S 的栈顶元素,并 不将它从栈中删除。,a1,a2,an, ,e,17,ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。,18,Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈 顶元素。,19,Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素， 并用 e 返回其值。,a1,a2,an,an-1, ,e,20,StackTraverse(S, visit( ) 初始条件：栈 S 已存在且非空，visit( )为 元素的访问函数。 操作结果：从栈底到栈顶依次对S的每个 元素调用函数visit( )，一旦 visit( )失败，则操作失败。 这是对栈进行从栈底到栈顶的“遍历”操作，应用较多的场合是，输出栈中所有数据元素。,21,顺序栈,3.1.2 栈的表示和实现,类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。,/- 栈的顺序存储表示 - #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;,22,实现：一维数组sM,进栈,A,栈满,B,C,D,E,F,设数组维数为M top=base,栈空,此时出栈,则下溢（underflow) top=M,栈满,此时入栈,则上溢（overflow),空栈,出栈,栈空,栈底指针base,始终指向栈底位置；栈顶指针top,其初值指向栈底，始终在栈顶元素的下一个位置,A,B,23,Status InitStack (SqStack ,24,Status Push (SqStack ,25,Status Pop (SqStack ,26,在一个程序中同时使用两个栈：,27,3.2 栈的应用举例,由于栈的操作具有后进先出的固有特性，致使栈成为程序设计中的有用工具。凡应用问题求解的过程具有“后进先出“的天然特性的话，则求解的算法中也必然需要利用“栈“。,28,栈的应用举例,例一、 数制转换,例二、 括号匹配的检验,例三、 行编辑程序问题,例四、 迷宫求解,例五、 表达式求值,例六、 实现递归,29,例一、 数制转换 十进制数N和其他d进制数的转换是 计算机实现计算的基本问题，其解决方 法很多，其中一个简单算法基于下列原 理： N = (N div d)d + N mod d (其中：div为整除运算，mod为求余运算),30,N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,计算顺序,输出顺序,例如：（1348)10 = (2504)8 ， 其运算过程如下：,31,void conversion () InitStack(S); / 构造空栈 scanf (“%d“, / conversion,32,例二、 括号匹配的检验 假设在表达式中 （）或（ ） 等为正确的格式， （ ）或（ ）或 （） ）均为不正确的格式。,则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。,33,即后出现的“左括弧“，它等待与其匹配的“右括弧“出现的“急迫“心情要比先出现的左括弧高。换句话说，对“左括弧“来说，后出现的比先出现的“优先“等待检验，对“右括弧“来说，每个出现的右括弧要去找在它之前“最后“出现的那个左括弧去匹配。显然，必须将先后出现的左括弧依次保存，为了反映这个优先程度，保存左括弧的结构用栈最合适。这样对出现的右括弧来说，只要“栈顶元素“相匹配即可。如果在栈顶的那个左括弧正好和它匹配，就可将它从栈顶删除。,34,分析可能出现的不匹配的情况:,到来的右括弧并非是所“期待”的；,例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8,到来的是“不速之客”；,直到结束，也没有到来所“期待” 的括弧。,35,这三种情况对应到栈的操作即为： 1和栈顶的左括弧不相匹配； 2栈中并没有左括弧等在哪里； 3栈中还有左括弧没有等到和它 相匹配的右括弧。,36,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余， 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” ， 否则表明不匹配。,3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括弧”有余。,37,Status matching(char exp ) int state = 1; while (i=Length(exp) .,38,例三、行编辑程序问题,如何实现？,“每接受一个字符即存入存储器” ?,并不恰当！,39,设立一个输入缓冲区，用以接 受用户输入的一行字符，然后逐行 存入用户数据区,并假设“#”为退格 符，“”为退行符。,在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。,合理的作法是：,40,假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);,则实际有效的是下列两行： while (*s) putchar(*s+);,41,可设这个输入缓冲区为一个栈结构，每当从终端接受了一个字符之后先作如下判断： 1、既不是退格也不是退行符，则将该字符压入栈顶； 2、如果是一个退格符，则从栈顶删去一个字符； 3、如果是一个退行符，则将字符栈清为空栈 。,42,while (ch != EOF / 从终端接收下一个字符 ,ClearStack(S); / 重置S为空栈 if (ch != EOF) ch = getchar( ); ,ch=getchar(); ClearStack(S); / 重置S为空栈 while (ch != EOF) /EOF为全文结束符,将从栈底到栈顶的字符传送至调用过程的数据区；,43,例四、 迷宫求解,通常用的是“穷举求解”的方法,44,为了保证在任何位置上都能沿原路退回,需要用一个“后进先出”的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后,栈中保存的正是一条从入口到出口的路径 所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。 “纳入路径”的操作即为“当前位置入栈； “从当前路径上删除前一通道块”的操作 即为“出栈“。,45,迷宫路径算法的基本思想：,若当前位置“可通”,则纳入路径， 继续前进;,若当前位置“不可通”,则后退,换方 向继续探索;,若四周“均无通路”,则将当前位置 从路径中删除出去。,46,设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻 方块为新 的当前位置； 否则 若栈不空且栈顶位置尚有其他方向未 被探索，,求迷宫中一条从入口到出口的路径的算法：,47,则设定新的当前位置为: 沿顺时针方向转找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则 删去栈顶位置；/ 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈 空； while (栈不空)；,若栈空，则表明迷宫没有通路