剑指Offer:面试题22——栈的压入,弹出序列(java实现)
2024-10-19 00:24:01
题目描述:
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。
思路:
遍历待测试序列,如果当前元素在栈顶,出栈即可,否则,查看是否所有待入栈元素已入栈,如是说明当前元素在栈里面但又不在栈顶,显然出栈顺序错误,若没入栈,则按顺序从待入栈集合中入栈直到栈顶元素是当前元素,出栈…
代码:
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA == null || popA == null){
return false;
}
int m = pushA.length;
int n = popA.length;
if(m == 0 || n == 0){
return false;
}
Stack<Integer> s = new Stack<Integer>();
int start = 0;
for(int i = 0; i < n; i++){
while(s.empty() || s.peek() != popA[i]){
if(start >= m){
return false;
}
s.push(pushA[start++]);
}
if(s.peek() != popA[i]){
return false;
}
s.pop();
}
return true;
}
最新文章
- C#中Validating和Validated事件
- halcon中variation_model_single实例注释.
- BZOJ3488 : [ONTAK2010]Highways
- 2014ACMICPC亚洲区域赛牡丹江现场赛之旅
- PHP引用操作以及外部操作函数的局部静态变量的方法
- html5权威指南:用元数据元素说明文档
- Oracle 一些基本命令
- Effective Java 第三版——32.合理地结合泛型和可变参数
- T-SQL动态查询(3)——静态SQL
- ABP实践(1)-通过官方模板创建ASP.NET Core 2.x版本+vue.js单页面模板-启动运行项目
- PowerShell Empire使用笔记
- Qt代码吐槽
- centos设置路由route
- python读取es中的所有数据并计算md5然后进行持久化
- 从HTTP/0.9到HTTP/2:一文读懂HTTP协议的历史演变和设计思路
- ext Ext.grid.去除右边空白
- Linux 文件夹相关常用命令
- Android 判定手机是否root
- Visual Studio 2013 Update2
- poj 1236 Network of Schools 【Tarjan】