,Page 1,2019/1/16,学习目标 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。 熟练掌握栈类型的两种实现方法。 熟练掌握循环队列和链队列的基本操作实现算法。 理解递归算法执行过程中栈的状态变化过程。 重点和难点 栈和队列是在程序设计中被广泛使用的两种线性数据结构，本章的学习重点是掌握这两种结构的特点，以便能在应用问题中正确使用。 知识点 顺序栈、链栈、循环队列、链队列,第三章 栈和队列,Page 2,2019/1/16,栈和队列是在程序设计中被广泛使用的两种线性数据结构。 与线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。 线性表允许在表内任一位置进行插入和删除； 栈只允许在表尾一端进行插入和删除； 队列只允许在表尾一端进行插入，在表头一端进行删除。,Page 3,2019/1/16,3.1 栈,栈 限定只能在表的一端进行插入和删除操作的线性表。 栈顶(top)：允许插入和删除的一端。 栈底(bottom)：不允许插入和删除的另一端。 空栈：不含元素的空表。 特点 先进后出（FILO） 后进先出（LIFO）,Page 4,2019/1/16,栈的抽象数据类型定义,ADT Stack 数据对象：Dai| ai ElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1,aiD, i=2,.,n 基本操作： InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。,Page 5,2019/1/16,ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈 StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回TRUE，否则返回 FALSE。 StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回栈 S 中元素个数，即栈的长度。,Page 6,2019/1/16,GetTop(S, &e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回S的栈顶元素。 Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。 Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。,Page 7,2019/1/16,StackTraverse(S, visit( ) 初始条件：栈 S 已存在且非空，visit( )为元素的访问 函数。 操作结果：从栈底到栈顶依次对S的每个元素调用函数 visit( )，一旦visit( )失败，则操作失败。 ADT Stack,Page 8,2019/1/16,栈的顺序存储（顺序栈）,利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。 结构定义： #define STACK_INIT_SIZE 100; / 存储空间初始分配量 #define STACKINCREMENT 10; / 存储空间分配增量 typedef struct SElemType *base; / 存储空间基址 SElemType *top; / 栈顶指针 int stacksize; / 当前已分配的存储空间，以元素位单位 SqStack;,Page 9,2019/1/16,base,栈空,栈顶指针top,指向实际栈顶 后的空位置，top=base,进栈,A,出栈,栈满,B,C,D,E,F,设数组大小为M top=base,栈空，此时出栈，则下溢（underflow) Top-base=6,栈满，此时入栈，则上溢（overflow),栈空,top,Page 10,2019/1/16,基本操作接口(函数声明),void InitStack (SqStack /若栈不空，则删除S的栈顶元素，用e返回其值，并返回TRUE；否则返回FALSE。 void StackTraverse(SqStack S, Status (*visit() /依次对S的每个元素调用函数 visit( )，一旦 visit( )失败，操作失败。,Page 11,2019/1/16,基本操作的算法描述,Status InitStack (SqStack /InitStack,Page 12,2019/1/16,Status GetTop (SqStack S, SElemType /GetTop,Page 13,2019/1/16,Status Push (SqStack /Push,Page 14,2019/1/16,Status Pop (Stack /Pop,Page 15,2019/1/16,链栈(栈的链式存储结构),Page 16,2019/1/16,入栈算法,出栈算法,Page 17,2019/1/16,3.4 队列,队列 只允许在一端进行插入而在另一端进行删除的线性表。 队尾：允许插入的一端。 队头：允许删除的一端。 特点：先进先出（FIFO）。,Page 18,2019/1/16,队列的抽象数据类型定义,ADT Queue 数据对象：Dai|aiElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1,ai D, i=2,.,n 基本操作： InitQueue(&Q) 操作结果：构造一个空队列 Q。 DestroyQueue(&Q) 初始条件：队列 Q 已存在。 操作结果：队列 Q 被销毁，不再存在。,Page 19,2019/1/16,ClearQueue(&Q) 初始条件：队列 Q 已存在。 操作结果：将 Q 清为空队列。 QueueEmpty(Q) 初始条件：队列 Q 已存在。 操作结果：若 Q 为空队列，则返回TRUE，否则返回 FALSE。 QueueLength(Q) 初始条件：队列 Q 已存在。 操作结果：返回 Q 的元素个数，即队列的长度。,Page 20,2019/1/16,GetHead(Q,&e) 初始条件：Q 为非空队列。 操作结果：用 e 返回Q的队头元素。 EnQueue(&Q,e) 初始条件：队列 Q 已存在。 操作结果：插入元素 e 为 Q 的新的队尾元素。 DeQueue(&Q,&e) 初始条件：Q 为非空队列。 操作结果：删除 Q 的队头元素，并用 e 返回其值。 ,Page 21,2019/1/16,队列的顺序存储结构,用一组地址连续的存储单元依次存放从队头到队尾的元素。,front rear,队空,front,J1,J2,J3入队,J1,J2,J3,rear,J4,J5,J6入队,J4,J5,J6,front,设两个指针front,rear,约定： rear指示队尾元素； front指示队头元素前一位置 初值front=rear=0,空队列条件：front=rear 入队列：sq+rear=x; 出队列：x=sq+front;,J1,J2,J3出队,J1,J2,J3,存在问题(设数组大小为M)，则： 当front=0,rear=M-1时，再有元素入队发生溢出真溢出。 当front0,rear=M-1时，再有元素入队发生溢出假溢出。,Page 22,2019/1/16,解决方案 队首固定，每次出队剩余元素向下移动浪费时间。 循环队列 基本思想：把队列设想成环形，让sq0接在sqM-1之后;,Page 23,2019/1/16,rear,初始状态,解决方案： 1.另外设一个标志以区别队空、队满 2.少用一个元素空间： 队空：front=rear 队满：(rear+1)%M=front,队空：front=rear,队满：front=rear,Page 24,2019/1/16,2011年考研真题,Page 25,2019/1/16,循环队列的结构定义,#define MAXQSIZE 100 / 最大队列长度 typedef struct QElemType *base;/ 初始化的动态分配存储空间 int rear; / 队尾指针，指向队尾元素 int front; / 队头指针，指向队头元素的前一个位置 SqQueue;,Page 26,2019/1/16,rear,队首元素表示：,出队front变化:,入队rear变化:,Q-baseQ-front,Q-front=(Q-front+1)%maxsize;,Q-rear=(Q-rear+1)%maxsize;,队满条件： 队空条件：,Q-rear+1)%maxsize=Q-front Q-rear=Q-front,Page 27,2019/1/16,循环队列的基本操作的算法描述,Status InitQueue (SqQueue *Q) / 构造一个空队列 Q Q.base = (QElemType *)malloc(MAXQSIZE *sizeof(QElemType); / 为循环队列分配存储空间 if (!Q.base) exit(OVERFLOW); / 存储分配失败 Q.front = Q.rear = 0; return OK; / InitQueue,Page 28,2019/1/16,int QueueLength (SqQueue Q) / 返回队列Q中元素个数，即队列的长度 return (Q.rear-Q.front+MAXQSIZE) % MAXQSIZE); ,Page 29,2019/1/16,Status EnQueue (SqQueue ,Page 30,2019/1/16,Status DeQueue (SqQueue ,Page 31,2019/1/16,用链表表示的队列。 结点定义 typedef struct QNode QelemType data ; struct QNode *next ; QNode, *QueuePtr; typedef struct QueuePtr *front ;/队头指针 QueuePtr *rear ; /队尾指针 LinkQueue;,链队列队列的链式表示和实现,Page 32,2019/1/16,Page 33,2019/1/16,Status InitQueue (LinkQueue ,链队列基本操作的算法描述（部分）,Page 34,2019/1/16,Status EnQueue(LinkQueue / 移动队尾指针 ,Page 35,2019/1/16,Status DeQueue(LinkQueue / DeQueue,Page 36,2019/1/16,本章小结,栈和队列都属线性结构，因此他们的存储结构和线性表非常类似，同时由于他们的基本操作要比线性表简单得多，因此它们在相应的存储结构中实现的算法都比较简单，相信对大家来说都不是难点。 这一章的重点则在于栈和队列的应用。通过本章所举的例子学习分析应用问题的特点，在算法中适时应用栈和队列。,Page 37,2019/1/16,基础知识题,进栈序列为123，则可能得到的出栈序列是什么? 如果进栈序列为123456，则能否得到435612和135426的出栈序列，并请说明为什么不能得到。 简述栈和线性表的差别。 简述队列和栈这两种数据类型的相同点和差异处。,Page 38,2019/1/16,写出下列程序段的输出结果（栈的元素类型 SElemTyp