链栈的出栈序列C++代码

链栈的出栈序列的判断可以利用一个辅助栈来模拟整个出栈的过程，下面是一个基于链栈实现的C++代码示例：

#include <iostream>
using namespace std;

// 链栈结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class LinkedStack {
public:
    LinkedStack() {
        head = new ListNode(-1);
    }

    // 入栈
    void push(int x) {
        ListNode *node = new ListNode(x);
        node->next = head->next;
        head->next = node;
    }

    // 出栈
    int pop() {
        if (isEmpty()) {
            return -1;
        }
        ListNode *node = head->next;
        int val = node->val;
        head->next = node->next;
        delete node;
        return val;
    }

    // 判断栈是否为空
    bool isEmpty() {
        return head->next == NULL;
    }

    // 获取栈顶元素
    int top() {
        if (isEmpty()) {
            return -1;
        }
        return head->next->val;
    }

private:
    ListNode *head;
};

// 判断出栈序列是否合法
bool isValidPopOrder(int *pushOrder, int *popOrder, int n) {
    if (pushOrder == NULL || popOrder == NULL || n <= 0) {
        return false;
    }

    LinkedStack stack;
    int pushIndex = 0, popIndex = 0;

    while (popIndex < n) {
        while (stack.isEmpty() || stack.top() != popOrder[popIndex]) {
            if (pushIndex >= n) {
                return false;
            }
            stack.push(pushOrder[pushIndex++]);
        }
        stack.pop();
        popIndex++;
    }
    return true;
}

int main() {
    int pushOrder[] = {1, 2, 3, 4, 5};
    int popOrder[] = {4, 5, 3, 2, 1};

    if (isValidPopOrder(pushOrder, popOrder, 5)) {
        cout << "The pop order is valid" << endl;
    } else {
        cout << "The pop order is invalid" << endl;
    }
    return 0;
}

这里我们利用辅助栈模拟整个出栈的过程，具体实现见 `isValidPopOrder` 函数。