這些堆棧是否需要合併？

在能力評估，98-361考試的一部分，軟件開發基礎，這個問題會彈出：這些堆棧是否需要合併？

場景3-3：使用堆棧

你要編寫一個使用兩個方案棧。每個堆棧中的數據已經以降序排列。您需要以這種方式處理這兩個堆棧的內容，以便輸出結果按照屏幕升序顯示。你會如何編寫這樣的程序？

現在，我已經編寫了這個場景。我的解決方案是迭代兩個單獨的堆棧，通過彈出它們的項目將它們合併到List中，直到堆棧爲空，並按照正確的順序對列表進行排序。

但是，這讓我覺得這個問題對於我是否應該合併堆棧有些模糊。它的種的暗示，但它種的不是。

如果你在閱讀這個問題，你會如何解讀它？

請注意，我實際上沒有參加此考試，只是爲此準備。這是更多的要求的解釋問題，在這一點上，在我的腦海裏。

來源

2012-02-13 Mike Hofer

我認爲你是對的。在我看來，除非它們被合併，否則不需要指定*兩個*堆棧。 – Blorgbeard 2012-02-13 11:08:14

@Blorgbeard：這就是我的想法。「兩堆」的特殊性似乎意味着他們希望它們合併。任何機會，你可以把這個答案，所以你得到信貸？ – 2012-02-13 11:18:10

的解決方案，我認爲你是正確的。這是我最初的解釋（儘管我同意它似乎有點含糊）。在進一步的思考中，在我看來，沒有必要指定兩個堆棧，除非它們應該被合併。

來源

2012-02-13 11:27:32 Blorgbeard

我的觀點：

DECLARE NEW_LIST; 
INT COUNT = STACK_A.COUNT() + STACK_B.COUNT() 

FOR I=0 TO COUNT-1 
    IF STACK_A.PEEK() > STACK_B.PEEK() 
     NEW_LIST.ADD(STACK_A.POP()) 
    ELSE 
     NEW_LIST.ADD(STACK_B.POP());

現在你有NEW_LIST其排序 - 你只需要打印順序的決定（按升序排列扭轉）

假設m, n是初始大小的兩個堆棧，

合併兩個堆棧然後對列表進行排序將花費更多 -

O((n+m)log(n+m))爲快速排序，這顯然是慢

O(m+n) - 上面

來源

2012-02-13 11:06:43 Shai

爲什麼不使用託管堆棧呢？我認爲這更像他們之後的事情。但上面的解決方案應該可以。 – leppie 2012-02-13 11:08:56

不回答OP的問題.. – Blorgbeard 2012-02-13 11:09:33

這是我解釋問題的方式，-1表示什麼？這是我*會給這個問題的答案，而且OP肯定能夠找到這個帖子有用。 OP提到他通過合併和整理得到了這一個;確實，在求職面試中知道如何實際編寫代碼非常重要，但是一些僱主*會*尋找優化的解決方案，而不是簡單，慢速的解決方案。軟件工程師當然需要考慮到這一點！ – Shai 2012-02-13 11:12:20

這個問題聽起來像一個合併排序的設置;要以合併，排序（但顛倒）的順序獲取內容，您需要反覆查看每個堆棧的頂部以查看哪個值較低（id est，按照降序排序），將該值從堆棧中彈出，推到第三個堆棧。重複，直到兩個源堆棧都爲空，並且因爲第三個堆棧是FILO，則按降序添加的項目將按升序彈出。

來源

2012-02-13 11:39:04 FacticiusVir

這些堆棧是否需要合併？

回答

相關問題