算法专题导航页面
【算法专题 - 栈】
- 《栈系列之 栈排序》
- 《栈系列之 最小栈的实现》
- 《栈系列之 用栈实现队列》
- 《栈系列之 递归实现一个栈的逆序》
【题目】
使用递归来完成一个栈的逆序操作。
【其他限制】
不能借助任何其他数据结构。
【图示】
无
【分析】
递归思想原本就和栈这一数据结构密不可分,题目要求不能借助任何其他数据结构,故我们可能需要充分利用栈的已有特性。因此题目等价于“使用递归思想和栈操作来逆序一个栈”。
设想有一个函数getAndRemovTailElement(),其功能是获取并删除一个栈的栈底元素。对于一个栈,通过多次调用getAndRemovTailElement(),我们即可得到一个栈的逆序序列。那么,接下来我们需要将关注点放在如何将该逆序序列保存在原始栈中,也就是完成栈的逆序。
【解决方案】
首先,设计函数: 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); // 原始栈逆序入栈
}