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

CodePudding user response：

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]