判断出栈序列是否合法

在栈数据结构中，元素的添加（入栈）遵循后进先出（LIFO, Last In First Out）原则，这意味着最后一个进入栈的元素最先被弹出。因此，判断出栈序列是否合法，我们需要检查按照这个顺序操作栈是否能得到给定的序列。

一个简单的算法可以通过迭代或递归来实现：

1. 创建一个空栈 `stack` 和一个辅助数组 `output` 来存储实际的出栈过程。
2. 遍历给定的出栈序列 `sequence`，对于每个元素 `seq[i]`：
a. 如果 `stack` 不为空且顶部元素等于 `seq[i]`，则从栈中移除该元素并将其实例添加到 `output` 中。
b. 否则，如果栈为空或者顶部元素不等于 `seq[i]`，那么序列就不合法。
3. 最终，如果遍历结束后 `stack` 为空，表示所有元素都被正确地弹出了，所以序列合法；否则，序列不合法。

以下是这个算法的C语言代码示例：

#include <stdbool.h>
#include <stdio.h>

bool isValidSequence(int sequence[], int n) {
    stack<int> stack;
    for (int i = 0; i < n; i++) {
        if (!stack.empty() && sequence[i] == stack.top()) {
            stack.pop();
        } else {
            return false;
        }
    }
    return stack.empty();
}

// 示例用法
int main() {
    int sequence[] = {1, 2, 3, 2, 1};
    int n = sizeof(sequence) / sizeof(sequence[0]);
    bool is_valid = isValidSequence(sequence, n);
    printf("The sequence %s valid.\n", is_valid ? "is" : "is not");
    return 0;
}