栈与队列PPT课件

栈与队列,东营市胜利第一中学高天宇,1,-2015年信息学夏令营,栈,2,-2015年信息学夏令营,栈的简介,栈（stack）是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。,A,B,D,C,3,-2015年信息学夏令营,栈的简介,栈的特点就是：后进先出栈在计算机中应用广泛。如计算机调用函数时，函数的信息便被保存在栈中。回想一下，递归过程是否和栈的特性有些类似？,4,-2015年信息学夏令营,栈的实现,如何写一个栈？,5,-2015年信息学夏令营,栈的实现：存储,我们通常用一个数组存储栈中的元素DataTypestack_dataSTACK_SIZE;/通常DataType都是intinttop=0;/栈顶指针，初始时栈为空,6,-2015年信息学夏令营,栈的实现：存储,我们通常用一个数组存储栈中的元素DataTypestack_dataSTACK_SIZE;/通常DataType都是intinttop=0;/栈顶指针，初始时栈为空,7,-2015年信息学夏令营,栈的实现：判断栈为空,当栈顶指针为0时说明空boolisStackEmpty()returntop=0;,8,-2015年信息学夏令营,栈的实现：判断栈为满,当栈顶指针达到栈容量上限时boolisStackFull()returntop=STACK_SIZE1;,9,-2015年信息学夏令营,栈的实现：进栈操作,将新元素压入栈之前，先检查栈里面还有没有空间。boolpush(DataTypex)if(isStackFull()returnfalse;stack_data+top=x;returntrue;/如果进栈成功返回true,10,-2015年信息学夏令营,栈的实现：出栈操作,查询+删除，要先检查栈是不是空的：boolpop(DataType,11,-2015年信息学夏令营,栈的应用,所有满足后进先出原则的问题表达式计算,12,-2015年信息学夏令营,例题：铁轨,某城市有一个火车站，有n节车厢从A方向驶入车站，按进站顺序编号1n。火车站只有一个入口，最外面的列车可以驶向B方向。你的任务是判断，一个输入的出站顺序，是否可能是合法的。（所谓合法指存在一种操作车厢的方法，可以得到该出栈顺序。如54123是不合法的，54321是合法的）,火车站,A方向,B方向,13,-2015年信息学夏令营,例题：铁轨,所谓车站即为一个栈我们用程序模拟这个过程即可。用两个指针i,j分别表示当前第i节车厢已经进站，当前出站序列里面的第j节车厢已经出站。每次如果发现出站序列里面下一个要出站的车厢为当前栈顶的车厢，则让其出站，更新指针j。如果不是，则继续令后面的车厢进站，更新指针i。如果所有车厢已经进站了，但出栈序列没有完成（有车厢滞留了），则所给的出栈序列不是合法的。反之则合法。,14,-2015年信息学夏令营,例题：铁轨,举例：54123举例：54321,15,-2015年信息学夏令营,例题：等价表达式NOIP2005提高组,明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。他需要你写一个程序帮他解决这个问题。输入中的表达式的长度都不超过50个字符，而且保证选项中总有表达式和题干中的表达式是等价的。,16,-2015年信息学夏令营,例题：等价表达式,这个选择题中的每个表达式都满足下面的性质：1表达式只可能包含一个变量a。2表达式中出现的数都是正整数，而且都小于10000。3表达式中可以包括四种运算+（加），-（减），*（乘），（乘幂），以及小括号(，)。小括号的优先级最高，其次是，然后是*，最后是+和-。+和-的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符+，-，*，以及小括号(，)都是英文字符）4幂指数只可能是1到10之间的正整数（包括1和10）。5表达式内部，头部或者尾部都可能有一些多余的空格。,17,-2015年信息学夏令营,例题：等价表达式,关于a的表达式？这么复杂的式子判断是否相等，难道我要合并同类项？NoNoNo机智的方法：给a代入特殊值。不要代入0，1，-1这样的数。最好代质数。只代入一个数还是很有可能出现两个不等的式子算出来结果相等。多代几个数,18,-2015年信息学夏令营,例题：等价表达式,还有一个问题，代数的话，计算结果可能会超过longlong范围。计算的时候记得模一个大质数因为我们取了若干个数代进去，所以即使模了一个数冲突的几率也很小,19,-2015年信息学夏令营,例题：等价表达式,下面进入正题：如何计算表达式的值？我们需要开两个栈：一个用来存储数字，一个用来存储符号。读入数字时，压入数字栈读入符号时：1.如果是运算符，当前栈顶的运算符优先级大于等于新运算符，则将栈顶运算符弹出，并将当前数字栈顶的两个数进行相应运算，弹出旧数，压入新结果。不停循环，直到栈里面没有符号或符号优先级低于当前新运算符。2.如果是(，直接压入栈。3.如果是），则依次将栈里面的符号弹出，并计算。直到遇到一个（。,20,-2015年信息学夏令营,例题：等价表达式,举例子：3+5*23*5+(21*2*34)小技巧：可以在表达式开头和结尾分别加一个括号，避免了边界的特殊处理。,21,-2015年信息学夏令营,例题：用栈来实现非递归的搜索,写一个程序，输出n的全排列,22,-2015年信息学夏令营,例题：用栈来实现非递归的搜索,递归写法：,23,-2015年信息学夏令营,例题：用栈来实现非递归的搜索,非递归写法：,24,-2015年信息学夏令营,队列,25,-2015年信息学夏令营,队列的简介,队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除（查询）操作，而在表的后端进行插入操作。进行插入操作的端称为队尾，进行删除（查询）操作的端称为队头。,4,3,2,1,队尾,队首,26,-2015年信息学夏令营,队列的简介,队列的特点：先进先出（就和我们平时排队一样）队列最常见的应用是在BFS（广度优先搜索）中。,27,-2015年信息学夏令营,队列的实现,如何写一个队列,28,-2015年信息学夏令营,队列的实现：存储,DataTypequeue_dataQUEUE_SIZE;/DataType通常为intintfront=0,tail=0;/队首和队尾指针。队首指针指向第一个元素，队尾指针指向最后一个元素后面的位置。,29,-2015年信息学夏令营,队列的实现：判断队列是否为空,boolisQueueEmpty()returnfront=tail;,30,-2015年信息学夏令营,队列的实现：判断队列是否为满,boolisQueueFull()returntail=QUEUE_SIZE;,31,-2015年信息学夏令营,队列的实现：入队,boolpush(DataTypex)if(isQueueFull()returnfalse;queue_datatail+=x;,32,-2015年信息学夏令营,队列的实现：出队（查询，删除）,查询（无空队列检查）：DataTypeget_front()returnqueue_datafront;删除：boolpop()if(isQueueEmpty()returnfalse;front+;returntrue;,33,-2015年信息学夏令营,循环队列,我们注意到，进行pop（弹出）操作后，队列数组前端有许多空闲下来的存储空间，如果能将其利用则队列存储效率更高。我们可以用循环队列的方式来节省空间。当我们的队首或者队尾指针变成QUEUE_SIZE的时候，将其对QUEUE_SIZE取模变为0。这样就实现了让队列首尾相接，循环起来了。,34,-2015年信息学夏令营,4,3,2,1,8,7,6,5,0,2,1,6,5,3,4,9,35,-2015年信息学夏令营,循环队列,这样判断队满的条件不再是tail=QUEUE_SIZE，而是tail=front。不过这样和判断队空的条件冲突了。我们可以通过牺牲一个存储单元的方式，将判断队满的条件改成tail=front-1。,36,-2015年信息学夏令营,双端队列,即可以在两端进行删除/查询/插入操作的队列，在普通队列的基础上稍加升级即可。,37,-2015年信息学夏令营,例题：拓扑序列,给定一张有向无环图（DAG），来描述某大学之间课程的联系。如果A到B有一条边，说明在学习课程B之前，必须要学习课程A。请找到一条合法的学习课程的序列，满足题目要求。,38,-2015年信息学夏令营,例题：拓扑序列,所谓一张有向无环图（DAG）的拓扑序列，即为一个点的序列，满足对任意一条边(u,v)，u都出现在v的前面。求解拓扑序列的方法叫做拓扑排序。,39,-2015年信息学夏令营,例题：拓扑序列,求法：首先，我们上的第一门课肯定入度为0（不需要先上别的课）。找出图中所有入度为0的点，放入一个队列中。（顺序无所谓）用类似BFS的方法，我们依次从队首取出点来，先输出到最后的答案序列，然后遍历从当前点u发出的所有边(u,v)。对v入度减一。如果某个v的入度减为0了，这个v就变成了可以学习的状态，将其由队尾插入。如果队列空了，答案序列点数不足，则无可行方案。,40,-2015年信息学夏令营,例题：拓扑序列,1,2,7,3,8,5,4,6,1,2,7,3,8,5,4,6,41,-2015年信息学夏令营,单调队列和单调栈,42,-2015年信息学夏令营,何为单调队列和单调栈,单调队列/单调栈，顾名思义，即保证内部元素单调（从大到下或者从小到大）的队列或者栈。我们只要在插入新元素的时候，将队尾/栈顶所有在插入新元素后不满足单调的元素依次弹出，再插入新元素即可。,43,-2015年信息学夏令营,示例,7,1,4,5,1,3,2,44,-2015年信息学夏令营,应用,单调队列和单调栈中的元素满足单调性可以这么理解：所有加入单调队列/单调栈的元素有一个价值和时效性。价值即为元素的值，时效性则为元素加入的时间。元素加入的时间越久远就越有可能失效。我们要查询在当前还没有失效的所有元素里面谁的价值最高。自然，如果一个元素加入的时间早（更有可能失效），其价值还赶不上后加入的元素，它便没有存在的必要。,45,-2015年信息学夏令营,应用,所以，单调栈/单调队列的本质是，其内部的元素，由队首到队尾/由栈底到栈顶，价值越来越小，但时效性越来越强（越来越不容易失效）。因为每个元素只可能入栈/队列一次，出栈/队列一次，所以整体的时间复杂度是O(n)的（n为元素个数）。通常用在DP的优化中。,46,-2015年信息学夏令营,例题：接待员来源：自己瞎编的,每天餐厅都会新招聘一个接待员，第i天招聘的接待员颜值为Facei。每天餐厅需选用一个接待员，要求该接待员必须是M天以内招聘的才可以。一共n(n=106)天，问每天选用的接待员的颜值最大总和是多少。,47,-2015年信息学夏令营,例题：接待员,暴力做法：对于每一天，枚举其前面的M天，谁颜值最高让谁上。聪明做法：维护一个单调队列，按颜值高低排序。每次从队首取，注意如果队首元素已经过期（距离当天超过M天），则弹出。直到队首元素在有效范围内。,队尾,队首,我比较丑，但我比较新鲜,我最帅，先选我，但我最有可能过期,48,-2015年信息学夏令营,例题：LittleBirdBZOJ3831POI2014,有一排n棵树，第i棵树的高度是Di。A要从第一棵树到第n棵树去找他的妹子玩。如果A在第i棵树，那么他可以跳到第i+1,i+2,.,i+k棵树。如果A跳到一棵不矮于当前树的树，那么他的劳累值会+1，否则不会。为了有体力和妹子玩，A要最小化劳累值。数据范围n=106,49,-2015年信息学夏令营,例题：LittleBird,50,-2015年信息学夏令营,例题：LittleBird,注意，如果对于两个位置j1和j2，有fj1fj2，则j1一定比j2更优。因为就算j1高度比较矮，到达i顶多再多消耗1个疲劳值，顶多和j2相等。如果不需要消耗疲劳值，比j2更优。如果fj1=fj2，则我们比较它们的高度D，高度高的更优。,51,-2015年信息学夏令营,例题：瑰丽华尔兹BZOJ1499NOI2005,题目大意：在一艘船上有一个N*M的大厅，大厅里面有一架钢琴，有一些障碍物，有一些空地。钢琴不能撞上障碍物。输入K段时间区间（保证输入时连续的），每段时间区间上钢琴都会往上下左右四个方向之一位移。每单位时间内位移一格。小精灵为了让钢琴运动轨迹尽量长（在撞上某个障碍物之前），可以施法使某一秒钢琴不移动。问钢琴轨迹最长是多少？1N,M200，K200，T40000（T为总时间）,52,-2015年信息学夏令营,例题：瑰丽华尔兹,样例输入45413.xx.x.134451673样例输出：6（方向中1234分别对应上下左右）,53,-2015年信息学夏令营,例题：瑰丽华尔兹,简单DP：ftij表示时间t到达(i,j)走过最长轨迹。ftij=max(ft-1ij+1,ft-1ij)其中i,j是根据船的移动计算出来的上一时刻的坐标时间复杂度O(NMT),54,-2015年信息学夏令营,例题：瑰丽华尔兹,用fkij表示第k段时间区间过去后，到(i,j)位置的最长路径。我们现在只考虑从左侧转移到右侧的情况（船向右位移的情况）。假如说当前时间区间长度为A，则每个点都可以更新其往右A个点的f值（即钢琴可以移动A个单位）对于每一段时间，我们以fk-1ij+m-j+1作为关键字，维护单调队列想一想，为什么不是以fk-1ij为关键字,55,-2015年信息学夏令营,黑科技时间：读入优化,我们平时所使用的scanf，cin速度都较慢，当读入的数