Reversing a Stack in Python

Question

To reverse a stack:

1. I made a empty temporary stack
2. I used tempstack.push(stack.pop())
3. and then renamed it to stack = tempstack

but it doesn't seem to work. Any idea why?

To call this, I want to use just reverse(stack), not stack = reverse(stack).

def reverse(stack):
    new_stack = Stack()
    while not stack.is_empty():
        new_stack.push(stack.pop())
    stack = new_stack

Answer 1

If you're using actual lists to implement stacks (that is, if Stack inherits from list or basically is a list), then simply reverse the list in-place:

def reverse_stack(stack):
    stack.reverse()

I renamed the function to reverse_stack just to avoid confusion; you could still call it reverse. Example:

>>> stack = [1, 2, 3]
>>> reverse_stack(stack)
>>> stack
[3, 2, 1]

However, it seems that your Stack class doesn't inherit from list but keeps the underlying list in a private attribute, so you can't directly use any of the MutableSequence API on a Stack. Hence,

Version2, using only is_empty, push and pop methods of Stack

and using only Stacks, not lists or deques etc. First, a couple of helper functions:

def reverse_copy_stack(stack, rev_stack=None):
    '''Return a reversed copy of stack, which is emptied.
    rev_stack receives the reversed copy if it's not None
    '''
    if rev_stack is None:
        rev_stack = Stack()
    while not stack.is_empty():
        rev_stack.push(stack.pop())
    return rev_stack

def copy_stack(stack):
    '''Return a copy of stack, which is emptied.'''
    return reverse_copy_stack( reverse_copy_stack(stack))

Now we can implement reverse_stack:

def reverse_stack(stack):
    '''Reverse stack in-place'''
    new_stack = copy_stack(stack)
    # Empty stack
    while not stack.is_empty():
        stack.pop()
    # put reversed copy of new_stack in stack
    reverse_copy_stack(new_stack, stack)

Answer 2

As others pointed out, the last assignment doesn't do anything. However, the idea behind the exercise here is probably to only use the standard stack primitives push, pop, and is_empty, without relying on the exact stack implementation to make use of list.reverse and such.

The key point to notice is that stack is a last-in-first-out structure, so reading its contents automatically produces them in the reverse order. This is why a solution that uses another stack for temporary storage doesn't work:

def reverse(stack):
    # Doesn't work
    temp = Stack()
    while not stack.is_empty():
        temp.push(stack.pop())
    while not temp.is_empty():
        stack.push(temp.pop())

Here the stack contents get reversed twice: once when reading them from the original stack, and once when reading them from the temporary stack, so you end up with stack contents in the original order. To actually reverse a stack, you need extract the items into a list and then traverse it in order (from beginning to end), pushing the items on the original stack as they come:

def reverse(stack):
    items = []
    while not stack.is_empty():
        items.append(stack.pop())
    for item in items:
        stack.push(item)

Edit: inspired by BrianO's answer, here is a version that doesn't use a list at all (but does instantiate two temporary stacks):

def reverse(stack):
    tmp1 = Stack()
    while not stack.is_empty():
        tmp1.push(stack.pop())
    tmp2 = Stack()
    while not tmp1.is_empty():
        tmp2.push(tmp1.pop())
    while not tmp2.is_empty():
        stack.push(tmp2.pop())

Here the idea is to make use of the fact that copying the stack does reverse the contents - it's just that copying it back reverses it again. So we just copy it three times, first from the original stack to a temporary stack, then from a temporary stack to another temporary stack, and finally from the other temporary stack to the original stack. Reversing the contents three times ends up with the original contents reversed, which was required.

Answer 3

Add a return value

def reverse(stack):
    new_stack = Stack()
    while not stack.is_empty():
        new_stack.push(stack.pop())
    return new_stack

and when calling the function do this:

stack = reverse(stack)

You are assigning value to stack inside function but not from where you called it. Issues with scope.

Answer 4

It looks like you should have written while not stack.is_empty():

(After the edit) Ok, now instead of stack = new_stack, it should say return new_stack. The function should be called with stack = reverse(stack).

(Responding to comments) If returning a value is not an option, then we need to know what methods there are to modify Stack objects. Saying stack = new_stack or stack = Stack() will not change it outside of the function.

Something like this should work:

def reverse(stack):
    new_stack = Stack()
    while not stack.is_empty():
        new_stack.push(stack.pop())
    stack._items = new_stack._items

However it's probably a bad idea because the underscore in front of _items shows that whoever wrote the Stack class didn't want it to be used that way.

Plus as @user4815162342 pointed out, this presumably reverses the stack twice, so instead of using a temporary new_stack = Stack() we should just use a temporary list. Really @user4815162342's answer is the best one.

Answer 5

If the Stack class is yours or you can extend it, then another way of reversing the stack would be to keep all the data intact, and keep track of which way up your stack is (growing up or down) and either push/pop to the top or the bottom of the stack depending on the stack direction. Your stack reverse method is then simply a case of changing the flag which determines whether your stack grows up or down.

I don't have any code as yet, but if your stack is large then changing a flag may well be far simpler than reversing a large list of data.

Answer 6

class Stack():
    def __init__(self):
        self.item=[]
        self.n=0
    def __len__(self):
        return self.n
    def isEmpty(self):
        return self.n==0
    def push(self,item):
        self.item.append(item)
        self.n+=1
    def pop(self):
        ele=self.item.pop()
        self.n-=1
        return ele
    def getPeek(self):
        if self.n>0:
            return self.item[-1]
        return "Stack is empty"
    def getStackitem(self):
        return [self.item[i] for i in range(self.n)]


def reversing(data):
    x=Stack()
    for i in data:
        x.push(i)
    y=Stack()
    while not x.isEmpty():
        y.push(x.pop())
    return "".join(y.getStackitem())

print(reversing("123456789")) 

Answer 7

Copy the stack first, empty the original stack, then follow your method.

def reverse(stack):
    old_stack = stack[:]
    while not stack.is_empty():
        stack.pop()
    while not old_stack.is_empty():
        stack.push(old_stack.pop())