华师本科生数据结构课件 第4章 栈与队列

1、引例,餐馆中一叠一叠的盘子：如果它们是按 1,2,n 的次序往上叠的，那么使用时候的次序应是什么样的？,必然是依从上往下的次序，即n,2,1。它们遵循的是后进先出的规律，这正是本章要讨论的栈的结构特点。,是排队。在计算机程序中，模拟排队的数据结构是队列。,栈和队列是两种特殊的线性表,是操作受限的线性表,称限定性数据结构。,在日常生活中，为了维持正常的社会秩序而出现的常 见现象是什么？,第4章 栈和队列,4.1 栈 4.2 栈的应用举例 4.3 队列 4.4 队列应用举例,【学习目标】,掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。 熟练掌握栈类型的两种实现方法。 熟练掌握循环队列和链队列的基本操作实现算法。 理解递归算法执行过程中栈的状态变化过程。,【重点和难点】,栈和队列是在程序设计中被广泛使用的两种线性数据结构，本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。,重点：栈和队列的基本特征，表示与实现 难点：递归、循环队列 算法：栈和队列的实现及其应用,顺序栈、链栈、递归、循环队列、链队列,【知识点】,【学习指南】,本章主要是学习如何在求

2、解应用问题中适当地应用栈和队列,栈和队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。,本章要求必须完成的算法设计题为： 4.1, 4.2, 4.3, 4.4, 4.5, 4.6, 4.9, 4.11, 4.12,4.1 栈,是限定仅在表尾进行插入或删除操作的线性表。 允许插入,删除的一端称为栈顶(top),另一端称为栈底(bottom),top,bottom,进栈,出栈,an . . . . a1,基本操作：,后进先出(LIFO),定义：,栈 特殊的线性表：操作受限的线性表,逻辑特征：,创建一个空栈； 判断栈是否为空栈； 判断栈是否为满； 往栈中插入(或称推入)一个元素； 从栈中删除(或称弹出)一个元素； 求栈顶元素的值。 访问栈中每个元素,栈和队列是两种常用的数据类型,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x)Insert(Q, n+1, x) 1in+1 Delete(L, i)

3、Delete(S, n) Delete(Q, 1) 1in,一般线性表 堆栈 逻辑结构：一对一 逻辑结构：一对一 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 运算规则：后进先出(LIFO),1. 定义,与线性表相同,仍为一对一关系。,用顺序栈或链栈存储均可,顺序栈更常见,只能在栈顶运算,且访问结点时依照后进先出(LIFO)或先进后出(FILO)的原则。,关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同。 基本操作有入栈、出栈、读栈顶元素值、建栈、判栈满、判栈空等。,限定只能在表的一端进行插入和删除运算的线性表(只能在栈顶操作),4.1.1 栈的特点和操作,例如： 栈 s = ( a1 , a2, a3, , an-1, an ),an 称为栈顶元素,插入元素到栈顶(即表尾)的操作，称为入栈。 从栈顶(即表尾)删除最后一个元素的操作，称为出栈。,强调：插入和删除都只能在表的一端（栈顶）进行！,a1 称为栈底元素,栈是仅在表尾进行插入、删除操作的线性表。 表尾(即 an 端)称为栈顶 top ; 表头(即 a1 端)称为栈底base,“进” 压入=PUS

4、H（x) “出” 弹出=POP ( y ),4.1.1 栈的特点和操作,栈的基本操作,InitStack(,顺序栈中的PUSH函数 status Push( ElemType x ) if ( topM ) 上溢 else vtop+ = x; ,Push( B );,Push( C );,Push( D );,低地址L,Push( A );,高地址M,B,C,D,出栈操作: 例如从栈中取出B（注意要遵循“后进先出” 原则）,核心语句： Pop ( ); Pop ( ); Printf( Pop () );,顺序栈中的POP函数 status Pop( ) if ( top=L ) 下溢 else y = v-top; return( y ); ,若入栈动作使地址向高端增长，称为“向上生成”的栈； 若入栈动作使地址向低端增长，称为“向下生成”的栈； 对于向上生成的栈 入栈口诀：堆栈指针top先压后加（vtop+=x）； 出栈口诀：堆栈指针top先减后弹（y=v-top) 。,栈不存在的条件：base=NULL; 栈为空 的条件 ： base=top; 栈满的条件 ： top-base=

