栈及其应用解决方案.pptVIP

PROC Dfs(startX, startY : integer); 初始化栈 Current_x?startX Current_y?startY top?1; s[top]?0; {初始结点入栈} 标记(Current_x, Current_y)为已扩展结点 while top0 do 【 s[top]?st[top]+1 if （s[top]=8）and（按s[top]方向扩展的结点属于海洋区域） and（之前没有扩展过）then 【 Current_x?Current_x+d[s[top], 1] Current_y?Current_y+d[s[top], 2] 标记(Current_x, Current_y)为已扩展结点 top?top+1; s[top]?0 {新结点入栈} 】 else 【 top?top-1 {当前结点退栈} if top0 then 【 Current_x?Current_x – d[s[top], 1] Current_y?Current_y – d[s[top], 2] 】 】 】ENDP 栈的应用5：双栈排序 有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2).最初的时候,q2,s1和s2都为空,而q1中有n个数(n=1000),为1~n的某个排列.现在支持如下四种操作: a操作,将 q1的首元素提取出并加入s1的栈顶. b操作,将s1的栈顶元素弹出并加入q2的队列尾. c操作,将 q1的首元素提取出并加入s2的栈顶. d操作,将s2的栈顶元素弹出并加入q2的队列尾. 请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,…,n.如果可以,求出字典序最小的一个操作序列. 一个简单问题：火车调度 例1：1,2,3,4,5 例2：5,4,3,2,1 例3：3,2,4,5,1 例4：3,1,4,5,2 no; yes; yes; yes; 分析 思考：给定一个入栈顺序，什么样的出栈顺序不合法？ 定理: 考虑对于任意两个数q[i]和q [j]来说,它们不能压入同一个栈中的充要条件p是:存在一个k,使得ijk且q [k]q [i]q [j]. 证明（1） 充分性： 即如果满足条件p,那么这两个数一定不能压入同一个栈.这个结论很显然,使用反证法可证.假设这两个数压入了同一个栈,那么在压入q [k]的时候栈内情况如下:…q [i]…q [j]…因为q [k]比q [i]和q [j]都小,所以很显然,当q [k]没有被弹出的时候,另外两个数也都不能被弹出(否则q中的数字顺序就不是1,2,3,…,n了).而之后,无论其它的数字在什么时候被弹出,q[j]总是会在q[i]之前弹出.而q[j]q[i],这显然是不正确的. 证明（2） 必要性： 也就是,如果两个数不可以压入同一个栈,那么它们一定满足条件p.这里我们来证明它的逆否命题,也就是“如果不满足条件p,那么这两个数一定可以压入同一个栈.”不满足条件p有两种情况:一种是对于任意ijk且q [i]q [j],q [k]q [i];另一种是对于任意ij,q [i]q[j].第一种情况下,很显然,在q [k]被压入栈的时候,q1[i]已经被弹出栈.那么,q[k]不会对q [j]产生任何影响(这里可能有点乱,因为看起来,当q[j]q[K]的时候,是会有影响的,但实际上,这还需要另一个数R,满足jkr且 q [r]q [j]q [k],也就是证明充分性的时候所说的情况…而事实上我们现在并不考虑这个r,所以说q [k]对q [j]没有影响).第二种情况下,我们可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈.这样,原命题的逆否命题得证,所以原命题得证. 此时,条件p为q [i]和q [j]不能压入同一个栈的充要条件也得证. 解决 这样,我们对所有的数对(i,j)满足1=ij=n,检查是否存在ijk满足q[k] q[i]q[j].如果存在,那么在点I和点j之间连一条无向边,表示q[i]和q[j]不能压入同一个栈.此时想到了什么?那就是二分图~二分图的两部分看作两个栈,因为二分图的同一部分内不会出现任何连边,也就相当于不能压入同一个栈的所有结点都分到了两个栈中.此时我们