华为OD机试E卷 - 空栈压数（Java & Python& JS & C++ & C ）

空栈压数问题

在编程中，空栈压数是一种常见的算法问题，尤其在数据结构与算法的学习中尤为重要。简单来说，空栈压数指的是利用栈结构的特性，将一些数字进行入栈和出栈操作，达到特定的目标，常常涉及到如何合理地使用栈来存储和管理数据。

栈的基本操作

栈是一种后进先出（LIFO, Last In First Out）的数据结构，它支持两个主要操作：

1. 入栈（Push）：将一个元素添加到栈顶。
2. 出栈（Pop）：移除并返回栈顶元素。

此外，栈还可以提供一些辅助操作，比如检查栈是否为空（isEmpty）和查看栈顶元素但不移除（peek）。

问题描述

在空栈压数问题中，题目通常要求从一个序列中完成特定的数值压入栈的操作，并在此过程中检查是否满足某个条件，比如能否用栈的操作构造出另一个给定序列。

例如，给定一个数列 1, 2, 3，需要判断是否可以通过入栈和出栈操作，得到一个目标序列 3, 2, 1。

示例代码

以下是用Python解决这一问题的代码示例：

def validate_stack_sequences(pushed, popped):
    stack = []
    j = 0

    for x in pushed:
        stack.append(x)  # 入栈
        while stack and stack[-1] == popped[j]:  # 检查栈顶元素是否和目标序列的下一个值相等
            stack.pop()  # 出栈
            j += 1  # 移动目标序列的指针

    return j == len(popped)  # 全部目标序列出栈后指针是否到达尾部

# 示例
pushed = [1, 2, 3, 4, 5]
popped = [4, 5, 3, 2, 1]
print(validate_stack_sequences(pushed, popped))  # 输出：True

在这个例子中，我们用一个栈来模拟入栈和出栈的过程。通过循环遍历 pushed 数组，当栈顶元素与 popped 数组当前指向的元素相同时，我们不断出栈并移动 popped 的指针，最后判断 popped 是否被完全遍历。

C++ 示例代码

这个问题在不同语言中也可以用类似的逻辑进行实现，例如在 C++ 中：

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    stack<int> stack;
    int j = 0;

    for (int x : pushed) {
        stack.push(x);  // 入栈
        while (!stack.empty() && stack.top() == popped[j]) {
            stack.pop();  // 出栈
            j++;  // 移动目标序列的指针
        }
    }

    return j == popped.size();  // 全部目标序列出栈后指针是否到达尾部
}

int main() {
    vector<int> pushed = {1, 2, 3, 4, 5};
    vector<int> popped = {4, 5, 3, 2, 1};
    cout << (validateStackSequences(pushed, popped) ? "True" : "False") << endl;  // 输出：True
    return 0;
}

总结

空栈压数问题不仅帮助我们理解栈的基本操作，也锻炼了我们处理数据流的能力。通过对栈的入栈和出栈过程的模拟，我们可以有效判断是否能够转换成目标序列。这类问题在实际开发中能提高我们对数据结构使用的掌握，也为后续更复杂的算法打下基础。理解栈的操作及其应用是每位开发者必须掌握的重要技能。