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

[编程题]用一个栈实现另一个栈的排序

热度指数：6308 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？

输入描述:

第一行输入一个N，表示栈中元素的个数
第二行输入N个整数表示栈顶到栈底的各个元素

输出描述:

输出一行表示排序后的栈中栈顶到栈底的各个元素。

示例1

输入

5
5 8 4 3 6

输出

8 6 5 4 3

备注:

1 <= N <= 10000
-1000000 <=  <= 1000000

算法知识视频讲解

Python3

毓毓子最可爱

# 输入的元素个数
n = int(input())
# 用列表模仿栈
stack = []
number = input().split()
number.reverse()
for i in range(len(number)):
    stack.append(int(number[i]))
# 辅助的栈
help = []
while len(stack) != 0:
    a = stack.pop()
    while len(help) != 0 and help[-1] < a:
        stack.append(help.pop())
    help.append(a)
while len(help) != 0:
    stack.append(help.pop())
# 输出栈顶到栈底
for i in range(len(stack)):
    print(stack.pop(), end=' ')

《程序员代码面试》Python题解 https://zhuanlan.zhihu.com/p/444550262

发表于 2021-12-26 08:05:51 回复(0)