2.3 如何翻转栈的所有元素

【出自ALBB面试题】

难度系数：★★★★☆

被考察系数：★★★★☆

题目描述：

翻转（也叫颠倒）栈的所有元素，如输入栈{1, 2, 3, 4, 5}。其中，1处在栈顶，翻转之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。

分析与解答：

最容易想到的办法是，申请一个额外的队列，先把栈中的元素依次出栈放到队列里，然后把队列里的元素按照出队列顺序入栈，这样就可以实现栈的翻转，这种方法的缺点是需要申请额外的空间存储队列，因此，空间复杂度较高。下面介绍一种空间复杂度较低的递归的方法。

递归程序有两个关键因素需要注意：递归定义和递归终止条件。经过分析后，很容易得到该问题的递归定义和递归终止条件。递归定义：将当前栈的最底元素移到栈顶，其他元素顺次下移一位，然后对不包含栈顶元素的子栈进行同样的操作。终止条件：递归下去，直到栈为空。递归的调用过程如下图所示。

在上图中，对于栈{1, 2, 3, 4, 5}，进行翻转的操作：首先把栈底元素移动到栈顶得到栈{5, 1, 2, 3, 4}，然后对不包含栈顶元素的子栈进行递归调用（对子栈元素进行翻转），子栈{1, 2, 3, 4}翻转的结果为{4, 3, 2, 1}，因此，最终得到翻转后的栈为{5, 4, 3, 2, 1}。

此外，由于栈的后进先出的特点，使得只能取栈顶的元素，因此，要把栈底的元素移动到栈顶也需要递归调用才能完成。主要思路：把不包含该栈顶元素的子栈的栈底的元素移动到子栈的栈顶，然后把栈顶的元素与子栈栈顶的元素（其实就是与栈顶相邻的元素）进行交换。

为了更容易理解递归调用，可以认为在进行递归调用时，子栈已经把栈底元素移动到了栈顶。在上图中，为了把栈{1, 2, 3, 4, 5}的栈底元素5移动到栈顶，首先对子栈{2, 3, 4, 5}，进行递归调用，调用的结果为{5, 2, 3, 4}，然后对子栈顶元素5，与栈顶元素1进行交换得到栈{5, 1, 2, 3, 4}，实现了把栈底元素移动到了栈顶。

实现代码如下：

程序的运行结果为

算法性能分析：

把栈底元素移动到栈顶操作的时间复杂度为O（N），在翻转操作中对每个子栈都进行了把栈底元素移动到栈顶的操作，因此，翻转算法的时间复杂度为O（N^2）。

引申：如何给栈排序。

分析与解答：

很容易通过对上述方法进行修改得到栈的排序算法。主要思路：首先对不包含栈顶元素的子栈进行排序，如果栈顶元素大于子栈的栈顶元素，则交换这两个元素。因此，在上述方法中，只需要在交换栈顶元素与子栈顶元素时增加一个条件判断即可实现栈的排序。

实现代码如下：

程序的运行结果为

算法性能分析：

这种方法的时间复杂度为O（N^2）。