Python程序员面试算法宝典---解题总结: 第2章 栈、队列与哈希 2.3-2 如何对栈中元素排序

# -*- encoding: utf-8 -*-

import os

'''

Python程序员面试算法宝典---解题总结: 第2章 栈、队列与哈希 2.3-2对栈中所有元素排序

题目: 对栈进行排序，使得栈顶到栈底的元素按照从小到大的顺序。
例如输入栈是{1,3,2}其中2在栈顶，排序后的栈
为{3,2,1}，其中1在栈顶.

分析:
主要思想就是首先将栈底元素移动到栈顶;
这就需要先对除了栈顶的子栈的栈底元素移动子栈顶
2 -> 1
3    2
1    3
其中将栈底元素移动到栈顶也是递归

关键:
1 整体思路
步骤1: 
将栈底元素移动到栈顶，然后获取栈顶元素，弹出栈顶，然后对子栈进行处理，把栈顶元素插入到栈中
步骤2:
将栈底元素移动到栈顶的处理过程如下:
获取当前栈顶元素，弹出当前栈顶元素，然后递归调用当前方法处理子栈，获取处理后子栈的栈顶元素，
并弹出子栈的栈顶，按照大小先插入栈顶和次栈顶元素中的较大值，然后插入较小值

2
def sortStack(s):
    if s.empty():
        return
    # 将栈底元素移动到栈顶，然后获取栈顶元素，弹出栈顶，然后对子栈进行处理，把栈顶元素插入到栈中
    moveBottomToTop(s)
    top = s.getTop()
    s.pop()
    sortStack(s)
    s.push(top)
    
3
def moveBottomToTop(s):
    if s.empty():
        return
    top1 = s.getTop()
    s.pop()
    if not s.empty():
        # 获取递归处理子栈的结果
        moveBottomToTop(s)
        top2 = s.getTop()
        # 必须弹出次栈顶元素
        s.pop()
        if top1 < top2:
            s.push(top2)
            s.push(top1)
        else:
            s.push(top1)
            s.push(top2)
    else:
        s.push(top1)

参考:
Python程序员面试算法宝典

'''

class Stack(object):
    def __init__(self):
        self.list = list()

    # 栈顶元素放在列表的尾部
    def push(self, data):
        self.list.append(data)

    def empty(self):
        result = False if self.list else True
        return result

    def pop(self):
        if self.empty():
            print "stack is empty, it can not pop"
        else:
            self.list.pop()

    def getTop(self):
        if self.empty():
            print "stack is empty, it can not pop"
        else:
            return self.list[-1]

def moveBottomToTop(s):
    if s.empty():
        return
    top1 = s.getTop()
    s.pop()
    if not s.empty():
        # 获取递归处理子栈的结果
        moveBottomToTop(s)
        top2 = s.getTop()
        # 必须弹出次栈顶元素
        s.pop()
        if top1 < top2:
            s.push(top2)
            s.push(top1)
        else:
            s.push(top1)
            s.push(top2)
    else:
        s.push(top1)


def sortStack(s):
    if s.empty():
        return
    # 将栈底元素移动到栈顶，然后获取栈顶元素，弹出栈顶，然后对子栈进行处理，把栈顶元素插入到栈中
    moveBottomToTop(s)
    top = s.getTop()
    s.pop()
    sortStack(s)
    s.push(top)



# def sortStack(s):
#     if s.empty():
#         return
#     top = s.getTop()
#     s.pop()
#     # 递归处理子栈
#     sortStack(s)
#     # 处理完子栈，将栈顶元素插入进去
#     _sortStack(s)
#     s.push(top)


def process():
    stack = Stack()
    stack.push(1)
    stack.push(3)
    stack.push(2)
    sortStack(stack)
    while not stack.empty():
        top = stack.getTop()
        print top
        stack.pop()


if __name__ == "__main__":
    process() 

最后

以上就是朴实蜻蜓为你收集整理的Python程序员面试算法宝典---解题总结: 第2章 栈、队列与哈希 2.3-2 如何对栈中元素排序的全部内容，希望文章能够帮你解决Python程序员面试算法宝典---解题总结: 第2章 栈、队列与哈希 2.3-2 如何对栈中元素排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。