Geek Answers Handbook

Reverse stack in Python using recursion

I deal with practical issues. To do this, you need to flip the stack without using any other data structures, except for another stack.

I know that I will need a helper function that adds popup numbers when the original stack is empty.

Can someone get me? I'm stuck here

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

Thank!

The Stack class has functions pop, pushand is_empty.

+5
source share
6 answers

Here is another possibility, using the battery and an auxiliary function. I use only the methods suggested in your class Stack, and no other data structures (such as Python lists):

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)

, , .

0
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]
+1

, 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.

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

, , , ,

Stack ,

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, , ++

0
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]

You can even get a little fancy by using the fact that closing keeps a parameter stack flip_stackin the scope of a recursive function, so you don't need it to be a parameter for an inner function. eg.

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

Or, get rid of all the parameters from the recursive function, and your stream stack frame will thank you:

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
0
source

More articles:


All Articles