Đảo ngược ngăn xếp bằng Python sử dụng đệ quy

Question

Tôi đang thực hiện một số câu hỏi thực hành. Điều này cần phải đảo ngược một ngăn xếp mà không sử dụng bất kỳ cấu trúc dữ liệu nào khác ngoại trừ một ngăn xếp khác.

Tôi biết tôi sẽ cần một hàm mà gắn thêm những con số pop-ed khi chồng ban đầu là rỗng.

Có thể ai đó cho tôi bắt đầu? Tôi bị kẹt ở đây

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

Cảm ơn!

Lớp Ngăn xếp có các chức năng pop, push và is_empty.

Answer 1

Đây là một khả năng khác, sử dụng bộ tích lũy và chức năng trợ giúp. Tôi chỉ sử dụng những phương pháp được cung cấp trong lớp Stack của bạn, và không có cấu trúc dữ liệu khác (chẳng hạn như danh sách của 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) 

Hãy nhận biết rằng ngăn xếp ban đầu sẽ trống ở cuối, và ngăn xếp lộn là trả lại.

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

Các công trình sau đây nếu chồng là danh sách Python bản địa:

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[:] gây ngăn xếp ban đầu để được bảo tồn.

Không khó để sửa đổi điều này để xử lý lớp học Stack nhất định của bạn.

Answer 4

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

Answer 5

Giả sử không có cấu trúc dữ liệu nên được sử dụng thậm chí không liệt kê để giữ kết quả cuối cùng đây là một khả năng giải pháp

Stack ở đây sẽ được coi là một danh sách mà hỗ trợ các chức năng sau

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

Giải pháp 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)] 

Thậm chí bạn có thể mã mà không cần sử dụng các IsEmpty chức năng NotEmpty ot

Giải pháp 2:

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

Note * * Sử dụng ngoại lệ đối với Kiểm tra điều kiện là một hành vi được chấp nhận trong Python như nó không có thêm chi phí như trong 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) 

sản lượng

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

Bạn thậm chí có thể có được một chút ưa thích bằng cách sử dụng thực tế rằng việc đóng giữ thông số stack của flip_stack trong phạm vi của hàm đệ quy, do đó bạn không cần nó là tham số cho hàm bên trong. ví dụ.

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()) 

Hoặc, thoát khỏi tất cả các thông số về chức năng đệ quy, và ngăn xếp khung chủ đề của bạn sẽ cảm ơn bạn:

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