题目要求仅借助一个辅助栈,可以申请新变量,但不能申请额外数据结构,来对另一个栈进行从栈顶到栈底的从大到小的排序。
思想是先从源栈中弹出栈顶元素到临时变量,比较临时变量与辅助栈栈顶元素的关系,如果临时变量大于辅助栈栈顶元素,则弹出辅助栈栈顶元素直到辅助栈栈顶元素小于等于临时变量或辅助栈为空,然后将临时变量压入辅助栈。再次从源栈弹出栈顶元素到临时变量,迭代这个过程直到源栈为空。就完成了元素在辅助栈中从小到大的排序。依次出栈辅助栈中所有元素压入到源栈则完成源栈从大到小的排序。
直接上代码:
class helpStackSort:
__helpStack=[]
def Sort(self,inputStack):
while inputStack:
tmppop = inputStack.pop()
while self.__helpStack and self.__helpStack[-1] < tmppop:
inputStack.append(self.__helpStack.pop())
self.__helpStack.append(tmppop)
print('辅助:',self.__helpStack)
print('源栈:',inputStack)
while self.__helpStack:
inputStack.append(self.__helpStack.pop())
print('源栈:', inputStack)
return inputStack
测试:
hs=helpStackSort() print(hs.Sort([1,3,2,5,3,6]))
运行结果:
辅助: [6] 源栈: [1, 3, 2, 5, 3] 辅助: [6, 3] 源栈: [1, 3, 2, 5] 辅助: [6, 5] 源栈: [1, 3, 2, 3] 辅助: [6, 5, 3] 源栈: [1, 3, 2] 辅助: [6, 5, 3, 2] 源栈: [1, 3] 辅助: [6, 5, 3, 3] 源栈: [1, 2] 辅助: [6, 5, 3, 3, 2] 源栈: [1] 辅助: [6, 5, 3, 3, 2, 1] 源栈: [] 源栈: [1, 2, 3, 3, 5, 6]