5、stacksize;,问：为什么要设计堆栈？它有什么独特用途？,调用函数或子程序非它莫属； 递归运算的有力工具； 用于保护现场和恢复现场； 简化了程序设计的问题。,答：,问：栈是什么？ 它与一般线性表有什么不同？,答：栈是一种特殊的线性表,它只能在表的一端(即栈顶)进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。,例 对于一个栈,给出输入项A、B、C,如果输入项序列由ABC组成， 试给出所有可能的输出序列。,A进 A出 B进 B出 C进 C出 ABC A进 A出 B进 C进 C出 B出 ACB A进 B进 B出 A出 C进 C出 BAC A进 B进 B出 C进 C出 A出 BCA A进 B进 C进 C出 B出 A出 CBA 不可能产生输出序列CAB,例 一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？,43512不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，只需压入一个立即弹出一个即可。,435612中到了12顺序不能实现； 135426可以实现。,例 如果一个栈的输入序列为12345

6、6，能否得到435612和135426的出栈序列？,答：,答：,例：设依次进入一个栈的元素序列为c,a,b,d, 则可得到出栈的元素序列是： ）a,b,c,d）c,d,a,b）b,c,d,a）a,c,d,b,A、D可以( B、C不行)。,讨论：有无通用的判别原则？ 有。在可能的输出序列中，不存在这样的输入序列i,j,k，能同时满足 ijk 和 PjPkPi,答：,SqStack：结构类型名； SqStack: 它的三个域分别是： base： 栈底指针，指向栈底位置； top： 栈顶指针； Stacksize：已分配的存储空间(一元素为单位)大小；,const STACK_INIT_SIZE 100 const STACKINCREMENT 10 typedef struct SElemType *elem; int top /栈顶指针 int stacksize; int increment; SqStack;,顺序栈算法,约定栈顶指针指向栈顶元素的下(后面)一个位置,void InitStack_Sq(SqStack /InitStack_Sq,1) 初始化操作InitStack_S

7、q(SqStack struct node *next; Node; typedef LinkList LinkStack;,栈底,top,q,链栈的定义,typedef int bool; #define TRUE 1; #define FALSE 0; typedef int Data; typedef struct node ElemType data; struct node *next; LNode; Typedef LinkList LinkStack,初始化 void InitStack_L( LinkStack *S ) S = NULL; 入栈 void Push_L ( LinkStack *S, ElemType e ) LNode *p = new LNode ; p-data = e; p-next = S; S = p; ,顺序栈算法,入栈算法,栈底,x,p,判栈空 bool StackEmpty_L( LinkStack *S ) return !S; 出栈 bool Pop_L( LinkStack *S, ElemType *e ) if ( S )

8、LNode *p = S; S = S-next; *e = p-data; delete p; return TRUE; else return FALSE; ,取栈顶 bool GetTop_L( LinkStack *S, ElemType *e ) if ( !S ) return 0; else *e = S-data; return 1; 置栈空 int MakeEmpty_L( LinkStack *S ) Lnode *p; while( S ) p = S; S = S-next; delete p; ,链栈算法,出栈算法,栈底,top,X,3.2 栈的应用举例,例一、 数制转换,例二、 括号匹配的检验,例三、 背包问题求解,例四、 表达式求值,例五、 实现递归,例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2,计算顺序,输出顺序,算法基于原理：N = (N div d)d + N mod d,例一 数制转换,void conversion () Init

9、Stack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion,假设在表达式中: （）或（ ） 等为正确的格式，（ ）或（ ）或 ( ( ) ) 均为不正确的格式。,检验括号是否匹配的方法可用 “期待的急迫程度” 来描述。,例二 括号匹配的检验,例如: 考虑下列括号序列: ( ) 1 2 3 4 5 6 7 8,分析可能出现的不匹配的情况:,算法的设计思想,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空,若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈” 否则表明不匹配,3）表达式检验结束时，若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余,bool matching(string exp ) int state = 1; ch = *exp+； while ( ch != # ,设有一个背包可以放入的物品的重量为s，现有n件物品，重量分别为w1,w2,wn。问能否从这n件物品中选择若干件放入此背包中，使得放入的重量之和正好为s。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真)；否则称此背包问题无解(或称其解为假)。,例三 背包问题,一个背包可以放入的物品重量为s, 现有n件物品, 重量分别为w1,w2,wn,问能否从这些物品中选若干件放入背包中, 使得放入的重量之和正好是s。如果存在一种符合上述要求的选择,则称此背包问题有解,否则此问题无解。,例三 背包问题,如果有解： 1. 选择的一组物品中不包含wn; knap( s,n-1 ) 的解就是knap( s,n)的解； 2. 选择的一组物品中包含wn;

《华师本科生数据结构课件 第4章 栈与队列》由会员小****分享，可在线阅读，更多相关《华师本科生数据结构课件 第4章 栈与队列》请在金锄头文库上搜索。