Leaky Cauldron
0%

递归逆序栈

Posted on Edited on

题目

逆序一个栈, 且不能使用额外的数据结构, 只可使用递归函数

题解

可将问题分为两个步骤:

  1. 弹出栈底元素并返回
  2. 获取栈底元素并将其放回栈顶

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class ReverseStackUsingRecursive {
    public static void reverse(Stack<Integer> stack) {
        if (stack.isEmpty()) return;

        int ele = getAndRemoveLastElement(stack);
        reverse(stack);
        stack.push(ele);
    }

    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;
        }
    }
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def reverse(stack):
    if not stack or len(stack) == 0:
        return
    ele = get_and_remove_last_element(stack)
    reverse(stack)
    stack.append(ele)


def get_and_remove_last_element(stack):
    result = stack.pop()
    if len(stack) == 0:
        return result
    else:
        last = get_and_remove_last_element(stack)
        stack.append(result)
        return last

Go

若不使用指针的指针则需注意引用传递, 否则会由于 stack 数组不更新进入死循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func reverse(stack []int) {
	if stack == nil || len(stack) == 0 {
		return
	}

	ele, stack := getAndRemoveLastElement(stack)	// 需将 stack 重新赋值
	reverse(stack)
	stack = append(stack, ele)
}

func getAndRemoveLastElement(stack []int) (int, []int) {
	result := stack[len(stack)-1]
	stack = stack[:len(stack)-1]
	if len(stack) == 0 {
		return result, stack
	} else {
		last, stack := getAndRemoveLastElement(stack)
		stack = append(stack, result)
		return last, stack
	}
}