Stay Hungry, Stay Foolish

用一个辅助栈实现另一个栈的排序

题目要求仅借助一个辅助栈,可以申请新变量,但不能申请额外数据结构,来对另一个栈进行从栈顶到栈底的从大到小的排序。
思想是先从源栈中弹出栈顶元素到临时变量,比较临时变量与辅助栈栈顶元素的关系,如果临时变量大于辅助栈栈顶元素,则弹出辅助栈栈顶元素直到辅助栈栈顶元素小于等于临时变量或辅助栈为空,然后将临时变量压入辅助栈。再次从源栈弹出栈顶元素到临时变量,迭代这个过程直到源栈为空。就完成了元素在辅助栈中从小到大的排序。依次出栈辅助栈中所有元素压入到源栈则完成源栈从大到小的排序。
直接上代码:

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]
喜欢 (0)
取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦


Warning: Use of undefined constant PRC - assumed 'PRC' (this will throw an Error in a future version of PHP) in C:\inetpub\wordpress\wp-content\themes\XHBlog\comments.php on line 17
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址