c语言实现原地倒置栈

在 C 语言中，实现一个原地倒置栈（也称为逆序栈或者反向栈）意味着我们需要只使用栈本身的操作来达到栈元素的反转效果，而不需要额外的数据结构。这通常通过递归或者迭代的方式完成。下面是一个简单的递归版本的原地倒置栈实现：

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

// 定义栈的基本操作
typedef struct Node {
    int data;
    struct Node* next;
} StackNode;

StackNode* createNode(int data) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void push(StackNode** top, int data) {
    StackNode* newNode = createNode(data);
    newNode->next = *top;
    *top = newNode;
}

int pop(StackNode** top) {
    if (*top == NULL)
        return -1; // 栈空
    StackNode* temp = *top;
    int data = temp->data;
    *top = (*top)->next;
    free(temp);
    return data;
}

// 原地倒置栈的递归实现
void reverse(StackNode** top) {
    if (*top != NULL) {
        reverse(&(*top)->next); // 递归处理剩余部分
        printf("Reversed: %d\n", pop(top)); // 取出当前栈顶并打印
    }
}

// 主函数测试
int main() {
    StackNode* stack = NULL;
    push(&stack, 5);
    push(&stack, 4);
    push(&stack, 3);
    push(&stack, 2);
    push(&stack, 1);

    printf("Original Stack (top to bottom):");
    while (pop(&stack) != -1)
        printf("%d ", pop(&stack));

    reverse(&stack);
    printf("\nReversed Stack:");
    while (pop(&stack) != -1)
        printf("%d ", pop(&stack));

    return 0;
}

在这个例子中，`reverse` 函数会首先递归地处理剩余的栈元素，然后每次返回时都会取出栈顶并打印出来，从而实现了栈的反转。