c - 按升序对堆栈进行排序？

Question

按升序对堆栈进行排序的最佳方法是什么？我遇到了这个面试问题，并且我遇到了一些问题以寻求最佳和最有效的解决方案。

我能想到的有两种方法。

1. 将栈中的内容全部弹出并存放到一个数组中，然后对数组进行排序
   O(nLog n) 然后将内容推回堆栈。不是最好的方法....

2. 递归实现栈的排序

void sort(stack)
{
    type x;

    if (!isEmpty(stack)) {
        x = pop(stack);
        sort(stack);
        insert(x, stack);
    }           
}

void insert(x, stack)
{
    type y;

    if (!isEmpty(stack) && top(stack) < x) {
        y = pop(stack);
        insert(x, stack);
        push(y, stack);
    } 
    else {
        push(x, stack);
    }
} 

但是第二种方法似乎进行了太多的递归调用，如果堆栈恰好非常大，开销将是一个问题。

是否有可能以更好的方式解决这个问题以获得最佳的空间和时间复杂度？

有这么多递归调用，(重叠子问题)，这是 动态规划 类型问题的竞争者吗？

解决这个问题的最佳方法是什么？ ？

Answer 1

这是一个堆栈。除了最高值，您什么也看不到。您必须至少弹出一次所有内容，并至少一次推送所有内容。第一种方法没问题。

如果堆栈操作很昂贵，但您有时间期限，请在弹出时使用插入排序，并且您可以在最后一次弹出完成后立即推送。但是你说这是在 C++ 中，所以我怀疑我们是否正在考虑这种情况。