栈系列之 递归实现一个栈的逆序
【算法专题 - 栈】
- 《》
- 《》
- 《》
- 《》
【题目】 使用递归来完成一个栈的逆序操作。
【其他限制】 不能借助任何其他数据结构。
【图示】 无
【解决方案】 首先，设计函数: int getAndRemovTailElement(…)。如下图所示： 其次，设计递归函数: void stackReverse(…)，该函数将调用上述函数，最终完成一个栈的逆序。如下图所示：
【代码实现】
/*
* DESC:
* Get and remove the tail element of a stack
*/
public int getAndRemovTailElement(Stack<Integer> stack) {
int result = stack.pop();
if (stack.IsEmpty()) // 递归结束条件
return result;
int tail = getAndRemovTailElement(stack); // 返回栈底元素
stack.push(result);// 递归结束条件触发后，将弹出的非栈底元素入栈，保持栈原始结构
return tail;
}
}
/*
* DESC:
* Reverse a stack
*/
public void stackReverse(Stack<Integer> stack) {
if (stack.IsEmpty()) // 递归结束条件
return;
int tmp == getAndRemovTailElement(stack); // 去除栈底元素之后的栈
stackReverse(stack); // 递归调用，触发上一步操作
stack.push(tmp); // 原始栈逆序入栈
}
