递归函数可变引用问题：Rust中VecDeque元素批量有序移动

问题场景 #

我有一个名为crates的栈向量，每个栈用VecDeque<char>实现，整体类型是Vec<VecDeque<char>>。我把它当作栈使用，从后向前遍历、向后添加元素。现在需要将一个栈的最后k个元素移动到另一个栈，保持元素顺序不变。

示例：

stack_a = [ 1 <- 2 <- 3 <- 4 ]
stack_b = [ 5 <- 6 ]

# 从a移动k=3个元素到b
stack_b = [ 5 <- 6 <- 2 <- 3 <- 4 ]

如果允许打乱目标栈顺序，循环k次push(stack_b, pop(stack_a))即可，但这里要保持顺序，所以需要先弹出k个元素暂存再按原顺序推入。我尝试用递归实现，但遇到了引用问题。

现有代码问题 #

我的代码如下：

// 从正则捕获中提取栈ID
let source_id = usize::from_str(&cap[2]).unwrap() - 1;
let target_id = usize::from_str(&cap[3]).unwrap() - 1;
// 自定义函数
fn move_crates_simultaneously(
    amount: usize,
    source: Rev<Iter<char>>,
    target: &mut VecDeque<char>,
) {
    if amount == 0 {
        return;
    }
    let value = source.next();
    move_crates_simultaneously(amount - 1, source, target);
    target.push_back(*(value.unwrap()));
}
// 函数调用
move_crates_simultaneously(
    usize::from_str(&cap[1]).unwrap(),
    crates[source_id].iter().rev(),
    &crates[target_id],
);

当前问题：&crates[target_id]是&VecDeque<char>类型，但函数需要&mut VecDeque<char>。我猜测编译器无法确定源栈和目标栈不是同一个，所以没法创建可变引用。想知道Rust里能不能用这种方式解决？

解决方案 #

首先要指出：原代码用iter().rev()只是遍历源栈元素，并没有弹出元素，源栈的元素会保留，这不符合“移动”的语义。下面给出两种可行的解决思路：

思路1：递归实现+安全获取可变引用 #

先判断源栈和目标栈是否为同一个，再用split_at_mut安全获取两个不同元素的可变引用，同时修正递归逻辑实现元素移动：

fn move_crates_simultaneously(
    amount: usize,
    source: &mut VecDeque<char>,
    target: &mut VecDeque<char>,
) {
    if amount == 0 {
        return;
    }
    // 从源栈弹出元素
    let value = source.pop_back().unwrap();
    move_crates_simultaneously(amount - 1, source, target);
    // 按原顺序推入目标栈
    target.push_back(value);
}

// 调用逻辑
let k = usize::from_str(&cap[1]).unwrap();
if source_id == target_id {
    return; // 源和目标为同一栈，无需操作
}

// 用split_at_mut安全获取两个不同栈的可变引用
let (source, target) = {
    let split_idx = source_id.max(target_id);
    let (left, right) = crates.split_at_mut(split_idx);
    if source_id < target_id {
        (&mut left[source_id], &mut right[0])
    } else {
        (&mut right[0], &mut left[target_id])
    }
};

move_crates_simultaneously(k, source, target);

思路2：临时向量暂存（更简洁） #

如果不需要递归，用临时向量暂存弹出的元素，再反向推入目标栈，代码更直观：

let k = usize::from_str(&cap[1]).unwrap();
if source_id == target_id {
    return;
}

// 安全获取两个不同栈的可变引用
let (source, target) = {
    let split_idx = source_id.max(target_id);
    let (left, right) = crates.split_at_mut(split_idx);
    if source_id < target_id {
        (&mut left[source_id], &mut right[0])
    } else {
        (&mut right[0], &mut left[target_id])
    }
};

// 弹出k个元素到临时向量
let mut temp = Vec::with_capacity(k);
for _ in 0..k {
    temp.push(source.pop_back().unwrap());
}

// 反向推入目标栈，保持原顺序
temp.into_iter().rev().for_each(|c| target.push_back(c));

关键说明 #

Rust的借用检查器不允许同时获取同一向量中两个元素的可变引用，除非能证明它们是不同的元素。split_at_mut是标准解决方案，它能保证分割后的两个子切片无重叠，因此可以安全地同时持有内部元素的可变引用。

内容的提问来源于stack exchange，提问作者Th0rgal