用递归函数和栈逆序一个栈

[编程题]用递归函数和栈逆序一个栈

热度指数：8460 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个栈依次压入1,2,3,4,5，那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后，从栈顶到栈底为1,2,3,4,5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，不能用其他数据结构。

输入描述:

输入数据第一行一个整数N为栈中元素的个数。

接下来一行N个整数表示一个栈依次压入的每个元素。

输出描述:

输出一行表示栈中元素逆序后的栈顶到栈底的每个元素

示例1

输入

5
1 2 3 4 5

输出

1 2 3 4 5

算法知识视频讲解

helloxuanbao

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

typedef struct {
    int *data;
    int top;
} stack;

stack *new_stack(int cap);

void push(stack *st, int val);

int pop(stack *st);

bool is_empty(stack *st);

void destroy_stack(stack *st);

int remove_bottom(stack *st);

void reverse_stack(stack *st);

int main(void) {
    int n, x;
    scanf("%d", &n);
    stack *st = new_stack(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        push(st, x);
    }
    reverse_stack(st);
    while (!is_empty(st)) {
        x = pop(st);
        printf("%d", x);
        if (!is_empty(st))
            printf(" ");
    }
    printf("\n");
    destroy_stack(st);
    return 0;
}

int remove_bottom(stack *st) {
    int x = pop(st);
    if (is_empty(st)) {
        return x;
    }
    int next = remove_bottom(st);
    push(st, x);
    return next;
}

void reverse_stack(stack *st) {
    if (is_empty(st)) return;
    int bottom = remove_bottom(st);
    reverse_stack(st);
    push(st, bottom);
}

stack *new_stack(int cap) {
    stack *st = (stack *) malloc(sizeof(stack));
    st->data = (int *) malloc(sizeof(int) * cap);
    st->top = -1;
    return st;
}

void push(stack *st, int val) {
    st->data[++st->top] = val;
}

int pop(stack *st) {
    return st->data[st->top--];
}

bool is_empty(stack *st) {
    return st->top == -1;
}

void destroy_stack(stack *st) {
    free(st->data);
    free(st);
}

发表于 2022-02-17 00:11:53 回复(0)