I have three stacks. The first one has elements in it. The other ones are just for help. How do I sort a stack using only push, pop, peek and empty operators? This is what I have done.
def sort(stack1, stack2, stack3): while not stack1.empty(): temp = stack1.pop() while not stack2.empty() and stack2.peek() > temp: stack1.push(stack2.pop()) stack2.push(temp) return stack1
It seems that you haven’t used the
stack3 which was meant to be a temporary holder for the items in
stack2 that are greater than
temp. Also, don’t modify
stack1, besides the fact that it just contains the source unsorted items, you are pushing into it and then popping, which would be an endless cycle.
For your guidance, here are the roles of the stacks:
stack1– Contains the original data. That’s it, nothing more. You should just pop its items until empty. But of course while getting each item, make sure that your other stacks are maintaining a sorted set of items.
stack2– Contains the sorted data. This is the one that you should return. It is mandatory to keep the items in here as sorted.
stack3– Temporary holder for the sorted items in
stack2. Let’s say
1->4->5. For us to insert
3while maintaining the order, we can’t just push it on top as that will make it
1->4->5->3. Instead, we will keep on popping the already-sorted data and put it temporarily to
stack3until the point where we can already insert
5->4(this will also be in order, descending in particular). Once we pushed
1->3, we can then return the items we temporarily stored here in
stack3thus bringing it back to
class Stack(list): def empty(self): return len(self) == 0 def push(self, value): self.append(value) def peek(self): return self[-1] def sort(stack1, stack2, stack3): while not stack1.empty(): temp = stack1.pop() while not stack2.empty() and stack2.peek() > temp: stack3.push(stack2.pop()) stack2.push(temp) while not stack3.empty(): stack2.push(stack3.pop()) return stack2 print(sort(Stack([1,5,4,2,3]), Stack(), Stack())) print(sort(Stack([5,4,3,1,2]), Stack(), Stack())) print(sort(Stack([1,2,3,5,4]), Stack(), Stack()))
[1, 2, 3, 4, 5] [1, 2, 3, 4, 5] [1, 2, 3, 4, 5]