算法-不用额外空间逆序栈

2022-4-22 diaba 算法 

package com.jiucaiyuan.net.question;

import java.util.Stack;

/**
 * 【问题】不使用额外空间逆序一个栈：给你一个栈，请你逆序这个栈，
 * 不能申请额外的数据结构，只能使用递归函数，如何实现？
 * 【思路】通过用递归，利用栈帧局部变量保存，未主动额外申请空间
 *
 * @Author jiucaiyuan  2022/4/22 22:24
 * @mail services@jiucaiyuan.net
 */

public class ReverseStackNoExtraSpace {
    /**
     * 未申请额外空间（利用递归栈帧）逆序一个栈
     *
     * @param stack 待逆序的栈
     */
    public static void reverse(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return;
        }
        int i = getLastElement(stack);
        reverse(stack);
        stack.push(i);
    }

    /**
     * 功能：返回stack栈底元素，其他元素仍然在栈中，原来的顺序
     * 如(左侧是栈顶，右侧是栈底)：栈中入参[1,2,3]，返回3，栈变成[1,2]
     *
     * @param stack
     * @return 返回stack当前栈底元素
     */
    public static int getLastElement(Stack<Integer> stack) {
        int result = stack.pop();
        if (stack.isEmpty()) {
            return result;
        } else {
            int last = getLastElement(stack);
            stack.push(result);
            return last;
        }
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(6);
        System.out.println(stack);
        reverse(stack);
        System.out.println(stack);
    }


}

« 算法-数字字符转化为字母字符种数 | 算法-字符串的全排列»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022