这些堆栈需要合并吗？
在作为98-361“软件开发基础”考试的一部分的能力评估中，会弹出以下问题：
场景3-3:使用堆栈
您正在编写一个使用两个堆栈的程序。每个堆栈中的数据已经按降序排列。您需要处理两个堆栈的内容，以便将输出打印在屏幕升序上。你怎么写这样的程序？
现在，我已经对这个场景进行了编码。我的解决方案是在两个不同的堆栈上迭代，将它们合并到一个列表中，方法是将它们的项弹出，直到堆栈为空，然后按照正确的顺序对列表进行排序。
然而，我觉得这个问题有点模糊，我是否应该合并这些堆栈。这是一种暗示，但实际上并非如此。
如果你正在读这个问题，你会怎么解释它？
请注意，我实际上并没有参加这次考试，只是在为考试做准备。在我看来，这更像是一个需求解释的问题。
回答 3
Stack Overflow用户
发布于 2012-02-13 11:27:32
我想你是对的。这是我最初的解释(虽然我同意这似乎有点模糊)。而且，在我看来，似乎没有必要指定两个堆栈，除非它们应该合并。
Stack Overflow用户
发布于 2012-02-13 11:06:43
我的观点是：
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) -用于上述解决方案
Stack Overflow用户
发布于 2012-02-13 11:39:04
这个问题听起来像是一个合并排序的设置；为了以一个组合的、排序的(但反向的)顺序获取两个堆栈的内容，您可以反复查看每个堆栈的顶部，查看哪个值较低(id est，在降序排序的前面)，将值从堆栈中弹出并将其推到第三个堆栈中。重复，直到两个源堆栈都为空，并且由于第三个堆栈是FILO，您按降序添加的项将按升序弹出。
https://stackoverflow.com/questions/9259321
复制相似问题
腾讯云开发者
