如何仅用递归函数和栈操作逆序一个栈

【题目】

一个栈依次压入1、2、3、4、5，那么从栈顶到栈底分别为5、4、3、2、1。将这个栈转置后，从栈顶到栈底为 1、2、3、4、5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，不能用其他数据结构。

【难度】

尉 ★★☆☆

【解答】

本题考查栈的操作和递归函数的设计，我们需要设计出两个递归函数。

递归函数一：将栈stack的栈底元素返回并移除。

具体过程就是如下代码中的getAndRemoveLastElement方法。

如果从stack的栈顶到栈底依次为3、2、1，这个函数的具体过程如图1-4所示。

图1-4

递归函数二：逆序一个栈，就是题目要求实现的方法，具体过程就是如下代码中的reverse方法。该方法使用了上面提到的getAndRemoveLastElement方法。

如果从stack的栈顶到栈底依次为3、2、1，reverse函数的具体过程如图1-5所示。

图1-5

getAndRemoveLastElement方法在图中简单表示为get方法，表示移除并返回当前栈底元素。