合法的出栈序列

poj 1363 Rails 已知从1至n的数字序列,按顺序入栈,每个数字入栈后即可出栈,也可在栈中 停留,等待后面的数字入栈出栈后,该数字再出栈,求该数字序列的某出栈 序列是否合法?

算法设计:使用栈与队列模拟入栈、出栈过程

同时使用一个队列与一个栈来解决该问题,设队列order与栈为S。队列order存储待判断是否合法 的出栈序列,使用栈S用来模拟出栈与入栈的过程。 1.按照1-n的顺序,将元素push进入栈S中: 2.每push一个元素,即检查栈顶S.top()是否与队列头部元素order.front()相同。 3.如果相同则同时弹出栈顶元素与队列头部元素,直到栈空或栈顶与队列头部元素不同。 若最终栈为空,则说明序列合法,否则不合法。

EG.1
#include<stack>
#include<queue>
bool check_is_valid_order(std::queue<int> &order){
    std::stack<int> s;//s为模拟栈
    int n = order.size();//n为序列长度,将1-n按顺序入栈
    for(int i = 1; 1<= n;i++){
        s.push(i);//将i入栈
        while(!s.empty()&&order.front() == s.top()){
            s.pop();
            order.pop();
        }
    }
if(!s.empty()){
    return false;//如果最终栈不空,则说明序列不合法!
}
return true;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏androidBlog

笔试题—字符串常见的算法题集锦

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

1411
来自专栏智能算法

程序员必须了解的数据结构:Array、HashMap 与 List

当开发程序时,我们(通常)需要在内存中存储数据。根据操作数据方式的不同,可能会选择不同的数据结构。有很多常用的数据结构,如:Array、Map、Set、List...

1250
来自专栏java 成神之路

java.lang.Void 解析与使用

2865
来自专栏个人分享

Scala第一章学习笔记

  面向对象编程是一种自顶向下的程序设计方法。用面向对象方法构造软件时,我们将代码以名词(对象)做切割,每个对象有某种形式的表示服(self/this)、行为(...

1062
来自专栏LanceToBigData

Java集合源码分析(二)Linkedlist

前言   前面一篇我们分析了ArrayList的源码,这一篇分享的是LinkedList。我们都知道它的底层是由链表实现的,所以我们要明白什么是链表? 一、Li...

2757
来自专栏从流域到海域

《数据结构》 定长顺序串常用操作代码集合

代码来自老师上课使用的ppt或者课本 /*定长顺序串*/ #define MAXLEN 40 typedef struct { char ch[M...

1966
来自专栏大神带我来搬砖

程序员的职业素养真是完全靠不住的东西

这里面<T extends Comparable<? super T>>有什么用?

491
来自专栏XAI

程序员必知的8大排序(java实现)

8种排序之间的关系: ?  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要...

20110
来自专栏追不上乌龟的兔子

Python中最快的格式化字符串方式

第一种是传承自C语言printf函数的使用%占位符格式化字符串,如'%d' % 100,这种方式严格来说是使用%作为算数运算符进行的二元运算,而且有一个限制是只...

1084
来自专栏程序你好

如何比较一个List对象Java 7 vs Java 8

1122

扫码关注云+社区

领取腾讯云代金券