To reverse a stack:
tempstack.push(stack.pop())stack = tempstackbut 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
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,
is_empty, push and pop methods of Stackand 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)
Stack but we don't know what those are. Can you use append or extend of the underlying list class?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.
lists after all? The constraints of the problem really were not clear.
stack._items.reverse() (or stack.reverse() if the stack were implemented as a list itself). This answer doesn't presume anything about the implementation of Stack. Still, I like your answer better because it doesn't rely on an external data structure at all, it does its magic with pure recursion.Stack implementation is supposed to be opaque. I assumed that similarly it would be "cheating" (as in, too easy) to copy the elements to a two-way structure like a list or deque. If the question is a class assignment, the OP will find out soon enough ;) PS -- no "recursion" involved.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.
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.
while stack:, if the implementation is sensible.None is appropriate), but without knowing the implementation we can't tell you how.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.
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"))
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())
old_stack = stack does not create a copyold_stack = stack[:] does.Stacks. It emerges, in fact, that it probably doesn't copy those at all. The class probably doesn't inherit from list, but keeps the underlying list in a private attribute. I addressed this in my answer & comments leading up to the Version2 there.
stack = new_stackwill only make a difference inside the function, whatever object you passed in will be unaffected. Considerreturn new_stackthen dostack = reverse(stack)outside.