C语言实现出栈序列

C语言实现出栈序列的完整攻略

什么是出栈序列？

在栈（Stack）的操作中，如果我们要把栈中的元素全部取出来，那么根据栈的“先进后出”原则，最上面的元素最后一个被取出，最后面进入栈中的元素最先被取出。

把栈中的元素全部取出来，并且按照原来的顺序排列，得到的序列就是一个出栈序列（Pop Sequence）。

如何判断一个出栈序列是否合法？

给定一个原始序列和一个目标序列，如何判断目标序列是否是原始序列的出栈序列呢？

我们可以模拟栈的入栈和出栈操作过程，遍历目标序列中的每一个元素：

1. 如果栈顶元素和当前元素相等，说明当前元素是从栈顶弹出的，因此不需要做入栈操作，直接弹出栈顶元素。
2. 如果栈为空或者栈顶元素和当前元素不相等，说明此时需要将当前元素入栈，继续遍历目标序列。
3. 如果目标序列中的元素全部遍历完后，栈中还有剩余元素，说明目标序列不是原始序列的出栈序列，否则目标序列是原始序列的出栈序列。

核心算法的C语言实现

下面是使用C语言实现出栈序列判断的核心算法：

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];  // 模拟栈中的数据
    int top;             // 栈顶指针
} Stack;

// 初始化栈
void init(Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
int is_empty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
int is_full(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈操作
void push(Stack *s, int value) {
    if (is_full(s)) {
        printf("Error: stack overflow\n");
        exit(1);
    }
    s->data[++(s->top)] = value;
}

// 出栈操作
int pop(Stack *s) {
    if (is_empty(s)) {
        printf("Error: stack underflow\n");
        exit(1);
    }
    return s->data[(s->top)--];
}

// 判断目标序列是否是原始序列的出栈序列
int is_pop_seq(int *origin_seq, int *pop_seq, int n) {
    Stack s;
    init(&s);
    int i = 0, j = 0;
    while (j < n) {
        if (!is_empty(&s) && s.data[s.top] == pop_seq[j]) {
            // 如果栈顶元素和当前元素相等，说明当前元素是从栈顶弹出的，
            // 因此不需要做入栈操作，直接弹出栈顶元素。
            pop(&s);
            j++;
        } else {
            // 如果栈为空或者栈顶元素和当前元素不相等，说明此时需要将当前元素入栈。
            if (i >= n) {
                // 目标序列中的元素全部遍历完后，栈中还有剩余元素，
                // 说明目标序列不是原始序列的出栈序列。
                return 0;
            }
            push(&s, origin_seq[i]);
            i++;
        }
    }
    return 1;
}

两个示例说明

接下来，我们用两个示例说明如何使用上面的算法判断目标序列是否是原始序列的出栈序列。

示例一

假设原始序列为 {1, 2, 3, 4, 5}，目标序列为 {3, 5, 4, 2, 1}，则使用 is_pop_seq() 函数进行判断：

int origin_seq[] = {1, 2, 3, 4, 5};
int pop_seq[] = {3, 5, 4, 2, 1};
int n = sizeof(origin_seq) / sizeof(origin_seq[0]);
if (is_pop_seq(origin_seq, pop_seq, n)) {
    printf("The target sequence is a valid pop sequence.\n");
} else {
    printf("The target sequence is not a valid pop sequence.\n");
}

输出结果为：

The target sequence is a valid pop sequence.

说明目标序列 {3, 5, 4, 2, 1} 是原始序列 {1, 2, 3, 4, 5} 的出栈序列。

示例二

假设原始序列为 {1, 2, 3, 4, 5}，目标序列为 {3, 5, 4, 1, 2}，则使用 is_pop_seq() 函数进行判断：

int origin_seq[] = {1, 2, 3, 4, 5};
int pop_seq[] = {3, 5, 4, 1, 2};
int n = sizeof(origin_seq) / sizeof(origin_seq[0]);
if (is_pop_seq(origin_seq, pop_seq, n)) {
    printf("The target sequence is a valid pop sequence.\n");
} else {
    printf("The target sequence is not a valid pop sequence.\n");
}

输出结果为：

The target sequence is not a valid pop sequence.

说明目标序列 {3, 5, 4, 1, 2} 不是原始序列 {1, 2, 3, 4, 5} 的出栈序列。