使用遞歸在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