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

## Answer

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`stack2`

has items`1->4->5`

. For us to insert`3`

while 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`stack3`

until the point where we can already insert`3`

. Thus,`stack2`

would be`1`

while`stack3`

would be`5->4`

(this will also be in order, descending in particular). Once we pushed`3`

making`stack2`

as`1->3`

, we can then return the items we temporarily stored here in`stack3`

thus bringing it back to`1->3->4->5`

.

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

**Output:**

[1, 2, 3, 4, 5] [1, 2, 3, 4, 5] [1, 2, 3, 4, 5]