Reversing a Stack in Python using recursion

Question

I'm doing some practise questions. This one needs to reverse a stack without using any other data structures except another stack.

I know I will need a helper function that appends the pop-ed numbers once the original stack is empty.

Can somebody get me started? I'm stuck here

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

Thanks!

The Stack class has pop, push and is_empty functions.

This sounds like a homework question. If so, you should add a 'homework' tag — K Mehta, Mar 13 '12 at 15:57
@KshitijMehta The homework tag has been deprecated - http://meta.stackexchange.com/questions/147100/the-homework-tag-is-now-officially-deprecated — Alex L, Apr 16 '13 at 01:23
@AlexL The tag was deprecated in September 2012. My comment is from March 2012. — K Mehta, Apr 16 '13 at 04:52
@KshitijMehta Oops, I thought your comment (and this question) was from this year. Never mind then! — Alex L, Apr 16 '13 at 05:12

fraxel · Answer 1 · 2012-03-13T16:01:52.203

1

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]

edited Mar 13 '12 at 16:01

answered Mar 13 '12 at 15:26

fraxel

34,470
11
98
102

You'll only be able to use this function once - reversel will not get reset after each call. See here: http://stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument – grifaton Mar 13 '12 at 15:43
@grifaton - excellent point, lost it in the change to only being able to call with one argument! – fraxel Mar 13 '12 at 15:50
fixed default argument oversight – fraxel Mar 13 '12 at 16:04

mtadd · Answer 2 · 2013-04-16T02:25:09.640

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)

yields

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

You could even get a little fancy using the fact that the closure keeps the stack parameter of flip_stack in the scope of the recursive function, so you don't need it to be a parameter to the inner function. e.g.

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 parameters on the recursive function, and your thread 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

score 0 · Answer 3 · answered Mar 13 '12 at 15:42

0

The following works if stack is a native Python list:

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[:] causes the original stack to be preserved.

It shouldn't be hard to modify this to handle your given Stack class.

answered Mar 13 '12 at 15:42

grifaton

3,986
4
30
42

But, it gives me error saying "Stack" object is not subscriptable. – Mar 13 '12 at 15:44
That's probably a problem with "stack[:]", which assumes that your stack is a native list. I'll update my answer. – grifaton Mar 13 '12 at 15:46

Óscar López · Accepted Answer · 2012-03-13T22:41:36.940

Here's another possibility, using an accumulator and a helper function. I'm only using the methods provided in your Stack class, and no other data structures (such as Python's 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)

Be aware that the original stack will be empty at the end, and the flipped stack is returned.

score 0 · Answer 5 · answered Mar 13 '12 at 16:00

0

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

answered Mar 13 '12 at 16:00

Fred

1,011
1
10
36

That's not a stack, that's a list. – Serdalis Apr 16 '13 at 01:30

score 0 · Answer 6 · answered Mar 13 '12 at 17:04

Assuming no data structure should be used even not list to hold the final result here is one possible solution

The Stack here would be considered a list which supports the following function

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

Solution 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)]

Even you can code without using the IsEmpty ot NotEmpty functionality

Solution 2:

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

Note ** Using Exception for Conditional Checking is an accepted behavior in Python as it has no added overhead as in C++

Reversing a Stack in Python using recursion

6 Answers6