前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >出栈顺序问题的一般解决方法

出栈顺序问题的一般解决方法

作者头像
KevinBruce
发布2020-03-12 16:04:06
7260
发布2020-03-12 16:04:06
举报
文章被收录于专栏:CTF及算法学习

方案

  1. 设有一个栈为s
  2. 设有一队列q,q存储了要求的s中元素出栈的顺序
  3. 设有一队列q_push,其中存储了元素的入栈顺序
  4. 判断栈顶元素是否可以出栈,若为空,或者不为空但是栈顶元素不是q中当前数据,则不可以出栈.否则可以出栈
  5. 若栈顶元素可以出栈,则将其进行出栈,并将q队首元素出队
  6. 若栈顶元素不可以出栈,则在队列q_push中元素不为空且不等于q的队首元素的情况下,将q_push持续出队,并将弹出的队首元素都入栈到s中。
  7. 当循环结束时,q_push只有空与非空两种可能。空说明没找到这样一个符合要求的元素,即出栈队列q非法,程序结束。若非空,说明找到了这样一个元素,回到步骤4
  8. 当循环结束时,判断q是否为空,若非空,说明出栈顺序不符合要求,否则,是符合要求的。

实例

题目来源:oj.hbu.cn

代码语言:javascript
复制
题目描述

已知自然数1,2,...,N(1<=N<=100)依次入栈,请问序列C1,C2,...,CN是否为合法的出栈序列
输入

输入包含多组测试数据。
每组测试数据的第一行为整数N(1<=N<=100),当N=0时,输入结束。
第二行为N个正整数,以空格隔开,为出栈序列。
输出

对于每组输入,输出结果为一行字符串。
如给出的序列是合法的出栈序列,则输出Yes,否则输出No。

样例输入
5
3 4 2 1 5
5
3 5 1 4 2
0
样例输出
Yes
No

代码

代码语言:javascript
复制
/*
这里没有很严格的使用前面提到的数据结构,而是根据题目特性进行了一些变形
这样写可读性受到了一点影响,但是还是可以类比到对应的数据结构上,而且代码更简洁一些
*/
#include<stdio.h>
typedef struct
{
    int data[101];
    int top;
}stack;

int main(void)
{
    int n,a[101],j;
    stack s1,s2;
    //s1是相当于方案中的队列q_push,这里用了栈进行表示,没有严格的使用队列
    //s2是方案中提到的栈
    while(scanf("%d",&n) && n!=0)
    {
        s1.top = s2.top = -1;
        for(int i = 0;i < n;i++)
            scanf("%d",&a[i]);
        for(int i = n;i > 0;i--)
            s1.data[++s1.top] = i;
        //前面都是初始化操作,算法从这里开始
        for(j = 0;j < n;) //这里的j相当于队列q
        {
            //栈顶元素不符合要求
            if(s2.top==-1 || (s2.top!=-1 && s2.data[s2.top]!=a[j]))
            {
                //出队入栈
                while(s1.top!=-1 && s1.data[s1.top]!=a[j])
                    s2.data[++s2.top] = s1.data[s1.top--];
                //判断q_push是否为空,若空则程序结束
                if(s1.top!=-1)
                    s2.data[++s2.top] = s1.data[s1.top--];
                else
                    break;
            }
            //栈顶元素符合要求
            else {
                s2.top--;
                j++;    
            }
        }
        if(j!=n)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-11-17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 方案
  • 实例
  • 代码
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档