使用递归在Python中颠倒堆栈

Question

我正在做一些练习题。这需要在不使用除另一个堆栈之外的任何其他数据结构的情况下反转堆栈。

我知道我需要一个辅助函数，在原始堆栈为空时附加弹出的数字。

有人能让我开始吗？我卡在这里

def flip_stack(s): 
    if not s.is_empty(): 
     temp = s.pop 
     flip_stack(s) 

谢谢！

堆栈类具有pop,push和is_empty函数。

Answer 1

下面是使用累加器和辅助函数的另一种可能性。我只使用在Stack类提供的方法，并没有其他的数据结构（如Python的列表）：

def flip_stack(s): 
    return flip_stack_helper(s, Stack()) # Stack is your stack class 

def flip_stack_helper(s, t): 
    if s.is_empty(): 
     return t 
    t.push(s.pop()) 
    return flip_stack_helper(s, t) 

注意，原来堆将是空的结尾，并翻转堆栈回。

Answer 2

def reverse(orig, reversel=None): 
    if not reversel: 
     reversel = [] 
    reversel.append(orig.pop()) 
    if orig: 
     reverse(orig, reversel) 
    return reversel 

stack = [1, 2, 3, 4, 5] 
stack = reverse(stack) 
print stack 
[5, 4, 3, 2, 1] 

Answer 3

下工作，如果堆栈是一个原生的Python列表：

def flip(stack): 
    def helper(old_stack, new_stack): 
     if old_stack: 
      new_stack.append(old_stack.pop()) 
      return helper(old_stack, new_stack) 
     else: 
      return new_stack 
    return helper(stack[:], []) 

stack[:]导致原始堆被保留。

不应该很难修改这个来处理给定的Stack类。

Answer 4

>>> liste = [1, 2, 3, 4, 5] 
>>> liste[::-1] 
[5, 4, 3, 2, 1] 

Answer 5

假设没有数据结构应采用甚至没有列出来这里举行最后的结果是一个可能的解决方案

这里的堆栈将被视为支持如下功能列表

append(elem) ---- push(elem) 
pop()   ---- pop() 
if <some stack>---- NotEmpty() 

解决方案1：

def flip_stack(s): 
    while True: 
     if s: 
      yield s.pop() 
     else: 
      return 

stack = [1,2,3,4,5] 
revStack = [x for x in flip_stack(stack)] 

即使您不使用所述的IsEmpty OT NotEmpty功能

解决方案2：

def flip_stack(s): 
    while True: 
     try: 
      yield s.pop() 
     except IndexError: 
      return 

注* *使用异常为条件检查是在Python一个公认的行为，因为它没有开销加入作为在C++

Answer 6

class Stack(object): 
    def __init__(self,items=[]): 
     self.stack = items 

    def is_empty(self): 
     return not self.stack 

    def pop(self): 
     return self.stack.pop() 

    def push(self,val): 
     self.stack.append(val) 

    def __repr__(self): 
     return "Stack {0}".format(self.stack) 

def flip_stack(stack): 
    def flip_stack_recursive(stack,new_stack=Stack()): 
     if not stack.is_empty(): 
      new_stack.push(stack.pop()) 
      flip_stack_recursive(stack,new_stack) 
     return new_stack 
    return flip_stack_recursive(stack) 


s = Stack(range(5)) 
print s 
print flip_stack(s) 

收益率

Stack [0, 1, 2, 3, 4] 
Stack [4, 3, 2, 1, 0] 

你甚至可以使用闭合将flip_stack的参数flip_stack保留在递归函数的范围内的事实可能会有点花哨，所以您不需要它作为内部函数的参数。例如

def flip_stack(stack): 
    def flip_stack_recursive(new_stack): 
     if not stack.is_empty(): 
      new_stack.push(stack.pop()) 
      flip_stack_recursive(new_stack) 
     return new_stack 
    return flip_stack_recursive(Stack()) 

或者，得到的递归函数摆脱了所有的参数，和你的线程的堆栈帧会感谢你：

def flip_stack(stack): 
    new_stack = Stack() 
    def flip_stack_recursive(): 
     if not stack.is_empty(): 
      new_stack.push(stack.pop()) 
      flip_stack_recursive() 
    flip_stack_recursive() 
    return new_stack