Реверсирование стека в Python с использованием рекурсии

Question

Я занимаюсь практическими вопросами. Для этого нужно перевернуть стек без использования каких-либо других структур данных, кроме другого стека.

Я знаю, что мне понадобится вспомогательная функция, которая добавляет всплывающие номера, когда исходный стек пуст.

Может кто-нибудь меня завести? Я застрял здесь

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

Спасибо!

Класс Stack имеет pop, push и is_empty функции.

Answer 1

Вот еще одна возможность, используя аккумулятор и вспомогательную функцию. Я только с помощью методов, в вашем Stack классе, и никакие другие структуры данных (такие как списки Питона):

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 ВЗ функциональность 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] 

Вы даже можете получить немного фантазии, используя тот факт, что замыкание сохраняет параметр stackflip_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