如何使排序堆栈（最小的顶部）从两个排序堆栈？

Question

以下是完整的问题：

编写一个java方法，它将接受两个排序后的堆栈a和B（最小值在顶部），并返回一个排序后的堆栈D（最小值在顶部）。只允许使用堆栈操作，如pop、push、isEmpty和peek。

示例：假设A={（top）1,4,7,9}和B={（top）2,3,6}，那么函数将返回一个新的堆栈D={（top）1,2,3,4,6,7,9}

我写的代码是这样的：

     Public static stack myStack ( Stack A , Stack B) {
Stack D = new Stack();
D= A.length()+ B.length();
for ( int i = 0 ; i < D.length ; i++)
{
      if( A.top== -1)
             System.out.println(" Stack is Empty ");
      return A[ top ] ;

            if( B.top== -1)
                 System.out.println(" Stack is Empty ");
             return B[ top ] ;
                   if ( A[top] < B[top])
                      D[top]= A[top];
                   else
                       D[top]= B[top];
  } 
 return D;
}

你怎么认为？

Answer 1

请记住，本练习要求您仅使用堆栈操作（Push、Pop、Peek和IsEmpty），因此您无法在尝试执行直接索引时执行。但有些逻辑相当接近有效。

正如我在注释中建议的那样，我首先编写一个可以反转堆栈的方法。这在现在看来可能不太相关，但它是有用的。如果你考虑如何颠倒项目堆栈的顺序，这就非常简单了——从一个堆栈中取出最上面的项目，放在另一个堆栈的顶部。重复此操作，直到第一个堆栈是空的，并且您已经颠倒了顺序。

这为什么有用？因为您的大多数方法将构建与要求相反的内容—您将构建一个顶部有最大项的堆栈，然后作为最后一步，将其反转。

那么，如果您试图创建一个顶部有最大值的堆栈，那么如何开始呢？嗯，这个堆栈上最低的项目应该是最小的。因此，检查两个堆栈顶部的内容，并选择最低的项目作为第一个推到新堆栈上的项目。

虽然两个堆栈都有项目，但您可以继续这样做以建立堆栈。考虑到是空的，我建议您在一段时间内这样做。

一旦其中一个堆栈为空，您就可以从另一个堆栈中推送所有剩余的项来完成此构造。您应该意识到，您可以做到这一点，而不必在这里应用过多的控制流，而不仅仅是几个while循环，因为“从空列表中推送所有剩余项”实际上是不可行的。

而且，正如我在开始时所说，一旦你创建了这个（最大值在顶部）堆栈，你所需要做的就是反转它。