数据结构（Python Java）（微课版） 课件 第3章 栈和队列

数据结构与算法设计3.1栈栈的定义与基本操作栈的顺序存储结构与实现栈的链式存储结构与实现顺序栈和链栈的比较栈的应用案例栈的定义与基本操作栈的定义栈：限定仅在一端进行插入和删除操作的线性表（a1,…,an-1,an）栈顶（top）：允许插入和删除的一端称为栈顶栈底（bottom）：另一端称为栈底插入位置：1~n+1删除位置：1~n线性表插入位置：n+1删除位置：n栈栈底栈顶栈的定义与基本操作栈的操作插入：入栈、进栈、压栈删除：出栈、弹栈a插入删除bc此时执行出栈操作，哪个元素可以出栈呢？栈的操作特性：后进先出（LastInFirstOut，LIFO）空栈：不含任何数据元素的栈

如何判空栈

initStack()：初始化操作。设置一个空栈isEmpty()：判栈空函数。若为空，则返回true，否则返回false。getTop()：读栈顶元函数。若栈不空，函数值为栈顶元素，否则为空元素NULLpush(x)：进栈操作。将元素x插入栈中，使x成为栈的栈顶元素pop()：出栈函数。若栈不空，函数值为栈顶元素，且从栈中删除当前栈顶元素，否则函数值为空元素NULLclearStack()：栈置空操作。不论栈是否为空栈，置为空栈栈的定义与基本操作栈的基本操作栈的定义与基本操作栈的抽象数据类型定义ADTStackDataModelOperationendADT栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系initStack：栈的初始化clearStack：清空栈内元素push：入栈pop：出栈getTop：取栈顶元素isEmpty：判空利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素a1a2……an顺序栈Sai……0n栈底栈顶top栈的顺序存储结构与实现顺序栈用数组的一端作为栈底设变量top存储栈顶元素所在的下标组织形式与单链表类似，链表的尾部是栈底，链表的头部是栈顶FtopdatanextEDANULL栈顶栈底栈的链式存储结构与实现链栈顺序栈和链栈的比较顺序栈和链栈的基本算法的时间复杂度均为O(1)空间复杂度比较Java中，初始时顺序栈需要确定栈的长度，所以存在存储元素个数的限制和浪费存储空间的问题。链栈没有栈满的问题，只有当内存没有可用存储空间时才会出现栈满，但是每个元素都需要指针域，从而存在结构性开销。把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）十进制数转换成二进制数栈的应用351784210110001余数结果：100011表达式求值栈的应用对算术表达式求值：

1+2*4-9/3遵循先乘除后加减、先左后右及先括号内，后括号外的四则运算法则，其计算顺序应为：1+2*4-9/3└─┘└─┘①②└──┘③└───┘④采用“运算符优先数法”对每种运算符赋于一个优先数，如：运算符：*/+-#优先数：22110其中

#是表达式结束符表达式求值时，设立两个栈运算符栈(OPTR)操作数栈(OPND)分别存放表达式中的运算符和操作数

步骤OPTR栈OPND栈输入字符主要操作──────────────────────────────────────────

1 # 1+2*4-9/3# PUSH(OPND,'1')2 # 1+2*4-9/3#PUSH(OPTR,'+')3 #+ 12*4-9/3# PUSH(OPND,'2')4 #+ 12*4-9/3# PUSH(OPTR,'*')5 #+* 124-9/3# PUSH(OPND,'4')6 #+* 124-9/3# OPERATE('2','*','4')7 #+ 18-9/3# OPERATE('1','+','8')8 # 9-9/3# PUSH(OPTR,'-')9 #- 99/3# PUSH(OPND,'9')10 #- 99/3# PUSH(OPTR,'/')11 #-/ 993# PUSH(OPND,'3')12 #-/ 993# OPERATE('9','/','3')13 #- 93# OPERATE('9','-','3')14 # 6# RETURN(TOP(OPND))表达式求值栈的应用小结3.1栈栈的定义与基本操作栈的顺序存储结构与实现栈的链式存储结构与实现顺序栈和链栈的比较栈的应用案例数据结构与算法设计3.2队列队列的定义与基本操作队列的顺序存储结构与实现队列的链式存储结构与实现循环队列与链队列的比较队列的应用案例队列的定义队列的定义与基本操作只能在表的一端进行插入，在表的另一端进行删除的线性表（a1,a2,…,an-1,an）a1

