算法：使用栈来排序一个栈

算法

版本：1
作者：陈小默
声明：禁止商用，禁止转载

发布于作业部落、CSDN博客

题目

一个栈中的元素类型为整型，如何在只用一个栈的情况下对原始数据排序？

要求

使用任意语言实现，不能使用其他数据结构。

思路

使用一个栈来存放排序过的数据，和一个额外变量用来存储需要排序的数据。

实现

fun sort(stack: Stack<Int>) {
    val help = Stack<Int>(stack.max)
    var value: Int? = null
    while (!stack.isEmpty) {
        value = stack.pop()
        while (!help.isEmpty && help.top < value)
            stack.push(help.pop())
        help.push(value)
    }
    while (!help.isEmpty)
        stack.push(help.pop())
}