第三章(数据结构)汇编.pptx

第三章 栈和队列 第1页 【学习目标】 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。 2. 熟练掌握栈类型的两种实现方法。 3. 熟练掌握循环队列和链队列的基本操作实现算法。 4. 理解递归算法执行过程中栈的状态变化过程。 【知识点】 顺序栈、链栈、循环队列、链队列 注意它们的基本操作实现时的特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法 。 【学习指南】 第2页 栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按后进先出的规则进行操作，而队列必须按先进先出的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。 和线性表相比，从数据结构的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的限定。 第3页 线性表： Insert(L,i,x)　　 Delete(L,i)　　　　　 　 (1≤i≤n+1)　 　(1≤i≤n)　　栈：　　Insert(L,n+1,x) 　Delete(L,n)　　　队列：　Insert(L,n+1,x)　 Delete(L,1) 插 入 删 除 线性表允许在表内任一位置进行插入和删除； 栈只允许在表尾一端进行插入和删除； 队列只允许在表尾一端进行插入，在表头一端进行删除。 第4页 3.1.1栈的类型定义 栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。在表中，允许插入和删除的一端称作栈顶(top)，不允许插入和删除的另一端称作栈底(bottom) 。 通常称往栈顶插入元素的操作为入栈，称删除栈顶元素的操作为出栈。因为后入栈的元素先于先入栈的元素出栈，故被称为是一种后进先出的结构，因此又称LIFO（LastIn First Out的缩写）表 如左图所示的铁路调度站表示栈的特点 第5页 类型定义如下： ADT Stack {　 数据对象：D＝{ ai| ai?∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ ai-1,ai| ai-1,ai∈D, i=2,...,n }　　　　　　　　　约定 an端为栈顶，a1 端为栈底。 基本操作： InitStack(S) 构造一个空栈 S。 DestroyStack(S) 初始条件：栈 S 已存在。操作结果：栈 S 被销毁。 ClearStack(S) 初始条件：栈 S 已存在。操作结果：将 S 清为空栈。  StackEmpty(S) 判空，通常以它作为循环结束的条件 GetTop(S, e) 取栈顶元素，只以 e 返回栈顶元素，并不从栈中删除 Push(S, e) 入栈操作 Pop(S, e) 出栈操作，不仅以 e 返回栈顶元素，并将它从栈中删除。 } ADT Stack 第6页 3.1.2 栈的存储表示和操作的实现 一、顺序栈类型的定义 和线性表类似，栈也有两种存储表示，其顺序存储结构简称为顺序栈。 和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最多元素的存储空间，base 为这个存储空间的基地址，也即一维数组的地址。 从名称来讲，“栈顶指针”意为指示栈顶元素在栈中的位置，但它的值实际是栈中元素的个数，和顺序表中的 length 值的意义相同。 为了应用方便，这个最大空间的容量应由使用这个顺序栈的程序员决定，它的默认值和顺序表的默认值相同。 第7页 顺序栈的结构 top指向压栈时下一个元素将要存放的位置。 出栈时top减一指向弹栈时下一个元素的取值位置。 栈空的条件：top=base 栈满的条件：top-base = stacksize ? ? ? ? ? ? 栈的表示和实现 非空非满栈 第8页 顺序表示 #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; 　其中stacksize表示栈当前可以使用的最大容量。Base为栈底，Top为栈顶。栈顶指针指向栈顶元素的下一个位置（即下次压栈时元素所放的位置） ? ? ? ? ? ? 顺序队列 第9页 基本操作的