首页 > 试题广场 >

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

[编程题]用递归函数和栈逆序一个栈
  • 热度指数:8452 时间限制: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个整数X_i表示一个栈依次压入的每个元素。


输出描述:
输出一行表示栈中元素逆序后的栈顶到栈底的每个元素
示例1

输入

5
1 2 3 4 5

输出

1 2 3 4 5
import java.util.Scanner;
import java.util.Stack;

public class Main{

    // 将stack的栈底元素移除并返回
    public static int getAndRemoveLastElement(Stack<Integer> stack){
        int result = stack.pop();
        if (stack.isEmpty()){
            return result;
        } else {
            int last = getAndRemoveLastElement(stack);
            stack.push(result);
            return last;
        }
    }

    // 逆序一个栈
    public static void reverse(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return;
        }
        int i = getAndRemoveLastElement(stack);
        reverse(stack);
        stack.push(i);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 迷惑行为:本题的输入是入栈的反顺序,因此借助stackPlus将输入逆序
        Stack<Integer> stackInt = new Stack<>();
        Stack<Integer> stackPlus = new Stack<>();
        while (sc.hasNextInt()){
            int N = sc.nextInt();
            for (int i = 0; i < N; i++){
                stackPlus.push(sc.nextInt());
            }
            while (!stackPlus.isEmpty()){
                stackInt.push(stackPlus.pop());
            }
            reverse(stackInt);
            while (!stackInt.isEmpty()){
                System.out.print(stackInt.pop() + " ");
            }
        }
    }
}

发表于 2020-04-04 16:04:37 回复(1)

void reverse_print(int ptr, int n, int arr[]){
    if(ptr < n){
        reverse_print(ptr+1, n, arr);
        printf("%d ", arr[ptr]);
    } else{
        return;
    }
}


int main(){
    int n;
    scanf("%d", &n);
    int arr[n];
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    reverse_print(0, n, arr);

    return EXIT_SUCCESS;
}



为什么你们都手动弄了个栈……
我的理解是用递归模拟栈的逆序输出
直接递归打印就van♂事
发表于 2019-11-05 17:35:06 回复(2)
这题真有毒,输出最后一个要有个空格和回车
而且把栈翻转后,又要从栈底往栈顶输出,和不翻转从栈顶往栈底输出没什么区别,翻转了还更麻烦,干脆不翻转了
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            stack.add(reader.nextInt());
        }
        Fun(stack);
        System.out.println();
        reader.close();
    }

    public static void Fun(Stack<Integer> stack) {
        //自顶向下打印栈
        if (stack.isEmpty()) {
            return;
        }
        int a = stack.pop();
        System.out.print(a+" ");
        Fun(stack);
    }
}
当然也有翻转的实现方式
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            stack.push(reader.nextInt());
        }
        Fun2(stack);
        Fun(stack);
        System.out.println();
        reader.close();
    }

    public static void Fun(Stack<Integer> stack) {
        //自底向上打印栈
        if (stack.isEmpty()) {
            return;
        }
        int top = stack.pop();
        Fun(stack);
        System.out.print(top + " ");
    }

    public static void Fun2(Stack<Integer> stack) {
        //翻转函数
        if (stack.isEmpty()) {
            return;
        }
        int last = getLast(stack);
        Fun2(stack);
        stack.push(last);
    }

    public static int getLast(Stack<Integer> stack) {
        //取出栈底元素
        int top = stack.pop();
        if (stack.isEmpty()) {
            return top;
        } else {
            int last = getLast(stack);
            stack.push(top);
            return last;
        }
    }
}



编辑于 2019-08-31 18:36:27 回复(3)
#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)
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)
左老师课堂上的经典例题,这两个递归函数还是得画个图好好理解一下。基本思路是:每次获得栈底元素,当一层层调用递归函数,就能够得到栈中只有一个元素的base case。栈顶弹出后直接压栈,然后一层层返回去,将之前的栈底压栈,这样之前的栈底就变成了现在的栈顶。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < n; i++) stack.push(Integer.parseInt(strArr[i]));
        reverse(stack);
        while(!stack.isEmpty()) System.out.print(stack.pop() + " ");
    }
    
    private static int getLast(Stack<Integer> stack) {
        int result = stack.pop();
        if(!stack.isEmpty()){
            int last = getLast(stack);
            stack.push(result);
            return last;
        }else
            return result;        // 只有一个元素,返回去
    }
    
    private static void reverse(Stack<Integer> stack) {
        if(stack.isEmpty()) return;
        int elem = getLast(stack);     // 获得栈底
        reverse(stack);
        stack.push(elem);
    }
}

