首页 > 代码库 > Tarjan中栈的分析与SLT栈的实现
Tarjan中栈的分析与SLT栈的实现
首先看一下手写的栈:
1 do{2 printf("%d ",stack[index]);3 visit[stack[index]]=0;4 index--;5 }while(x!=stack[index+1]);//出栈,并且输出。6 printf("\n");
我们可以发现。x是与index的上一个元素比较的
举个例子
栈:1 3 2 4 5 x=2
这样的话会输出 5 4 2
但是stl不支持和栈顶的上一个元素比较,因为上一个元素一定是被pop掉的。
那么我们可以怎么实现呢?
1.首先我们需要明白一点,如果我们把循环的条件改为
1 x!=stack.top;
那么当栈已经空的时候,还是会执行一下判断操作,这样就会导致re,
所以我们可以记录下pop之前的元素,这样就可以保证在判断的时候不会越界,而且是与pop之前的元素进行比较的
code:
1 int h;2 do3 {4 h=s.top();5 if(!color[s.top()])6 color[s.top()]=colornum;7 vis[s.top()]=0;8 s.pop();9 }while(now!=h);
2.一般的do while语句都可以用while语句来实现
我们如果单纯的把do while改成while,
那么在上面的例子中会输出 5 4
所以我们还需要判断一次,把当前的栈顶给输出
代码:
1 while(now!=s.top()) 2 { 3 if(!color[s.top()]) 4 color[s.top()]=colornum; 5 vis[s.top()]=0; 6 s.pop(); 7 } 8 if(!color[s.top()]) 9 color[s.top()]=colornum;10 vis[s.top()]=0;11 s.pop();
如果你还有其他什么写法的话欢迎发表评论或者通过其他方式联系我。
谢谢
Tarjan中栈的分析与SLT栈的实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。