C语言实现栈出栈序列判断算法

本文将介绍一个算法来判断通过一个栈能否得到由 a[0..n-1]（比如为：2,1,3,4，…n）指定出栈序列。同时，我们将设计一个测试主函数进行测试，并用 C语言实现整个算法。

算法思路

初始化一个辅助栈，将第一个元素入栈；
从 1 到 n-1 遍历出栈序列，对于每个元素 x，进行如下操作： a. 如果辅助栈的栈顶元素等于 x，则直接弹出栈顶元素； b. 如果辅助栈的栈顶元素不等于 x，且 a 数组还有元素可以入辅助栈，则将 a 中下一个元素入辅助栈； c. 如果辅助栈的栈顶元素不等于 x，且 a 数组已经没有元素可以入辅助栈，则返回 false；
如果出栈序列遍历完毕，且辅助栈已经为空，则返回 true，否则返回 false。

C语言实现

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

bool is_pop_order(int *a, int *b, int n)
{
    if (a == NULL || b == NULL || n <= 0)
        return false;
    int i = 0, j = 0;
    int *stack = (int *) malloc(sizeof(int) * n);
    while (j < n) {
        if (i < n && a[i] == b[j]) {
            i++;
            j++;
        } else if (stack > 0 && stack[stack-1] == b[j]) {
            stack--;
            j++;
        } else if (i < n) {
            *stack++ = a[i++];
        } else {
            return false;
        }
    }
    return true;
}

int main()
{
    int a[] = {2, 1, 3, 4};
    int b[] = {1, 2, 4, 3};
    int n = sizeof(a) / sizeof(int);
    if (is_pop_order(a, b, n))
        printf('b is a pop order of a\n');
    else
        printf('b is not a pop order of a\n');
    return 0;
}

总结

本文介绍了判断一个栈是否能得到指定出栈序列的算法思路和 C语言实现代码。算法使用辅助栈，通过模拟入栈和出栈操作来判断出栈序列的合法性。代码包含测试主函数，方便读者进行验证。希望本文对大家理解栈出栈序列判断算法有所帮助。