按升序排序堆栈？

按升序排序堆栈的最佳方法是什么？ I遇到了这个面试问题，我遇到了一些问题，以找到最好和最有效的解决方案。按升序排序堆栈？

有两种方法我可以想到。

为了弹出堆栈中的所有内容，并将它们存储在数组中，然后在
O(nLog n)对数组进行排序，然后按内容备份堆栈。不是最好的方式....
执行递归执行堆栈的排序它

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); 
    } 
}

但第二个方法看起来好像有太多的递归调用和开销如果堆栈碰巧很大，将会成为问题。

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

有这么多的递归调用，（重叠的子问题），这是dynamic programming类型的问题的竞争者？

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

来源

2011-10-15 Legolas

为什么'O（n * log n）'排序时间次优？对于一般情况，这是已证实的限制。 –

你不能比'O（n）'空间和'O（n log n）'时间做得更好。弹出到数组中，排序和推送是最佳的。 – avakar

@avakar：得到第一个要求的证明（“不能做比'O（n）'空间好”）？ – NPE

这是一个堆栈。除了最高价值，你什么也看不到。你必须至少弹出一次，并且至少推一次。第一种方法很好。

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

来源

2011-10-15 18:14:30 bdares

它在C.道歉！ – Legolas

您可以通过消除递归来解决。为此，您只需使用一个循环在堆栈下迭代，直到它为空。

例如，伪码：

Linekd Stack stack = new List(); 

while stack is not empty then 

    element <- stack removes peek 

    // Recursiong 
    push new elements on stack 

end

来源

2011-10-15 18:18:22

我不认为这个伪代码甚至可以应用 – Legolas

你可以用迭代循环和堆栈数据结构来模拟递归 –

不一样吗递归使得函数调用进入堆栈内存，并且它只是相同的实现 – Legolas

-1

此问题不能有复杂性小于为O（n^2）。为进一步参考here

来源

2012-07-07 15:51:28 Moosa

链接被破坏... – Legolas

请再次参考这个问题（1）已经完成了这个 – Legolas

“这个算法会有一段时间O（N^2）的复杂性“并不意味着O（N^2）是最优的，在这种情况下，在O（N LG N）如问题本身所述！ – quasiverse

按升序排序堆栈？

回答

相关问题