[算法学习]栈的出栈序列

最新推荐文章于 2022-07-15 22:14:11 发布

KesarChen

最新推荐文章于 2022-07-15 22:14:11 发布

阅读量9.7k

点赞数 1

分类专栏： java 算法随笔算法学习文章标签：算法栈

本文链接：https://blog.csdn.net/KesarChen/article/details/50685577

版权

该博客讨论了如何验证两个整数序列A（压栈序列）和B（出栈序列）是否为同一栈的合法操作序列。通过使用双指针技术和栈的数据结构，比较序列中的元素并进行相应的入栈和出栈操作，来判断这两个序列是否匹配。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

问题描述： 输入数字不重复的两组整数序列：压栈的序列A,出栈的序列B，验证AB是否为同一栈的序列。

解法与分析：
1. 使用两个指针pA，pB分别在两个序列A，B上遍历。
2. 做个这样的判断，首先判断两个指针所指元素是否相等，若相等，则两个指针同时推进；若不相等，取出栈顶元素作比较；若与栈顶元素不相等，则序列A的元素入栈，pA指针向前推进，若与栈顶元素相等，则出栈，pB指针推进。

参考代码如下

public static boolean isStackSeq(int[] pushSeq, int[] popSeq)
{
    if (popSeq == null || pushSeq == null
            || pushSeq.length != popSeq.length)
    {

最低0.47元/天解锁文章