按升序排序堆棧？

按升序排序堆棧的最佳方法是什麼？ 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

按升序排序堆棧？

回答

相關問題