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

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

热度指数：8600 时间限制：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

算法知识视频讲解

Rust

AlexanderGan

rust版本：

use std::io::{prelude::*, BufReader};

pub fn get_and_remove_stack_bottom_element(stk: &mut Vec<i32>) -> i32 {
    let ans = stk.pop().unwrap();
    if stk.is_empty() {
        return ans;
    } else {
        let last = get_and_remove_stack_bottom_element(stk);
        stk.push(ans);
        return last;
    }
}

pub fn reverse_stack(stk: &mut Vec<i32>){
    if stk.is_empty() {
        return;
    }

    let i = get_and_remove_stack_bottom_element(stk);
    reverse_stack(stk);
    stk.push(i);
}

pub fn main() {
    let stdin = std::io::stdin();
    let handle = stdin.lock();
    let mut reader = BufReader::new(handle);

    let mut s = String::new();
    reader.read_line(&mut s).expect("err");
    let n = s.trim().parse::<i32>().expect("err");
    s.clear();
    reader.read_line(&mut s).expect("err");
    let mut stk: Vec<i32> = s.trim().split(' ').map(|x| x.parse().unwrap()).collect();
    reverse_stack(&mut stk);

    while stk.len() > 0 {
        print!("{} ", stk.pop().unwrap());
    }
}

发表于 2022-01-24 21:30:10 回复(0)