发表于 2021-11-14 18:00:24 回复(0)
import java.util.Stack;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main{
    private Stack<Integer> myStack;
    public Main(){
        this.myStack = new Stack<>();
    }
    public static void main(String[] args) throws IOException{
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(sc.readLine());
        String[] inputData = sc.readLine().split(" ");
        Main m = new Main();
        for(int i=0;i<num;i++){
            m.myStack.push(Integer.parseInt(inputData[num-1-i])); 
        }
        m.reverse(m.myStack);
        m.print(m.myStack);

    }
    
    public int getandRemoveLast(Stack<Integer> stack){
        int result = stack.pop();
        if(stack.isEmpty()){
            return result;
        }
        else{
            int last = getandRemoveLast(stack);
            stack.push(result);
            return last;
        }
    }
    
    public void reverse(Stack<Integer> stack){
        if(stack.isEmpty()){
            return;
        }
        else{
            int i = getandRemoveLast(stack);
            reverse(stack);
            stack.push(i);
        }     
    }
    
    public void print(Stack<Integer>stack){
        if(stack.isEmpty()){
            return;
        }
        else{
            
            if(stack.size()==1){
                System.out.print(stack.pop());
            }
            else{
                System.out.print(stack.pop()+" ");
            }
            print(stack);
        }
    }

}

发表于 2021-03-18 22:04:27 回复(0)
#include<iostream>
using namespace std;
void dfs(int i,int n){
    if(i==n)return;
    int x;
    scanf("%d",&x);
    dfs(i+1,n);
    printf("%d ",x);
}
int main(){
    int n;
    scanf("%d",&n);
    dfs(0,n);
    return 0;
}
发表于 2020-09-24 17:06:18 回复(0)
    private void reverse(Deque<Integer> stack){
        if(stack.isEmpty()){
            return;
        }
        int temp = stack.pop();
        reverse(stack);
        stack.push(temp);
    }
 没看懂题。。。 直接这么写不行吗
发表于 2020-09-10 11:12:04 回复(1)
这题是不是有问题啊?栈逆序后再打印出来的顺序应该和输入一样啊。输入1,2,3,4,5,栈顶到栈底为5,4,3,2,1,逆序后从栈顶到栈底的元素变成1,2,3,4,5,再打印出来就是1,2,3,4,5。干脆不用逆序,直接从栈里弹出来打印就是5,4,3,2,1。
发表于 2020-06-25 16:21:40 回复(0)
#include <bits/stdc++.h>
using namespace std;

void F(stack<int> S){
    cout<<S.top()<<" ";
    S.pop();
    if(!S.empty())
        F(S);
}

int main(){
    stack<int> S;
    int n, x;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        S.push(x);
    }
    F(S);
    return 0;
}

发表于 2020-02-01 01:21:04 回复(0)
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		Stack<Integer> stack = new Stack<>();
		int[] arr = new int[n];
		for(int i=0;i<n;i++) {
			arr[i] = scanner.nextInt();
		}
		for(int i=n-1;i>=0;i--) {
			stack.push(arr[i]);
		}
		
		reverse(stack);
		
		for(int i=0;i<n;i++) {
			System.out.print(stack.pop() + " ");
		}
	}
	
	
	private static int getAndRemoveLastEle(Stack<Integer> stack) {
		int val = stack.pop();
		if(stack.isEmpty()) {
			return val;
		}else {
			int res = getAndRemoveLastEle(stack);
			stack.push(val);
			return res;
		}
	}
	
	private static void reverse(Stack<Integer> stack) {
		if(stack.isEmpty()) {
			return;
		}
		
		int lastEle = getAndRemoveLastEle(stack);
		reverse(stack);
		stack.push(lastEle);
	}
}

发表于 2019-10-21 15:17:48 回复(0)
#include<bits/stdc++.h>
using namespace std;
stack<int>s,t;
void func()
{
    int m=s.top();
    s.pop();
    cout<<m<<" ";
    if(!s.empty())
        func();
}
int main()
{
    int n,x;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        s.push(x);
    }
    func();
    return 0;
}

发表于 2019-08-23 22:38:17 回复(1)
这道题的输出属实尴尬
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;

int popBottom(stack<int>& sta)
{
	int top = sta.top();
	sta.pop();
	if (sta.empty())return top;
	int down = popBottom(sta);
	sta.push(top);
	return down;
}
void reverseSta(stack<int>&sta)
{
	if (sta.size() == 1)return;
	int bottom = popBottom(sta);
	reverseSta(sta);
	sta.push(bottom);
}

int main()
{
	int n;
	scanf("%d", &n);
	stack<int> sta;
	for (int i = 0; i < n; i++)
	{
		int tmp;
		scanf("%d", &tmp);
		sta.push(tmp);
	}
	//reverseSta(sta);
	while (!sta.empty())
	{
		int top = sta.top();
		sta.pop();
		printf("%d ", top);
	}
}

发表于 2019-08-10 11:31:04 回复(0)
有毒的一道题,要用递归逆序一个栈,但是输入与输出顺序相反,那我还逆序干嘛,直接全部进栈,再全部出栈,不就行了。
此外使用python,一直卡在90%的测试用例点上,考试模式也不提示错误用例,唉,真的难受。
import sys
from collections import deque

def pop_bottom(stack):
    if len(stack) == 1:
        return stack.pop()
    num = stack.pop()
    res = pop_bottom(stack)
    stack.append(num)
    return res


