这些堆栈是否需要合并？

在能力评估，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

这些堆栈是否需要合并？

回答

相关问题