MENU

Reverse a Stack Only with Recursion and That Stack

2022 年 05 月 01 日 • 阅读: 1435 • 算法

只用递归和自身反转栈,这题机试没法考,面试考纯属刁难,当作回溯练习食用最佳。

步骤如下:

  1. 获取并删除栈底
  2. 反转剩余栈
  3. 将原栈底入栈

举个例子,要把 [1, 2, 3, 4, 5 变为 [5, 4, 3, 2, 1

  1. 获取并删除栈底 1,变为 [2, 3, 4, 5
  2. 反转剩余栈,变为 [5, 4, 3, 2
  3. 原栈底 1 入栈,变为 [5, 4, 3, 2, 1

第 1 步也可递归,出口是只有一个元素,此时弹栈顶返回。否则原问题等价于去掉栈顶,递归子栈,恢复栈顶。这样完美符合它的定义,即删除栈底并返回,剩余元素顺序不变。

int del_bottom(stack<int>& s) {
    int top = s.top(); s.pop();
    if (s.empty()) return top;

    int bottom = del_bottom(s);
    s.push(top); // 回溯恢复现场

    return bottom;
}

void reverse(stack<int>& s) {
    if (s.size() <= 1) return;
    int bottom = del_bottom(s);
    reverse(s);
    s.push(bottom);
}

其实,你还是用了其它栈,即函数调用栈,进入下层递归时,弹出的栈顶被自动压入系统栈,返回时又被你压回原栈,只是原栈底没有被压回。

TG 大佬群 QQ 大佬群

返回文章列表 文章二维码
本页链接的二维码
打赏二维码