栈排序算法实现：对栈排序使栈顶元素为最大值

问题描述 #

给定一个栈结构，需要对其完成降序排序，排序后栈顶元素为整个栈的最大值。

输入输出示例 #

• 示例1

输入：Stack: 3 2 1
输出：3 2 1

• 示例2

输入：Stack: 11 2 32 3 41
输出：41 32 11 3 2

要求与约束 #

• 预期时间复杂度为O(N²)
• 递归实现的预期辅助空间为O(N)
• 栈元素数量约束：1 ≤ N ≤ 100

实现思路 #

采用递归思路实现，核心分为两个步骤：

1. 递归弹出栈顶元素直到栈为空，回溯阶段每次将弹出的元素插入到已排序栈的对应位置
2. 插入逻辑：如果当前栈为空，或要插入的元素大于等于栈顶元素，直接压入栈；否则先弹出栈顶元素，递归完成插入后再把弹出的元素压回栈

代码实现（Python版本） #

def sort_stack(stack):
    if stack:
        # 弹出栈顶元素
        temp = stack.pop()
        # 递归排序剩余栈
        sort_stack(stack)
        # 将弹出的元素插入到合适位置
        insert(stack, temp)
    return stack

def insert(stack, num):
    # 栈为空或num大于等于栈顶元素时直接插入
    if not stack or num >= stack[-1]:
        stack.append(num)
    else:
        # 弹出栈顶元素，插入完成后再压回
        temp = stack.pop()
        insert(stack, num)
        stack.append(temp)

# 测试用例
if __name__ == "__main__":
    # 示例1测试
    stack1 = [3,2,1]
    print(sort_stack(stack1)) # 输出 [3,2,1]
    # 示例2测试
    stack2 = [11,2,32,3,41]
    print(sort_stack(stack2)) # 输出 [41,32,11,3,2]

内容的提问来源于stack exchange，提问作者Ishita