document.write('最容易想到的办法是申请一个额外的队列，先把栈中的元素依次出栈放到队列里，然后把队列里的元素按照
出队列顺序入栈，这样就可以实现栈的翻转，这种方法的缺点是需要申请额外的空间存储队列，因此，空间
复杂度较高。下面介绍一种空间复杂度较低的递归的方法。
递归程序有两个关键因素需要注意：递归定义和递归终止条件。经过分析后，很容易得到该问题的递归定
义和递归终止条件。递归定义：将当前栈的最底元素移到栈顶，其他元素顺次下移一位，然后对不包含栈顶
元素的子栈进行同样的操作。终止条件：递归下去，直到栈为空。递归的调用过程如下图所示：
在上图中，对于栈{1，2，3，4，5}，进行翻转的操作为：首先把栈底元素移动到栈顶得到栈{5，1，2，
3，4}，然后对不包含栈顶元素的子栈进行递归调用(对子栈元素进行翻转)，子栈{1，2，3，4}翻转的结果
为{4，3，2，l}，因此，最终得到翻转后的栈为{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)，实现了把栈
底元素移动到栈顶。
实现代码如下：
#Python中没有栈的模块,所以先新建一个栈类
class Stack:
#模拟栈
def __init__(self):
self.items=[]
#判断栈是否为空
def empty(self):
return len(self.items)==0
#返回栈的大小
def size(self):
return len(self.items)
#返回栈顶元素
def peek(self):
if not self.empty():
return self.items[len(self.items)-1]
else:
return None
#弹栈
def pop(self):
if len(self.items)＞0:
return self.items.pop()
else:
priiit "栈已经为空"
return None
#压栈
def push(self,item):
self.items.append(item)
"""
方法功能: 把栈底元素移动到栈顶
参数: s栈的引用
"""
def moveBottomToTop(s):
if s.empty():
return
top1=s.peek()
s.pop()#弹出栈项元素
if nots.empty():
#递归处理不包含栈顶元素的子栈
moveBottomToTop(s)
top2=s.peek()
s.pop()
#交换栈顶元素与予栈栈顶元素
s.push(top1)
s.push(top2)
else:
s.push(top1)
def reverse_stack(s):
if s.empty():
return
#把栈底元素移动到栈顶
moveBottomToTop(s)
top=s.peek()
s.pop()
#递归处理子栈
reverse_stack(s)
s.push(top)
if __name__=="__main__":
s=Stack()
s.push(5)
s.push(4)
s.push(3)
s.push(2)
s.push(1)
reverse_stack(s)
print "翻转后出栈顺序为:",
while nots.empty():
print s.peek(),
s.pop()
程序的运行结果为：
翻转后出栈顺序为：5 4 3 2 1
算法性能分析：
把栈底元素移动到栈顶操作的时间复杂度为O(N)，在翻转操作中对每个子栈都进行了把栈底元素移动到
栈顶的操作，因此，翻转算法的时间复杂度为O(N2)。
');
![\"360截图20190815222932828.jpg\"](\"http://www.alatiku.com/d/file/shiti/ccda36b32ab709cfa1b910346ee8dbfd.jpg\")
![\"360截图20190815223009277.jpg\"](\"http://www.alatiku.com/d/file/shiti/9e352418844e302fef5c4ea7e54fa6e7.jpg\")