讲解LeetCode第946题：验证栈序列（完整代码）

序属秋秋秋

发布于 2025-12-18 14:56:24

750

LeetCode第946题：验证栈序列

👨‍💻 博主正在持续更新关于LeetCode的习题中。 ❤️ 如果你觉得内容还不错，请多多点赞。 ⭐️ 如果你觉得对你有帮助，请多多收藏。（防止以后找不到了） 👨‍👩‍👧‍👦如果你想阅读更多的LeetCode习题讲解，请多多关注博主。

题目介绍

方法一：栈模拟

完整代码展示

//验证栈的序列——栈模拟
#include<iostream>
#include<vector>
#include<stack>
using namespace std;

class Solution
{
public:
	bool validateStackSequenes(vector<int>& pushed, vector<int>& popped)
	{
		stack<int>stk;

		int n = pushed.size();
		for (int i = 0, j = 0; i < n; i++)
		{
			stk.emplace(pushed[i]);

			while (!stk.empty() && stk.top() == popped[j])
			{
				stk.pop();
				j++;
			}
		}
		return stk.empty();
	}
};

int main()
{
	vector<int>pushed = { 1,2,3,4,5 };
	vector<int>popped = { 4,3,5,1,2 };

	Solution sol;
	bool result = sol.validateStackSequenes(pushed, popped);

	if (result)
	{
		cout << "true" << endl;
	}
	else
	{
		cout << "false" << endl;
	}

	return 0;
}

代码思路阐述

如果 pushed 和 popped 是有效的栈操作序列,则经过所有的入栈和出栈操作之后，每个元素各入栈和出栈一次，栈为空。

根据上述分析，验证栈序列的模拟做法如下：

1.遍历数组 pushed , 将 pushed 的每个元素依次入栈；
2.每次将 pushed 的元素入栈之后，如果栈不为空且栈顶元素与 popped 的当前元素相同，则将栈顶元素出栈，同时遍历数组 popped ，直到栈为空或栈顶元素与 popped 的当前元素不同。

遍历数组 pushed 结束之后，每个元素都按照数组 pushed 的顺序入栈一次。

如果栈为空，则每个元素都按照数组 popped 的顺序出栈，返回 true。
如果栈不为空，则元素不能按照数组 popped 的顺序出栈，返回 false。

class Solution
{
public:
	bool validateStackSequenes(vector<int>& pushed, vector<int>& popped)
	{
		stack<int>stk;

		int n = pushed.size();
		for ()
		{
            //1.遍历数组 pushed ,
            //将 pushed 的每个元素依次入栈；
			while ()
			{
				//2.每次将 pushed 的元素入栈之后，
                //如果栈不为空且栈顶元素与 popped 的当前元素相同，
                //则将栈顶元素出栈，同时遍历数组 popped ，
                //直到栈为空或栈顶元素与 popped 的当前元素不同。
			}
		}
		return stk.empty();
	}
};

核心原理演示

代码片段解释

片段一：

stk.emplace(pushed[i]);

push()：该成员函数是标准栈提供的一个接口，用于将元素添加到栈顶。

当使用 push 添加元素时，它会在栈内部创建一个元素的副本，并将其放置在栈顶

emplace()：该成员函数是C++11引入的一个新特性，它允许在容器内部直接构造元素。

与 push 不同，emplace 会尝试使用给定的参数在容器内部直接调用元素的构造函数，从而避免不必要的复制或移动操作。

综上所述：

对于基本数据类型，push 和 emplace 在功能上是等价的，性能差异也可以忽略不计。
对于复杂对象或类类型，emplace 可以减少复制或移动构造的开销，从而提高性能。

片段二：

while (!stk.empty() && stk.top() == popped[j])

疑问：while的判断条件可以简单的写成(stk.top() == popped[j])吗？

在函数 validateStackSequences 中，条件判断 !st.empty() && st.top() == popped[j] 是必要的，不能简单地替换为 st.top() == popped[j]。 原因解释：

栈可能为空，如果栈为空，调用 stk.top() 会导致未定义行为（通常是运行时错误）。因此，在尝试访问栈顶元素之前，必须确保栈不为空。
并且逻辑顺序条件 !stk.empty() 必须在 stk.top() == popped[j] 之前检查。如果先检查 stk.top() == popped[j] 而栈为空，那么就会先尝试访问栈顶元素，从而引发错误。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-18，如有侵权请联系 cloudcommunity@tencent.com 删除

函数