def reverse(stack):
    if stack is None or len(stack) == 0:
        return
    num = pop_bottom(stack)
    reverse(stack)
    stack.append(num)


N = int(sys.stdin.readline().strip())
nums = [int(i) for i in sys.stdin.readline().strip().split()]
stack = deque()
for num in nums:
    stack.append(num)
reverse(stack)
while len(stack) > 0:
    print(stack.popleft(), end=' ')


发表于 2019-10-17 23:56:41 回复(0)

来一个python能全部跑通的版本


注意: python 的recursion有次数限制, 默认的是1000, 但此处的测试用例的最后一个输入了1500多个数字, 所以要改变默认的限制, 这里保险设置成了2000.

​
​
​import sys
# python has a recurision limitation
# default is 1000
sys.setrecursionlimit(2000)

def getLastRemove(stack): 

    res = stack.pop()
    if len(stack) == 0:
        return res
    last = getLastRemove(stack)
    stack.append(res)
    return last

def reverse(stack): 
    if len(stack) == 0:
        return None
    i = getLastRemove(stack)
    reverse(stack)
    stack.append(i)
    return None

stack = []
N = int(input())

a = input()
for i in a.split():
    stack.append(int(i))

reverse(stack)

s=""

for i in range(N):
    s+= str(stack.pop())
    if i < N-1:
        s+= " "
print(s)

发表于 2022-12-11 17:35:56 回复(0)
N = int(input())
X = list(map(int,input().split()))
mm = [X.pop() for i in range(0,len(X))]

def resort(n,x):
    if len(x)-n < n-1:
        x[len(x)-n],x[n-1] = x[n-1],x[len(x)-n]
        resort(n-1,x)
    return x

print(" ".join(map(str,resort(N,mm))))
发表于 2023-06-14 17:51:57 回复(0)
不知道这样符不符合题意的
#include <bits/stdc++.h>

using namespace std;

stack<int> st;    // 栈

// 递归函数
int dfs(stack<int>& st){
    if(st.size() == 1){
        int res = st.top();
        st.pop();
        return res;
    }
    st.pop();
    return dfs(st);
}

int main()
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; ++i) cin >> nums[i];
    for(int i = 0; i < n; ++i){
        st.push(nums[i]);
        cout << dfs(st) << " " ;
    }
    return 0;
}


发表于 2022-04-07 10:00:00 回复(0)

写个go语言版本的,这牛马题非要逆序输出

package main
import "fmt"
type Stack struct {
    stack []int
}
func Constructor() Stack {
    return Stack{make([]int, 0)}
}
func getAndRemoveLastElement(this *Stack) int {
    result := this.pop()
    if len(this.stack) == 0 {
        return result
    } else {
        last := getAndRemoveLastElement(this)
        this.push(result)
        return last
    }
}
func reserve(this *Stack) {
    if len(this.stack) == 0 {
        return
    }
    i := getAndRemoveLastElement(this)
    reserve(this)
    this.push(i)
}
func (this *Stack) pop() int {
    value := this.stack[len(this.stack)-1]
    this.stack = this.stack[:len(this.stack)-1]
    return value
}
func (this *Stack) push(val int) {
    this.stack = append(this.stack, val)
}
func main() {
    stack := Constructor()
    var number int
    fmt.Scanf("%d", &number)
    for i := 0; i < number; i++ {
        var tmp int
        fmt.Scanf("%d", &tmp)
        stack.stack = append(stack.stack, tmp)
    }
    reserve(&stack)
    for i := number-1; i >=0; i-- {
        fmt.Printf("%d ",stack.stack[i])
    }
}
发表于 2022-02-20 16:15:38 回复(0)
用递归对栈进行逆序,不能使用其他数据结构;
首先,dfs_last实现:将栈底元素移除,并返回;
然后dfs实现:每次将栈底元素移除,并记录栈底元素,然后递归,最后将栈底元素压入
#include "iostream"
#include "stack"
//#include "bits/stdc++.h"

using namespace std;

int dfs_last(stack<int>& stk)
{
    //将栈底元素移除,并返回
    int tmp=stk.top();
    stk.pop();
    if(stk.empty()) return tmp;
    else {
        int t=dfs_last(stk);
        stk.push(tmp);
        return t;
    }
}

void dfs(stack<int>& stk)
{
    if(stk.empty()) return;
    int tmp;
    //每次获得栈底元素,并将栈底元素移除
    tmp=dfs_last(stk);
    dfs(stk);
    stk.push(tmp);
}

int main()
{
    int len;
    cin>>len;
    stack<int> stk;
    int tmp;
    for(int i=0;i<len;i++)
    {
        cin>>tmp;
        stk.push(tmp);
    }
    dfs(stk);
    for(int i=0;i<len;i++)
    {
        cout<<stk.top()<<' ';
        stk.pop();
    }
    return 0;
}


发表于 2021-12-28 10:40:54 回复(0)