当前位置：首页 > news >正文

算法的学习笔记—栈的压入、弹出序列(牛客JZ31)

news 来源：原创 2024/9/21 5:27:54

😀前言
栈（Stack）是一种常见的数据结构，具有“后进先出”的特性。在实际应用中，我们常常需要验证一组操作是否符合栈的特性。本文将探讨如何通过编程判断一个给定的弹出序列是否可以由另一个给定的压入序列生成，并提供一个高效的解决方案。

🏠个人主页：尘觉主页

文章目录

😀栈的压入、弹出序列
- 🥰题目链接
- 😊问题描述
- - ❤️‍🔥解决思路
  - 🤔代码实现
  - 💞示例分析
- 😄总结

😀栈的压入、弹出序列

🥰题目链接

牛客网

😊问题描述

给定两个整数序列 pushSequence 和 popSequence，其中 pushSequence 表示一个栈的压入顺序，popSequence 表示一个弹出顺序。我们需要判断 popSequence 是否可能是 pushSequence 的一个合法弹出序列。

示例分析：

输入：pushSequence = [1,2,3,4,5]，popSequence = [4,5,3,2,1]
输出：true

说明：可以通过如下操作序列得到 popSequence：

push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true

输入：pushSequence = [1,2,3,4,5]，popSequence = [4,3,5,1,2]
输出：false

说明：由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false

❤️‍🔥解决思路

要判断 popSequence 是否是 pushSequence 的合法弹出序列，我们可以利用栈的特性进行模拟。具体步骤如下：

使用辅助栈：我们利用一个辅助栈 stack 来模拟栈的压入和弹出操作。
逐步压入和匹配：
- 遍历 pushSequence，将元素逐个压入 stack 中。
- 每次压入元素后，检查 stack 的栈顶元素是否与 popSequence 的当前元素相同。如果相同，则执行弹出操作，并将 popSequence 指针向后移动。
- 继续此过程，直到 pushSequence 遍历完毕。
结果判定：
- 如果最终 stack 为空，说明 popSequence 是 pushSequence 的合法弹出序列，返回 true。
- 否则，返回 false。

🤔代码实现

以下是上述思路的 Java 代码实现：

import java.util.Stack;public class StackOrder {public boolean IsPopOrder(int[] pushSequence, int[] popSequence) {int n = pushSequence.length;Stack<Integer> stack = new Stack<>();// pushIndex 用于遍历 pushSequence// popIndex 用于遍历 popSequencefor (int pushIndex = 0, popIndex = 0; pushIndex < n; pushIndex++) {// 将元素压入栈中stack.push(pushSequence[pushIndex]);// 如果栈顶元素等于当前弹出序列的元素，则执行出栈操作while (popIndex < n && !stack.isEmpty() && stack.peek() == popSequence[popIndex]) {stack.pop();popIndex++;}}// 如果栈为空，说明弹出序列合法return stack.isEmpty();}
}