a2

…

an栈a1

a2

…

an队列队头队尾队尾：允许插入的一端，相应地，位于队尾的元素称为队尾元素队头：允许删除的一端，相应地，位于队头的元素称为队头元素队列的操作队列的定义与基本操作队列的操作特性：先进先出（FirstInFirstOut，FIFO）a插入：入队、进队入队bc例：有三个元素按a、b、c的次序依次入队，且每个元素只允许进一次队，则出队序列是什么？答：出队序列只有一种情况：abc出队删除：出队空队列：不含任何数据元素的队列

任何时候执行出队操作，一定是哪个元素呢？队列的基本操作队列的定义与基本操作initQueue()：初始化。设置一个空队列qisEmpty()：判断队列是否为空。若队列q为空，函数值为true，否则为false

size()：求队列长度。函数值为队列q中当前所含元素的个数getHead()：读队头元素。若队列q不为空，函数值为队头元素，否则为空元素enQueue(x)：入队。将元素x插入队列q的尾部，使x成为新的队尾元素delQueue()：出队。若队列q不为空，函数值为队头元素，且从队列q中删除当前队头元素，否则函数值为空元素顺序队列队列的顺序存储结构与实现队列的顺序存储结构队尾：设变量rear存储队尾元素所在的下标队头：用数组的一端作为队头，从下标0处开始存放01234a1a2a3a4rear例：a1a2a3a4

依次入队顺序队列队列的顺序存储结构与实现例：a1

出队01234a1a2a3a4rear01234a2a3a4rear队头元素出队后，后面的元素都需要前移，时间性能较差如何改进出队操作的时间性能？01234a2a3a4rear设置队头、队尾两个位置变量约定：队头front指向队头元素的前一个位置，队尾rear指向队尾元素fronta1入队、出队时间性能均是O(1)顺序队列队列的顺序存储结构与实现顺序队列队列的顺序存储结构与实现队列的移动有什么特点？01234a2a3a4front整个队列向数组下标较大方向移动单向移动性队列的单向移动性会产生什么问题？a5假溢出：数组空间发生上溢，但数组的低端还有空闲空间rear循环队列队列的顺序存储结构与实现如何解决假溢出呢？01234a3a4rearfront如何使数组下标循环呢？a5a6循环队列：队列采用顺序存储，并且数组是头尾相接的循环结构循环队列队列的顺序存储结构与实现01234a3rearfront如何判断循环队列的队空？队空的判定条件：front==rear循环队列队列的顺序存储结构与实现a6a2a4a5rearfront如何判断循环队列队满？队空的判定条件：front==rear队满的判定条件：front==rearx01234循环队列队列的顺序存储结构与实现如何确定不同的队空、队满的判定条件？队空的判定条件：front==rear队满的判定条件：front==rear数组中有一个空闲单元01234a6a2a4a5rearfront01234a1a2a4a5rearfront(rear+1)%QUEUE_SIZE=front链队列队列的链式存储是单链表，同时带有头指针和尾指针头指针指向队头结点尾指针指向队尾结点队列的链式存储结构头结点^…...head队头队尾tail设队首、队尾指针head和tail,head指向队头，tail指向队尾循环队列与链队列的比较循环队列和链队列基本算法的时间复杂度均为O(1)空间复杂度比较初始时循环队列必须确定一个固定的长度，所以存在存储元素个数的限制和浪费存储空间的问题。链队列没有溢出问题，只有当内存没有可用存储空间时才会出现溢出，但是每个元素都需要指针域，存在结构性开销。队列的应用案例舞伴配对问题在某舞会上，男士和女士进入舞厅时，各自排成一队。舞会开始时，依次从男队和女队的队头各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮。在算法中，假设男士和女士的记录存放在一个数组中，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成后，依次使两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待者，算法输出此队列中等