cc 3.6

sortStack.py

# 3.6 Write a program to sort a stack in ascending order (with biggest items on top). You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (such as an array).The stack supports the following operations: push, pop, peek, and isEmpty.


from stack import Stack

def sort(stack):
    result = Stack()
    while stack.isEmpty() is not True:
        tmp = stack.pop()
        while result.isEmpty() is not True and result.peek() > tmp:
            stack.push(result.pop()) #push larger items back to original stack
        result.push(tmp)
    result.printStack()

#test
test = Stack()
test.push(2)
test.push(8)
test.push(5)
test.push(6)
test.push(4)
print 'the original stack:',
test.printStack()
print 'sorting in ascending order:'
sort(test)