应用递归实现栈的逆序输出362

栈是一种先进后出(LIFO)的数据结构，元素通过栈顶进行压入和弹出。栈的逆序输出是指从栈底到栈顶依次输出栈中元素。

使用递归技术可以优雅地实现栈的逆序输出。递归是一种函数调用自身的过程，它可以将复杂问题分解为更简单的子问题，从而更容易求解。

以下是用 C 语言实现栈的逆序输出的递归函数：```c
#include
// 栈结构
typedef struct Stack {
int *arr;
int top;
int size;
} Stack;
// 栈初始化
void initStack(Stack *s, int size) {
s->arr = (int *) malloc(sizeof(int) * size);
s->top = -1;
s->size = size;
}
// 栈压入元素
void push(Stack *s, int data) {
if (s->top == s->size - 1) {
printf("栈已满");
} else {
s->arr[++s->top] = data;
}
}
// 栈弹出元素
int pop(Stack *s) {
if (s->top == -1) {
printf("栈已空");
return -1;
} else {
return s->arr[s->top--];
}
}
// 递归逆序输出栈
void reversePrintStack(Stack *s) {
if (s->top != -1) {
int data = pop(s);
reversePrintStack(s);
printf("%d ", data);
}
}
// 主函数
int main() {
Stack s;
initStack(&s, 5);
push(&s, 1);
push(&s, 2);
push(&s, 3);
push(&s, 4);
push(&s, 5);
reversePrintStack(&s);
printf("");
return 0;
}
```

该代码首先初始化一个栈并压入 5 个元素。然后调用 `reversePrintStack()` 函数，它使用递归逆序弹出并输出栈中元素。输出结果为 `5 4 3 2 1`，实现了栈的逆序输出。

递归的过程：

1. 递归调用 `reversePrintStack()` 函数，弹出栈顶元素 `data`。

2. 再次递归调用 `reversePrintStack()` 函数，继续弹出剩余元素。

3. 当栈为空时(即 `s->top == -1`)，递归终止。

4. 回溯过程中，将弹出的元素 `data` 输出。

通过递归，栈的逆序输出问题被分解为更简单的子问题：依次弹出栈中元素并输出。递归函数以栈为空为基线情况，确保了输出的正确性。

2024-11-21

上一篇：C 语言解题程序输出方法详解

下一篇：利用 C 语言计算和输出 cos 值